3D Geometric Predicates

Order Type Predicates

#include <CGAL/predicates_on_points_3.h>

Orientation	orientation ( Point_3<R> p, Point_3<R> q, Point_3<R> r, Point_3<R> s)
		returns POSITIVE, if $$s lies on the positive side of the oriented plane $$h defined by $$p, $$q, and $$r, returns NEGATIVE if $$s lies on the negative side of $$h, and returns COPLANAR if $$s lies on $$h.
bool	coplanar ( Point_3<R> p, Point_3<R> q, Point_3<R> r, Point_3<R> s)
		returns true, if $$p, $$q, $$r, and $$s are coplanar.
bool	collinear ( Point_3<R> p, Point_3<R> q, 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	are_ordered_along_line ( Point_3<R> p, Point_3<R> q, 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	are_strictly_ordered_along_line ( Point_3<R> p, Point_3<R> q, 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	collinear_are_ordered_along_line ( Point_3<R> p, Point_3<R> q, Point_3<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_3<R> p, Point_3<R> q, Point_3<R> r)
		returns true, iff q lies strictly between p and r. Precondition: p, q and r are collinear.

Similarly, there is a test for the special cases of coplanarity. If we want to know the order of coplanar points with respect to the plane they define, this is the functions to call:

Orientation	coplanar_orientation ( Point_3<R> p, Point_3<R> q, Point_3<R> r, Point_3<R> s)
		Let $$P be the plane defined by the points p, q, and r. Note that the order defines the orientation of $$P. The function computes the orientation of points p, q, and s in $$P: Iff p, q, s are collinear, COLLINEAR is returned. Iff $$P and the plane defined by p, q, and s have the same orientation, POSITIVE is returned; otherwise NEGATIVE is returned. Precondition: p, q, r, and s are coplanar and p, q, and r are not collinear.

The Insphere Test

The following predicates the relative position of a point with respect to a sphere implicitly defined by four points.

#include <CGAL/predicates_on_points_3.h>

Bounded_side	side_of_bounded_sphere ( Point_3<R> p, Point_3<R> q, Point_3<R> r, Point_3<R> s, 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.
Oriented_side	side_of_oriented_sphere ( Point_3<R> p, Point_3<R> q, Point_3<R> r, Point_3<R> s, 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	x_equal ( Point_3<R> p, Point_3<R> q)
		returns true, iff p and q have the same x-coordinate.
bool	y_equal ( Point_3<R> p, Point_3<R> q)
		returns true, iff p and q have the same y-coordinate.
bool	z_equal ( Point_3<R> p, 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 Comparison_result.

Comparison_result	compare_x ( Point_3<R> p, Point_3<R> q)
Comparison_result	compare_y ( Point_3<R> p, Point_3<R> q)
Comparison_result	compare_z ( Point_3<R> p, Point_3<R> q)

For lexicographical comparison CGAL provides

Comparison_result	compare_lexicographically_xyz ( Point_3<R> p, 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 compare_lexicographically_xyz(p,q).

bool	lexicographically_xyz_smaller_or_equal ( Point_3<R> p, Point_3<R> q)
bool	lexicographically_xyz_smaller ( Point_3<R> p, Point_3<R> q)

See Also

Distance comparisons, Section .