2D Geometric Predicates

Order Type Predicates

Orientation	orientation ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
		returns LEFTTURN, if $$r lies to the left of the oriented line $$l defined by $$p and $$q, returns RIGHTTURN if $$r lies to the right of $$l, and returns COLLINEAR if $$r lies on $$l.

The following functions return true or false depending on whether the orientation of three points is equal to one of the constants mentioned in .

bool	leftturn ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
bool	rightturn ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
bool	collinear ( Point_2<R> p, Point_2<R> q, Point_2<R> r)

Finally, there are some special cases of collinearity. If we not only want to know if three points are collinear but also if they respect a certain order on the line, these are the functions to call:

bool	are_ordered_along_line ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
		returns true, iff the three points are collinear and q lies between p and r. Note that true is returned, if q==p or q==r.
bool	are_strictly_ordered_along_line ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
		returns true, iff the three points are collinear and q lies strictly between p and r. Note that false is returned, if q==p or q==r.

If we already know that three points are collinear, we should not check it again.

bool	collinear_are_ordered_along_line ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
		returns true, iff q lies between p and r. Precondition: p, q and r are collinear.
bool	collinear_are_strictly_ordered_along_line ( Point_2<R> p, Point_2<R> q, Point_2<R> r)
		returns true, iff q lies strictly between p and r. Precondition: p, q and r are collinear.

The Incircle Test

#include <CGAL/predicates_on_points_2.h>

Instead of constructing a circle and performing the test if a given point lies inside or outside you might use the following predicate:

Bounded_side	side_of_bounded_circle ( Point_2<R> p, Point_2<R> q, Point_2<R> r, Point_2<R> test)
		returns the relative position of point test to the circle defined by $$p, $$q and $$r. The order of the points $$p, $$q and $$r does not matter. Precondition: p, q and r are not collinear.
Oriented_side	side_of_oriented_circle ( Point_2<R> p, Point_2<R> q, Point_2<R> r, Point_2<R> test)
		returns the relative position of point test to the oriented circle defined by $$p, $$q and $$r. The order of the points $$p, $$q and $$r is important, since it determines the orientation of the implicitly constructed circle. Precondition: p, q and r are not collinear.

Comparison of Coordinates of Points

In order to check if two points have the same $$x or $$y coordinate we provide the following functions. They allow to write code that does not depend on the representation type.

#include <CGAL/predicates_on_points_2.h>

bool	x_equal ( Point_2<R> p, Point_2<R> q)
		returns true, iff p and q have the same x-coordinate.
bool	y_equal ( Point_2<R> p, Point_2<R> q)
		returns true, iff p and q have the same y-coordinate.

The above functions, returning a bool, are decision versions of the following comparison functions, returning a Comparison_result.

Comparison_result	compare_x ( Point_2<R> p, Point_2<R> q)
Comparison_result	compare_y ( Point_2<R> p, Point_2<R> q)

CGAL offers the same functions for points given implicitly as intersection of two lines. We provide these functions because we can provide better code for the test, than simply computing the intersection and calling the respective function for points.

Precondition: Lines that define an intersection point may not be parallel.

#include <CGAL/predicates_on_lines_2.h>

Comparison_result	compare_x ( Point_2<R> p, Line_2<R> l1, Line_2<R> l2)
		compares the $$x-coordinates of $$p and the intersection of lines $$l1 and $$l2, see (a) in the figure below.
Comparison_result	compare_x ( Line_2<R> l, Line_2<R> h1, Line_2<R> h2)
		compares the $$x-coordinates of the intersection of line $$l with line $$h1 and with line $$h2, see (b) in the figure below.
Comparison_result	compare_x ( Line_2<R> l1, Line_2<R> l2, Line_2<R> h1, Line_2<R> h2)
		compares the $$x-coordinates of the intersection of lines $$l1 and $$l2 and the intersection of lines $$h1 and $$h2, see (c) in the figure below.

Comparison_result	compare_y ( Point_2<R> p, Line_2<R> l1, Line_2<R> l2)
		compares the $$y-coordinates of $$p and the intersection of lines $$l1 and $$l2, see (a) in the figure above.
Comparison_result	compare_y ( Line_2<R> l, Line_2<R> h1, Line_2<R> h2)
		compares the $$y-coordinates of the intersection of line $$l with line $$h1 and with line $$h2, see (b) in the figure above.
Comparison_result	compare_y ( Line_2<R> l1, Line_2<R> l2, Line_2<R> h1, Line_2<R> h2)
		compares the $$y-coordinates of the intersection of lines $$l1 and $$l2 and the intersection of lines $$h1 and $$h2 , see (c) in the figure above.

The following functions compare the y coordinate of a point (that may be given implicitly) with a line.

Precondition: If the point is given as an intersection of two lines these lines may not be parallel. Lines where points are projected on may not be vertical.

Comparison_result	compare_y_at_x ( Point_2<R> p, Line_2<R> h)
		compares the $$y-coordinates of $$p and the vertical projection of p on h, see (d) in the figure below.
Comparison_result	compare_y_at_x ( Point_2<R> p, Line_2<R> h1, Line_2<R> h2)
		This function compares the $$y-coordinates of the vertical projection of p on h1 and on h2, see (e) in the figure below.
Comparison_result	compare_y_at_x ( Line_2<R> l1, Line_2<R> l2, Line_2<R> h)
		Let $$p be the intersection of lines $$l1 and $$l2. This function compares the $$y-coordinates of $$p and the vertical projection of p on h, see (f) in the figure below.
Comparison_result	compare_y_at_x ( Line_2<R> l1, Line_2<R> l2, Line_2<R> h1, Line_2<R> h2)
		Let $$p be the intersection of lines $$l1 and $$l2. This function compares the $$y-coordinates of the vertical projection of p on h1 and on h2, see (g) in the figure below.

For lexicographical comparison CGAL provides

Comparison_result	compare_lexicographically_xy ( Point_2<R> p, Point_2<R> q)
		Compares the Cartesian coordinates of points p and q lexicographically in $$xy order: first $$x-coordinates are compared, if they are equal, $$y-coordinates are compared.

In addition, CGAL provides the following comparison functions returning true or false depending on the result of compare_lexicographically_xy(p,q).

bool	lexicographically_xy_smaller_or_equal ( Point_2<R> p, Point_2<R> q)
bool	lexicographically_xy_smaller ( Point_2<R> p, Point_2<R> q)
bool	lexicographically_xy_larger_or_equal ( Point_2<R> p, Point_2<R> q)
bool	lexicographically_xy_larger ( Point_2<R> p, Point_2<R> q)

See Also

Distance comparisons, Section .