Squared Distances

Introduction

There is a family of functions called CGAL_squared_distance that compute the square of the Euclidean distance between two geometric objects.

The squared distance between two two-dimensional points p1 and p2 is defined as $d$_x² + d_y², where $d$_x == p2.x()-p1.x() and $d$_y== p2.y()-p1.y().

For arbitrary two-dimensional geometric objects obj1 and obj2 the squared distance is defined as the minimal CGAL_squared_distance(p1, p2), where p1 is a point of obj1 and p2 is a point of obj2. Note that for objects like triangles and polygons that have an inside (a bounded region), this inside is part of the object. So, the squared distance from a point inside a triangle to that triangle is zero, not the squared distance to the closest edge of the triangle.

The general format of the functions is:

R::FT

CGAL_squared_distance ( Type1<R> obj1, Type2<R> obj2)

where the types Type1 and Type2 can be any of the following:

\itemsep0pt\topsep0pt\partopsep0pt\parsep0pt
• CGAL_Point_2
• CGAL_Line_2
• CGAL_Ray_2
• CGAL_Segment_2
• CGAL_Triangle_2

Those routines are defined in the header file CGAL/squared_distance.h.

Why the square?

There are routines that compute the square of the Euclidean distance, but no routines that compute the distance itself. Why?

First of all, the two values can be derived from each other quite easily (by taking the square root or taking the square). So, supplying only the one and not the other is only a minor inconvenience for the user.

Second, often either value can be used. This is for example the case when (squared) distances are compared.

Third, the library wants to stimulate the use of the squared distance instead of the distance. The squared distance can be computed in more cases and the computation is cheaper. We do this by not providing the perhaps more natural routine,

The problem of a distance routine is that it needs the sqrt operation. This has two drawbacks.

• The sqrt operation can be costly. Even if it is not very costly for a specific number type and platform, avoiding it is always cheaper.
• There are number types on which no sqrt operation is defined, especially integer types and rationals.

Distance Comparisons

Instead of computing distances and comparing them the following predicates can be used to that:

#include <CGAL/distance_predicates_2.h>

CGAL_Comparison_result
	CGAL_cmp_dist_to_point ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		compares the distances of points q and r to point p. returns CGAL_SMALLER, iff q is closer to p than r, CGAL_LARGER, iff r is closer to p than q, and CGAL_EQUAL otherwise.
bool	CGAL_has_larger_dist_to_point ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		returns true iff the distance between q and p is larger than the distance between r and p.
bool	CGAL_has_smaller_dist_to_point ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		returns true iff the distance between q and p is smaller than the distance between r and p.

The following compares the signed distances of two points and an oriented line. The sign of the distance of a point to an oriented line is positive (negative) iff the point lies on the positive (negative) side of the line, and zero otherwise.

CGAL_Comparison_result
	CGAL_cmp_signed_dist_to_line ( CGAL_Line_2<R> l, CGAL_Point_2<R> p, CGAL_Point_2<R> q)
		returns CGAL_LARGER iff the signed distance of p and q is larger than the signed distance of q and l, CGAL_SMALLER, iff it is smaller, and CGAL_EQUAL iff both are equal.
bool	CGAL_has_larger_signed_dist_to_line ( CGAL_Line_2<R> l, CGAL_Point_2<R> p, CGAL_Point_2<R> q)
		returns true iff the signed distance of p and q is larger than the signed distance of q and l.
bool	CGAL_has_smaller_signed_dist_to_line ( CGAL_Line_2<R> l, CGAL_Point_2<R> p, CGAL_Point_2<R> q)
		returns true iff the signed distance of p and q is smaller than the signed distance of q and l.

The following functions corresponds to the preceding ones with the exception that the line is implicitly given by the first two points p and q. The points whose signed distance to the line is compared are r and s.

Precondition: Points defining the line are not equal.

CGAL_Comparison_result
	CGAL_cmp_signed_dist_to_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r, CGAL_Point_2<R> s)
bool	CGAL_has_smaller_signed_dist_to_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r, CGAL_Point_2<R> s)
bool	CGAL_has_larger_signed_dist_to_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r, CGAL_Point_2<R> s)