3D Geometric Predicates

Order Type Predicates

#include <CGAL/predicates_on_points_3.h>

CGAL_Orientation	CGAL_orientation ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r, CGAL_Point_3<R> s)
		returns CGAL_POSITIVE, if $s$ lies on the positive side of the oriented plane $h$ defined by $p$, $q$, and $r$, returns CGAL_NEGATIVE if $s$ lies on the negative side of $h$, and returns CGAL_COPLANAR if $s$ lies on $h$.
bool	CGAL_coplanar ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r, CGAL_Point_3<R> s)
		returns true, if $p$, $q$, $r$, and $s$ are coplanar.
bool	CGAL_collinear ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r)
		returns true, if $p$, $q$, and $r$ are collinear.

Analogously to the two-dimensional case, there are some additional tests for 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_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<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_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<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 (as it is an expensive operation).

bool	CGAL_collinear_are_ordered_along_line ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<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_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r)
		returns true, iff q lies strictly between p and r. Precondition: p, q and r are collinear.

The Insphere Test

CGAL_Bounded_side	CGAL_side_of_bounded_sphere ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r, CGAL_Point_3<R> s, CGAL_Point_3<R> test)
		returns the relative position of point test to the sphere defined by $p$, $q$, $r$, and $s$. The order of the points $p$, $q$, $r$, and $s$ does not matter. Precondition: p, q, r and s are not coplanar.
CGAL_Oriented_side	CGAL_side_of_oriented_sphere ( CGAL_Point_3<R> p, CGAL_Point_3<R> q, CGAL_Point_3<R> r, CGAL_Point_3<R> s, CGAL_Point_3<R> test)
		returns the relative position of point test to the oriented sphere defined by $p$, $q$, $r$ and $s$. The order of the points $p$, $q$, $r$, and $s$ is important, since it determines the orientation of the implicitly constructed sphere. If the points $p$, $q$, $r$ and $s$ are positive oriented, positive side is the bounded interior of the sphere. Precondition: p, q, r and s are not coplanar.

Comparison of Coordinates of Points

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

#include <CGAL/predicates_on_points_3.h>

bool	CGAL_x_equal ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
		returns true, iff p and q have the same x-coordinate.
bool	CGAL_y_equal ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
		returns true, iff p and q have the same y-coordinate.
bool	CGAL_z_equal ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
		returns true, iff p and q have the same z-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_3<R> p, CGAL_Point_3<R> q)
CGAL_Comparison_result
	CGAL_compare_y ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
CGAL_Comparison_result
	CGAL_compare_z ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)

For lexicographical comparison CGAL provides

CGAL_Comparison_result
	CGAL_compare_lexicographically_xyz ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
		Compares the Cartesian coordinates of points p and q lexicographically in $xyz$ order: first $x$-coordinates are compared, if they are equal, $y$-coordinates are compared, and if both $x$- and $y$- coordinate are equal, $z$-coordinates are compared.

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

bool	CGAL_lexicographically_xyz_smaller_or_equal ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)
bool	CGAL_lexicographically_xyz_smaller ( CGAL_Point_3<R> p, CGAL_Point_3<R> q)