2D Geometric Predicates

Order Type Predicates

CGAL_Orientation	CGAL_orientation ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		returns CGAL_LEFTTURN, if $r$ lies to the left of the oriented line $l$ defined by $p$ and $q$, returns CGAL_RIGHTTURN if $r$ lies to the right of $l$, and returns CGAL_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	CGAL_leftturn ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
bool	CGAL_rightturn ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
bool	CGAL_collinear ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_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	CGAL_are_ordered_along_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_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	CGAL_are_strictly_ordered_along_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_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	CGAL_collinear_are_ordered_along_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		returns true, iff q lies between p and r. Precondition: p, q and r are collinear.
bool	CGAL_collinear_are_strictly_ordered_along_line ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r)
		returns true, iff q lies strictly between p and r. Precondition: p, q and r are collinear.

The Incircle Test

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

CGAL_Bounded_side	CGAL_side_of_bounded_circle ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r, CGAL_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.
CGAL_Oriented_side	CGAL_side_of_oriented_circle ( CGAL_Point_2<R> p, CGAL_Point_2<R> q, CGAL_Point_2<R> r, CGAL_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	CGAL_x_equal ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)
		returns true, iff p and q have the same x-coordinate.
bool	CGAL_y_equal ( CGAL_Point_2<R> p, CGAL_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 CGAL_Comparison_result.

CGAL_Comparison_result
	CGAL_compare_x ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)
CGAL_Comparison_result
	CGAL_compare_y ( CGAL_Point_2<R> p, CGAL_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>

CGAL_Comparison_result
	CGAL_compare_x ( CGAL_Point_2<R> p, CGAL_Line_2<R> l1, CGAL_Line_2<R> l2)
		compares the $x$-coordinates of $p$ and the intersection of lines $l1$ and $l2$ , see (a) in the figure below.
CGAL_Comparison_result
	CGAL_compare_x ( CGAL_Line_2<R> l, CGAL_Line_2<R> h1, CGAL_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.
CGAL_Comparison_result
	CGAL_compare_x ( CGAL_Line_2<R> l1, CGAL_Line_2<R> l2, CGAL_Line_2<R> h1, CGAL_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.

CGAL_Comparison_result
	CGAL_compare_y ( CGAL_Point_2<R> p, CGAL_Line_2<R> l1, CGAL_Line_2<R> l2)
		compares the $y$-coordinates of $p$ and the intersection of lines $l1$ and $l2$ , see (a) in the figure above.
CGAL_Comparison_result
	CGAL_compare_y ( CGAL_Line_2<R> l, CGAL_Line_2<R> h1, CGAL_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.
CGAL_Comparison_result
	CGAL_compare_y ( CGAL_Line_2<R> l1, CGAL_Line_2<R> l2, CGAL_Line_2<R> h1, CGAL_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 an 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.

CGAL_Comparison_result
	CGAL_compare_y_at_x ( CGAL_Point_2<R> p, CGAL_Line_2<R> h)
		compares the $y$-coordinates of $p$ and the vertical projection of p on h , see (d) in the figure below.
CGAL_Comparison_result
	CGAL_compare_y_at_x ( CGAL_Point_2<R> p, CGAL_Line_2<R> h1, CGAL_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.
CGAL_Comparison_result
	CGAL_compare_y_at_x ( CGAL_Line_2<R> l1, CGAL_Line_2<R> l2, CGAL_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.
CGAL_Comparison_result
	CGAL_compare_y_at_x ( CGAL_Line_2<R> l1, CGAL_Line_2<R> l2, CGAL_Line_2<R> h1, CGAL_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

CGAL_Comparison_result
	CGAL_compare_lexicographically_xy ( CGAL_Point_2<R> p, CGAL_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 CGAL_compare_lexicographically_xy(p,q).

bool	CGAL_lexicographically_xy_smaller_or_equal ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)
bool	CGAL_lexicographically_xy_smaller ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)
bool	CGAL_lexicographically_xy_larger_or_equal ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)
bool	CGAL_lexicographically_xy_larger ( CGAL_Point_2<R> p, CGAL_Point_2<R> q)

See Also