PCK (Predicate Construction Kit) implements a set of geometric predicates. PCK uses arithmetic filters (Meyer and Pion), expansion arithmetics (Shewchuk) and simulation of simplicity (Edelsbrunner). More...

Classes
class	PredicateStats
	Logs statistics for predicates. The statistics are displayed on exit if the command line flag "sys:statistics" is set. It is used as follows in a predicate: More...

Enumerations
enum	SOSMode { SOS_ADDRESS , SOS_LEXICO }
	Mode for symbolic perturbations.

Functions
Sign	orient_2d (const vec2HE &p0, const vec2HE &p1, const vec2HE &p2)
	Computes the orientation predicate in 2d. More...

Sign	orient_2d_projected (const vec3HE &p0, const vec3HE &p1, const vec3HE &p2, coord_index_t axis)
	Computes the orientation predicate in 2d projected along an axis. More...

Sign	orient_3d (const vec3HE &p0, const vec3HE &p1, const vec3HE &p2, const vec3HE &p3)
	Computes the orientation predicate in 3d. More...

Sign	dot_2d (const vec2HE &p0, const vec2HE &p1, const vec2HE &p2)
	Computes the sign of the dot product between two vectors defined by three points. More...

Sign	incircle_2d_SOS_with_lengths (const vec2HE &p0, const vec2HE &p1, const vec2HE &p2, const vec2HE &p3, double l0, double l1, double l2, double l3)
	Tests whether a point is in the circumscribed circle of three other points. More...

Sign	incircle_2d_SOS (const vec2HE &p0, const vec2HE &p1, const vec2HE &p2, const vec2HE &p3)
	Tests whether a point is in the circumscribed circle of three other points. More...

coord_index_t	triangle_normal_axis (const vec3 &p1, const vec3 &p2, const vec3 &p3)
	Gets the axis that is most normal to a triangle. More...

bool	aligned_3d (const vec3HE &p0, const vec3HE &p1, const vec3HE &p2)
	Tests whether three 3d points are aligned. More...

bool	on_segment_3d (const vec3HE &p, const vec3HE &q1, const vec3HE &q2)
	Tests whether a point is on a segment. More...

vec3	approximate (const vec3HE &p)
	Gets a 3D floating-point approximation of a 3D point with exact coordinates. More...

vec2	approximate (const vec2HE &p)
	Gets a 2D floating-point approximation of a 2D point with exact coordinates. More...

template<class POINT , class COMPARE , class FUNC1 , class FUNC2 , class FUNC3 , class FUNC4 >
Sign	SOS (COMPARE compare, const POINT &p1, FUNC1 sos_p1, const POINT &p2, FUNC2 sos_p2, const POINT &p3, FUNC3 sos_p3, const POINT &p4, FUNC4 sos_p4)
	template for writing symbolic perturbation in predicates More...

void	set_SOS_mode (SOSMode m)
	Sets the current mode for handling symbolic perturbations (SOS for Simulation Of Simplicity). More...

SOSMode	get_SOS_mode ()
	Gets the current mode for handling symbolic perturbations. More...

Sign	side1_SOS (const double p0, const double p1, const double *q0, coord_index_t DIM)
	Computes the side of a point (given directly) relative to a bisector. More...

Sign	side2_SOS (const double p0, const double p1, const double p2, const double q0, const double *q1, coord_index_t DIM)
	Computes the side of a point (given as the intersection between a segment and a bisector) relative to another bisector. More...

Sign	side3_SOS (const double p0, const double p1, const double p2, const double p3, const double q0, const double q1, const double *q2, coord_index_t DIM)
	Computes the side of a point (given as the intersection between a facet and two bisectors) relative to another bisector. More...

Sign	side3_3dlifted_SOS (const double p0, const double p1, const double p2, const double p3, double h0, double h1, double h2, double h3, const double q0, const double q1, const double *q2, bool SOS=true)
	Computes the side of a point (given as the intersection between a facet and two bisectors) relative to another bisector. More...

Sign	side4_SOS (const double p0, const double p1, const double p2, const double p3, const double p4, const double q0, const double q1, const double q2, const double *q3, coord_index_t DIM)
	Computes the side of a point (given as the intersection between a tetrahedron and three bisectors) relative to another bisector. More...

Sign	side4_3d (const double p0, const double p1, const double p2, const double p3, const double *p4)
	Computes the side of a point (given as the intersection between three bisectors) relative to another bisector. More...

Sign	side4_3d_SOS (const double p0, const double p1, const double p2, const double p3, const double *p4)
	Computes the side of a point (given as the intersection between three bisectors) relative to another bisector. More...

Sign	in_sphere_3d_SOS (const double p0, const double p1, const double p2, const double p3, const double *p4)
	Tests whether a 3d point is inside the circumscribed sphere of a 3d tetrahedron. More...

Sign	in_circle_2d_SOS (const double p0, const double p1, const double p2, const double p3)
	Tests whether a 2d point is inside the circumscribed circle of a 3d triangle. More...

Sign	in_circle_3d_SOS (const double p0, const double p1, const double p2, const double p3)
	Tests whether a 3d point is inside the circumscribed circle of a 3d triangle. More...

Sign	in_circle_3dlifted_SOS (const double p0, const double p1, const double p2, const double p3, double h0, double h1, double h2, double h3, bool SOS=true)
	Tests whether a lifted 3d point is inside the circumscribed circle of a lifted 3d triangle. More...

Sign	orient_2d (const double p0, const double p1, const double *p2)
	Computes the orientation predicate in 2d. More...

Sign	orient_2d (const vec2 &p0, const vec2 &p1, const vec2 &p2)
	Computes the orientation predicate in 2d. More...

Sign	orient_2dlifted_SOS (const double p0, const double p1, const double p2, const double p3, double h0, double h1, double h2, double h3)
	Computes the 3d orientation test with lifted points. More...

Sign	orient_3d (const double p0, const double p1, const double p2, const double p3)
	Computes the orientation predicate in 3d. More...

Sign	orient_3d (const vec3 &p0, const vec3 &p1, const vec3 &p2, const vec3 &p3)
	Computes the orientation predicate in 3d. More...

Sign	orient_3dlifted (const double p0, const double p1, const double p2, const double p3, const double *p4, double h0, double h1, double h2, double h3, double h4)
	Computes the 4d orientation test. More...

Sign	orient_3dlifted_SOS (const double p0, const double p1, const double p2, const double p3, const double *p4, double h0, double h1, double h2, double h3, double h4)
	Computes the 4d orientation test with symbolic perturbation. More...

Sign	det_3d (const double p0, const double p1, const double *p2)
	Computes the sign of the determinant of a 3x3 matrix formed by three 3d points. More...

Sign	det_3d (const vec3 &p0, const vec3 &p1, const vec3 &p2)
	Computes the sign of the determinant of a 3x3 matrix formed by three 3d points. More...

Sign	det_4d (const double p0, const double p1, const double p2, const double p3)
	Computes the sign of the determinant of a 4x4 matrix formed by four 4d points. More...

Sign	det_4d (const vec4 &p0, const vec4 &p1, const vec4 &p2, const vec4 &p3)
	Computes the sign of the determinant of a 4x4 matrix formed by four 4d points. More...

Sign	det_compare_4d (const double p0, const double p1, const double p2, const double p3, const double *p4)
	Computes the sign of the determinant of a 4x4 matrix formed by three 4d points and the difference of two 4d points. More...

bool	aligned_3d (const double p0, const double p1, const double *p2)
	Tests whether three points are aligned. More...

Sign	dot_3d (const double p0, const double p1, const double *p2)
	Computes the sign of the dot product between two vectors. More...

bool	aligned_3d (const vec3 &p0, const vec3 &p1, const vec3 &p2)
	Tests whether three points are aligned. More...

Sign	dot_3d (const vec3 &p0, const vec3 &p1, const vec3 &p2)
	Computes the sign of the dot product between two vectors. More...

Sign	dot_compare_3d (const double v0, const double v1, const double *v2)
	Compares two dot products. More...

bool	points_are_identical_2d (const double p1, const double p2)
	Tests whether two 2d points are identical. More...

bool	points_are_identical_3d (const double p1, const double p2)
	Tests whether two 3d points are identical. More...

bool	points_are_colinear_3d (const double p1, const double p2, const double *p3)
	Tests whether three 3d points are colinear. More...

Sign	orient_3d_inexact (const double p0, const double p1, const double p2, const double p3)
	Computes the (approximate) orientation predicate in 3d. More...

void	show_stats ()
	Displays some statistics about predicates, including the number of calls, the number of exact arithmetics calls, and the number of Simulation of Simplicity calls.

void	initialize ()
	Needs to be called before using any predicate.

void	terminate ()
	Needs to be called at the end of the program.

Detailed Description

PCK (Predicate Construction Kit) implements a set of geometric predicates. PCK uses arithmetic filters (Meyer and Pion), expansion arithmetics (Shewchuk) and simulation of simplicity (Edelsbrunner).

Function Documentation

◆ aligned_3d() [1/3]

bool GEO::PCK::aligned_3d	(	const double *	p0,
		const double *	p1,
		const double *	p2
	)

Tests whether three points are aligned.

Parameters

[in] p0,p1,p2 the three points

Return values

true	if the three points are aligned.
false	otherwise.

Function to be tested, use points_are_colinear_3d() instead.

◆ aligned_3d() [2/3]

bool GEO::PCK::aligned_3d	(	const vec3 &	p0,
		const vec3 &	p1,
		const vec3 &	p2
	)

inline

Tests whether three points are aligned.

Parameters

[in] p0,p1,p2 the three points

Return values

true	if the three points are aligned.
false	otherwise.

Function to be tested, use points_are_colinear_3d() instead.

Definition at line 628 of file predicates.h.

◆ aligned_3d() [3/3]

bool GEO::PCK::aligned_3d	(	const vec3HE &	p0,
		const vec3HE &	p1,
		const vec3HE &	p2
	)

Tests whether three 3d points are aligned.

Parameters

[in] p0,p1,p2 the three points, in homogeneous coordinates, represented in exact form.

Return values

true	if the three points are aligned (or if two of them or more are identical)
false	otherwise

◆ approximate() [1/2]

vec2 GEO::PCK::approximate ( const vec2HE & p )

Gets a 2D floating-point approximation of a 2D point with exact coordinates.

Parameters

[in] p a const reference to the point with homogeneous exact coordinates as expansion_nt

Returns: a floating-point approximation of p

◆ approximate() [2/2]

vec3 GEO::PCK::approximate ( const vec3HE & p )

Gets a 3D floating-point approximation of a 3D point with exact coordinates.

Parameters

[in] p a const reference to the point with homogeneous exact coordinates as expansion_nt

Returns: a floating-point approximation of p

◆ det_3d() [1/2]

Sign GEO::PCK::det_3d	(	const double *	p0,
		const double *	p1,
		const double *	p2
	)

Computes the sign of the determinant of a 3x3 matrix formed by three 3d points.

Parameters

[in] p0,p1,p2 the three points

Returns: the sign of the determinant of the matrix.

◆ det_3d() [2/2]

Sign GEO::PCK::det_3d	(	const vec3 &	p0,
		const vec3 &	p1,
		const vec3 &	p2
	)

inline

Computes the sign of the determinant of a 3x3 matrix formed by three 3d points.

Parameters

[in] p0,p1,p2 the three points

Returns: the sign of the determinant of the matrix.

Definition at line 548 of file predicates.h.

◆ det_4d() [1/2]

Sign GEO::PCK::det_4d	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3
	)

Computes the sign of the determinant of a 4x4 matrix formed by four 4d points.

Parameters

[in] p0,p1,p2,p3 the four points

Returns: the sign of the determinant of the matrix.

◆ det_4d() [2/2]

Sign GEO::PCK::det_4d	(	const vec4 &	p0,
		const vec4 &	p1,
		const vec4 &	p2,
		const vec4 &	p3
	)

inline

Computes the sign of the determinant of a 4x4 matrix formed by four 4d points.

Parameters

[in] p0,p1,p2,p3 the four points

Returns: the sign of the determinant of the matrix.

Definition at line 573 of file predicates.h.

◆ det_compare_4d()

Sign GEO::PCK::det_compare_4d	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4
	)

Computes the sign of the determinant of a 4x4 matrix formed by three 4d points and the difference of two 4d points.

Parameters

[in] p0,p1,p2,p3,p4 the four points

Returns: the sign of the determinant of the matrix p0 p1 p2 p4-p3

◆ dot_2d()

Sign GEO::PCK::dot_2d	(	const vec2HE &	p0,
		const vec2HE &	p1,
		const vec2HE &	p2
	)

Computes the sign of the dot product between two vectors defined by three points.

Parameters

[in] p0,p1,p2 the three points as 2d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).

Returns: the sign of(p1-p0)*(p2-p0)

◆ dot_3d() [1/2]

Sign GEO::PCK::dot_3d	(	const double *	p0,
		const double *	p1,
		const double *	p2
	)

Computes the sign of the dot product between two vectors.

Parameters

[in] p0,p1,p2 three 3d points.

Returns: the sign of the dot product between the vectors p0p1 and p0p2.

◆ dot_3d() [2/2]

Sign GEO::PCK::dot_3d	(	const vec3 &	p0,
		const vec3 &	p1,
		const vec3 &	p2
	)

inline

Computes the sign of the dot product between two vectors.

Parameters

[in] p0,p1,p2 three 3d points.

Returns: the sign of the dot product between the vectors p0p1 and p0p2.

Definition at line 641 of file predicates.h.

◆ dot_compare_3d()

Sign GEO::PCK::dot_compare_3d	(	const double *	v0,
		const double *	v1,
		const double *	v2
	)

Compares two dot products.

Parameters

[in] v0,v1,v2 three vectors.

Returns: the sign of v0.v1 - v0.v2

◆ get_SOS_mode()

SOSMode GEO::PCK::get_SOS_mode ( )

Gets the current mode for handling symbolic perturbations.

Returns: one of SOS_ADDRESS, SOS_LEXICO

See also: set_SOS_mode()

◆ in_circle_2d_SOS()

Sign GEO::PCK::in_circle_2d_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3
	)

Tests whether a 2d point is inside the circumscribed circle of a 3d triangle.

Parameters

[in]	p0,p1,p2	vertices of the triangle
[in]	p3	the point to be tested

Return values

POSITIVE	whenever `p3` is inside the circumscribed circle of the triangle `p0`, `p1`, `p2`
NEGATIVE	whenever `p2` is outside the circumscribed circle of the triangle `p0`, `p1`, `p2`
perturb()	if `p3` is exactly on the circumscribed circle of the triangle `p0`, `p1`, `p2`, where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Precondition: p3 belongs to the plane yielded by p0, p1 and p2

◆ in_circle_3d_SOS()

Sign GEO::PCK::in_circle_3d_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3
	)

Tests whether a 3d point is inside the circumscribed circle of a 3d triangle.

Parameters

[in]	p0,p1,p2	vertices of the triangle
[in]	p3	the point to be tested

Return values

POSITIVE	whenever `p3` is inside the circumscribed circle of the triangle `p0`, `p1`, `p2`
NEGATIVE	whenever `p2` is outside the circumscribed circle of the triangle `p0`, `p1`, `p2`
perturb()	if `p3` is exactly on the circumscribed circle of the triangle `p0`, `p1`, `p2`, where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Precondition: p3 belongs to the plane yielded by p0, p1 and p2

◆ in_circle_3dlifted_SOS()

Sign GEO::PCK::in_circle_3dlifted_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		double	h0,
		double	h1,
		double	h2,
		double	h3,
		bool	SOS = `true`
	)

Tests whether a lifted 3d point is inside the circumscribed circle of a lifted 3d triangle.

Parameters

[in]	p0,p1,p2	vertices of the triangle
[in]	p3	the point to be tested
[in]	h0,h1,h2	lifted coordinate of the triangle vertices
[in]	h3	lifted coordinate of the point to be tested
[in]	SOS	if true, do the symbolic perturbation in the degenerate cases

Return values

POSITIVE	whenever (`p3`, `h3`) is inside the circumscribed circle of the triangle (`p0`,`h0`) (`p1`,`h1`), (`p2`, `h2`)
NEGATIVE	whenever (`p3`, `h3`) is outside the circumscribed circle of the triangle (`p0`,`h0`) (`p1`,`h1`), (`p2`, `h2`)
perturb()	if (`p3`, `h3`) is exactly on the circumscribed circle of the triangle (`p0`,`h0`) (`p1`,`h1`), (`p2`, `h2`) where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Precondition: (p3, h3) belongs to the hyperplane yielded by (p0, h0), (p1, h1) and (p2, h2)

◆ in_sphere_3d_SOS()

Sign GEO::PCK::in_sphere_3d_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4
	)

Tests whether a 3d point is inside the circumscribed sphere of a 3d tetrahedron.

Parameters

[in]	p0,p1,p2,p3	the four vertices of the tetrahedron
[in]	p4	the point

Return values

POSITIVE	whenever `p4` is inside the circumscribed sphere of the tetrahedron `p0`, `p1`, `p2`, `p3`
NEGATIVE	whenever `p4` is outside the circumscribed sphere of the tetrahedron `p0`, `p1`, `p2`, `p3`
perturb()	if `p4` is exactly on the circumscribed sphere of the tetrahedron `p0`, `p1`, `p2`, `p3`, where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Precondition: orient_3d(p0,p1,p2,p3) > 0

◆ incircle_2d_SOS()

Sign GEO::PCK::incircle_2d_SOS	(	const vec2HE &	p0,
		const vec2HE &	p1,
		const vec2HE &	p2,
		const vec2HE &	p3
	)

inline

Tests whether a point is in the circumscribed circle of three other points.

If the triangle p0 , p1 , p2 is oriented clockwise instead of counter-clockwise, then the result is inversed. One can use instead the incircle_2d_SOS_with_lengths() that is faster and that uses cached lengths.

See also: incircle_2d_SOS_with_lengths()

Parameters

[in] p0,p1,p2,p3 the four points, in homogeneous coordinates,represented in exact form.

Return values

POSITIVE	if p3 is inside the circumscribed circle of p0, p1, p2
NEGATIVE	if p3 is outside the circumscribed circle of p0, p1, p2
a	coherent perturbation otherwise

Definition at line 314 of file exact_geometry.h.

◆ incircle_2d_SOS_with_lengths()

Sign GEO::PCK::incircle_2d_SOS_with_lengths	(	const vec2HE &	p0,
		const vec2HE &	p1,
		const vec2HE &	p2,
		const vec2HE &	p3,
		double	l0,
		double	l1,
		double	l2,
		double	l3
	)

Tests whether a point is in the circumscribed circle of three other points.

If the triangle p0 , p1 , p2 is oriented clockwise instead of counter-clockwise, then the result is inversed.

Parameters

[in]	p0,p1,p2,p3	the four points, in homogeneous coordinates,represented in exact form.
[in]	l0,l1,l2,l3	the four approximated pre-computed lengths li = (xi^2 + yi^2) / wi^2 as double coordinates

Return values

POSITIVE	if p3 is inside the circumscribed circle of p0, p1, p2
NEGATIVE	if p3 is outside the circumscribed circle of p0, p1, p2
a	coherent perturbation otherwise

◆ on_segment_3d()

bool GEO::PCK::on_segment_3d	(	const vec3HE &	p,
		const vec3HE &	q1,
		const vec3HE &	q2
	)

Tests whether a point is on a segment.

Parameters

[in]	p	the point in homogeneous coordinates, in exact form
[in]	q1,q2	the two extremities of the segment in homogeneous coordinates, in exact form

Return values

true	if `p` is on the segment `q1` , `q2`
false	otherwise

◆ orient_2d() [1/3]

Sign GEO::PCK::orient_2d	(	const double *	p0,
		const double *	p1,
		const double *	p2
	)

Computes the orientation predicate in 2d.

Computes the sign of the signed area of the triangle p0, p1, p2.

Parameters

[in] p0,p1,p2 vertices of the triangle

Return values

POSITIVE	if the triangle is oriented counter-clockwise
ZERO	if the triangle is flat
NEGATIVE	if the triangle is oriented clockwise

◆ orient_2d() [2/3]

Sign GEO::PCK::orient_2d	(	const vec2 &	p0,
		const vec2 &	p1,
		const vec2 &	p2
	)

inline

Computes the orientation predicate in 2d.

Computes the sign of the signed area of the triangle p0, p1, p2.

Parameters

[in] p0,p1,p2 vertices of the triangle

Return values

POSITIVE	if the triangle is oriented counter-clockwise
ZERO	if the triangle is flat
NEGATIVE	if the triangle is oriented clockwise

Definition at line 416 of file predicates.h.

◆ orient_2d() [3/3]

Sign GEO::PCK::orient_2d	(	const vec2HE &	p0,
		const vec2HE &	p1,
		const vec2HE &	p2
	)

Computes the orientation predicate in 2d.

Computes the sign of the signed area of the triangle p0, p1, p2.

Parameters

[in] p0,p1,p2 vertices of the triangle as 2d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).

Return values

POSITIVE	if the triangle is oriented counter-clockwise
ZERO	if the triangle is flat
NEGATIVE	if the triangle is oriented clockwise

◆ orient_2d_projected()

Sign GEO::PCK::orient_2d_projected	(	const vec3HE &	p0,
		const vec3HE &	p1,
		const vec3HE &	p2,
		coord_index_t	axis
	)

Computes the orientation predicate in 2d projected along an axis.

Computes the sign of the signed area of the triangle p0, p1, p2 projected onto a given axis. The used coordinates are (axis + 1) modulo 3 and (axis + 2) modulo 3.

Parameters

[in] p0,p1,p2 vertices of the triangle as 3d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).

Return values

POSITIVE	if the projected triangle is oriented counter-clockwise
ZERO	if the projected triangle is flat
NEGATIVE	if the projected triangle is oriented clockwise

◆ orient_2dlifted_SOS()

Sign GEO::PCK::orient_2dlifted_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		double	h0,
		double	h1,
		double	h2,
		double	h3
	)

Computes the 3d orientation test with lifted points.

Given three lifted points p0', p1', p2' in R^2, tests if the lifted point p3' in R^3 lies below or above the plane passing through the three points p0', p1', p2'. The first two coordinates and the third one are specified in separate arguments for each vertex.

Parameters

[in]	p0,p1,p2,p3	first 2 coordinates of the vertices of the 3-simplex
[in]	h0,h1,h2,h3	heights of the vertices of the 3-simplex

Return values

POSITIVE	if p3' lies below the plane
NEGATIVE	if p3' lies above the plane
perturb()	if p3' lies exactly on the hyperplane where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

◆ orient_3d() [1/3]

Sign GEO::PCK::orient_3d	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3
	)

Computes the orientation predicate in 3d.

Computes the sign of the signed volume of the tetrahedron p0, p1, p2, p3.

Parameters

[in] p0,p1,p2,p3 vertices of the tetrahedron

Return values

POSITIVE	if the tetrahedron is oriented positively
ZERO	if the tetrahedron is flat
NEGATIVE	if the tetrahedron is oriented negatively

◆ orient_3d() [2/3]

Sign GEO::PCK::orient_3d	(	const vec3 &	p0,
		const vec3 &	p1,
		const vec3 &	p2,
		const vec3 &	p3
	)

inline

Computes the orientation predicate in 3d.

Computes the sign of the signed volume of the tetrahedron p0, p1, p2, p3.

Parameters

[in] p0,p1,p2,p3 vertices of the tetrahedron

Return values

POSITIVE	if the tetrahedron is oriented positively
ZERO	if the tetrahedron is flat
NEGATIVE	if the tetrahedron is oriented negatively

Definition at line 473 of file predicates.h.

◆ orient_3d() [3/3]

Sign GEO::PCK::orient_3d	(	const vec3HE &	p0,
		const vec3HE &	p1,
		const vec3HE &	p2,
		const vec3HE &	p3
	)

Computes the orientation predicate in 3d.

Computes the sign of the signed volume of the tetrahedron p0, p1, p2, p3.

Parameters

[in] p0,p1,p2,p3 vertices of the tetrahedron as 3d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).

Return values

POSITIVE	if the tetrahedron is oriented positively
ZERO	if the tetrahedron is flat
NEGATIVE	if the tetrahedron is oriented negatively

◆ orient_3d_inexact()

Sign GEO::PCK::orient_3d_inexact	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3
	)

inline

Computes the (approximate) orientation predicate in 3d.

Computes the sign of the (approximate) signed volume of the tetrahedron p0, p1, p2, p3.

Parameters

[in]	p0	first vertex of the tetrahedron
[in]	p1	second vertex of the tetrahedron
[in]	p2	third vertex of the tetrahedron
[in]	p3	fourth vertex of the tetrahedron

Return values

POSITIVE	if the tetrahedron is oriented positively
ZERO	if the tetrahedron is flat
NEGATIVE	if the tetrahedron is oriented negatively

Definition at line 709 of file predicates.h.

◆ orient_3dlifted()

Sign GEO::PCK::orient_3dlifted	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4,
		double	h0,
		double	h1,
		double	h2,
		double	h3,
		double	h4
	)

Computes the 4d orientation test.

Given four lifted points p0', p1', p2', and p3' in R^4, tests if the lifted point p4' in R^4 lies below or above the hyperplance passing through the four points p0', p1', p2', and p3'. This version does not apply symbolic perturbation. The first three coordinates and the fourth one are specified in separate arguments for each vertex.

Parameters

[in]	p0,p1,p2,p3,p4	first 3 coordinates of the vertices of the 4-simplex
[in]	h0,h1,h2,h3,h4	heights of the vertices of the 4-simplex

Return values

POSITIVE	if p4' lies below the hyperplane
NEGATIVE	if p4' lies above the hyperplane
ZERO	if p4' lies exactly on the hyperplane

◆ orient_3dlifted_SOS()

Sign GEO::PCK::orient_3dlifted_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4,
		double	h0,
		double	h1,
		double	h2,
		double	h3,
		double	h4
	)

Computes the 4d orientation test with symbolic perturbation.

Given four lifted points p0', p1', p2', and p3' in R^4, tests if the lifted point p4' in R^4 lies below or above the hyperplance passing through the four points p0', p1', p2', and p3'. Symbolic perturbation is applied whenever the 5 vertices are not linearly independent. The first three coordinates and the fourth one are specified in separate arguments for each vertex.

Parameters

[in]	p0,p1,p2,p3,p4	first 3 coordinates of the vertices of the 4-simplex
[in]	h0,h1,h2,h3,h4	heights of the vertices of the 4-simplex

Return values

POSITIVE	if p4' lies below the hyperplane
NEGATIVE	if p4' lies above the hyperplane
perturb()	if p4' lies exactly on the hyperplane where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

◆ points_are_colinear_3d()

bool GEO::PCK::points_are_colinear_3d	(	const double *	p1,
		const double *	p2,
		const double *	p3
	)

Tests whether three 3d points are colinear.

Parameters

[in]	p1	first point
[in]	p2	second point
[in]	p3	third point

Return values

true	if `p1`, `p2` and `p3` are colinear \retbal false otherwise

◆ points_are_identical_2d()

bool GEO::PCK::points_are_identical_2d	(	const double *	p1,
		const double *	p2
	)

Tests whether two 2d points are identical.

Parameters

[in]	p1	first point
[in]	p2	second point

Return values

true	if `p1` and `p2` have exactly the same coordinates
false	otherwise

◆ points_are_identical_3d()

bool GEO::PCK::points_are_identical_3d	(	const double *	p1,
		const double *	p2
	)

Tests whether two 3d points are identical.

Parameters

[in]	p1	first point
[in]	p2	second point

Return values

true	if `p1` and `p2` have exactly the same coordinates
false	otherwise

◆ set_SOS_mode()

void GEO::PCK::set_SOS_mode ( SOSMode m )

Sets the current mode for handling symbolic perturbations (SOS for Simulation Of Simplicity).

Parameters

[in] m one of SOS_ADDRESS, SOS_LEXICO

If SOS_ADDRESS mode is used, then points are supposed to be allocated in a fixed array, and the same point always designated by the same address. If SOS_LEXICO is used then points are sorted in lexicographic order for computing the symbolic perturbation. SOS_LEXICO works for points that are generated dynamically (with no fixed address).

◆ side1_SOS()

Sign GEO::PCK::side1_SOS	(	const double *	p0,
		const double *	p1,
		const double *	q0,
		coord_index_t	DIM
	)

Computes the side of a point (given directly) relative to a bisector.

Computes the side of \( q0 \) relative to \( \Pi(p0,p1) \). Symbolic perturbation is applied whenever equality holds.

Parameters

[in]	p0,p1	extremities of the bisector
[in]	q0	point to be tested
[in]	DIM	number of coordinates of the point

Return values

POSITIVE	if d(p0,q0) < d(p1,q0)
NEGATIVE	if d(p0,q0) > d(p1,q1)
perturb()	if f(p0,q0) = d(p1,q1), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Note: Only some specific dimensions are implemented (3,4,6 and 7)

◆ side2_SOS()

Sign GEO::PCK::side2_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	q0,
		const double *	q1,
		coord_index_t	DIM
	)

Computes the side of a point (given as the intersection between a segment and a bisector) relative to another bisector.

Computes the side of \( q = \Pi(p0,p1) \cap [q0,q1] \) relative to \( \Pi(p0,p2) \). Symbolic perturbation is applied whenever equality holds.

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (against which orientation is tested)
[in]	q0,q1	extremities of the segment (that defines the intersection q)

Return values

POSITIVE	if d(p0,q) < d(p2,q)
NEGATIVE	if d(p0,q) > d(p2,q)
perturb()	if d(p0,q) = d(p2,q), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Note: Only some specific dimensions are implemented (3,4,6 and 7)

◆ side3_3dlifted_SOS()

Sign GEO::PCK::side3_3dlifted_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		double	h0,
		double	h1,
		double	h2,
		double	h3,
		const double *	q0,
		const double *	q1,
		const double *	q2,
		bool	SOS = `true`
	)

Computes the side of a point (given as the intersection between a facet and two bisectors) relative to another bisector.

Computes the side of \( q = \Pi(p0 h0,p1 h1) \cap Pi(p0 h0,p2 h2) \cap \Delta[q0, q1, q2] \) relative to \( \Pi(p0 hp0,p3 hp3) \). Symbolic perturbation is applied whenever equality holds.

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (that defines the intersection q)
[in]	p3	second extremity of the third bisector (against which orientation is tested)
	h0,h1,h2,h3	lifted coordinates of `p0`, `p1`, `p2` and `p3`
[in]	q0,q1,q2	vertices of the triangle (that defines the intersection q)
[in]	SOS	if true, do the symbolic perturbation in the degenerate case

Return values

POSITIVE	if d(p0 hp0,q) < d(p3 hp3, q)
NEGATIVE	if d(p0 hp0,q) > d(p3 hp3, q)
perturb()	if d(p0 hp0,q) = d(p3 hp3, q), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

◆ side3_SOS()

Sign GEO::PCK::side3_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	q0,
		const double *	q1,
		const double *	q2,
		coord_index_t	DIM
	)

Computes the side of a point (given as the intersection between a facet and two bisectors) relative to another bisector.

Computes the side of \( q = \Pi(p0,p1) \cap Pi(p0,p2) \cap \Delta[q0,q1,q2] \) relative to \( \Pi(p0,p3) \). Symbolic perturbation is applied whenever equality holds.

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (that defines the intersection q)
[in]	p3	second extremity of the third bisector (against which orientation is tested)
[in]	q0,q1,q2	vertices of the triangle (that defines the intersection q)

Return values

POSITIVE	if d(p0,q) < d(p3,q)
NEGATIVE	if d(p0,q) > d(p3,q)
perturb()	if d(p0,q) = d(p3,q), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Note: Only some specific dimensions are implemented (3,4,6 and 7)

◆ side4_3d()

Sign GEO::PCK::side4_3d	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4
	)

Computes the side of a point (given as the intersection between three bisectors) relative to another bisector.

Computes the side of \( q = \Pi(p0,p1) \cap \Pi(p0,p2) \cap \Pi(p0,p3) \) relative to \( Pi(p0,p4) \). This version does not apply symbolic perturbation when equality holds. side4_3d() is a special case of side4(), where the ambient and intrinsic dimensions coincide (therefore no embedding tetrahedron is needed).

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (that defines the intersection q)
[in]	p3	second extremity of the third bisector (that defines the intersection q)
[in]	p4	second extremity of the fourth bisector (against which orientation is tested)

Return values

POSITIVE	if d(p0,q) < d(p4,q)
NEGATIVE	if d(p0,q) > d(p4,q)
ZERO	if d(p0,q) = d(p4,q),

◆ side4_3d_SOS()

Sign GEO::PCK::side4_3d_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4
	)

Computes the side of a point (given as the intersection between three bisectors) relative to another bisector.

Computes the side of \( q = \Pi(p0,p1) \cap \Pi(p0,p2) \cap \Pi(p0,p3) \) relative to \( Pi(p0,p4) \). Symbolic perturbation is applied whenever equality holds. side4_3d() is a special case of side4(), where the ambient and intrinsic dimensions coincide (therefore no embedding tetrahedron is needed).

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (that defines the intersection q)
[in]	p3	second extremity of the third bisector (that defines the intersection q)
[in]	p4	second extremity of the fourth bisector (against which orientation is tested)

Return values

POSITIVE	if d(p0,q) < d(p4,q)
NEGATIVE	if d(p0,q) > d(p4,q)
perturb()	if d(p0,q) = d(p4,q), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

◆ side4_SOS()

Sign GEO::PCK::side4_SOS	(	const double *	p0,
		const double *	p1,
		const double *	p2,
		const double *	p3,
		const double *	p4,
		const double *	q0,
		const double *	q1,
		const double *	q2,
		const double *	q3,
		coord_index_t	DIM
	)

Computes the side of a point (given as the intersection between a tetrahedron and three bisectors) relative to another bisector.

Computes the side of \( q = \Pi(p0,p1) \cap Pi(p0,p2) \cap Pi(p0,p3) \cap \Delta[q0,q1,q2,q3] \) relative to \( \Pi(p0,p4) \). Symbolic perturbation is applied whenever equality holds.

Parameters

[in]	p0	first extremity of the bisectors
[in]	p1	second extremity of the first bisector (that defines the intersection q)
[in]	p2	second extremity of the second bisector (that defines the intersection q)
[in]	p3	second extremity of the third bisector (that defines the intersection q)
[in]	p4	second extremity of the fourth bisector (against which orientation is tested)
[in]	q0,q1,q2,q3	vertices of the tetrahedron (that defines the intersection q) (that defines the intersection q)

Return values

POSITIVE	if d(p0,q) < d(p4,q)
NEGATIVE	if d(p0,q) > d(p4,q)
perturb()	if d(p0,q) = d(p4,q), where `perturb()` denotes a globally consistent perturbation, that returns either POSITIVE or NEGATIVE

Note: Only some specific dimensions are implemented (3,4,6 and 7)

◆ SOS()

template<class POINT , class COMPARE , class FUNC1 , class FUNC2 , class FUNC3 , class FUNC4 >

Sign GEO::PCK::SOS	(	COMPARE	compare,
		const POINT &	p1,
		FUNC1	sos_p1,
		const POINT &	p2,
		FUNC2	sos_p2,
		const POINT &	p3,
		FUNC3	sos_p3,
		const POINT &	p4,
		FUNC4	sos_p4
	)

inline

template for writing symbolic perturbation in predicates

Parameters

[in]	compare	a comparator for sorting the points
[in]	p1,p2,p3,p4	the four points
[in]	sos_p1,sos_p2,sos_p3,sos_p4	the four lambdas that compute the symbolic perturbation associated with each point, and that return the sign of the perturbed predicate. There is a SOS_result() macro to help writing these lambdas.

How to use/example:

... beginning of predicate, filter did not hit and exact value
is zero ..
 
return SOS(
    vec2HgLexicoCompare<exact_nt>(),
       p0, SOS_result( det3_111_sign(p1,p2,p3)),
       p1, SOS_result(-det3_111_sign(p0,p2,p3)),
       p2, SOS_result( det3_111_sign(p0,p1,p3)),
       p3, SOS_result(-det3_111_sign(p0,p1,p2))
    );

Definition at line 172 of file PCK.h.

◆ triangle_normal_axis()

coord_index_t GEO::PCK::triangle_normal_axis	(	const vec3 &	p1,
		const vec3 &	p2,
		const vec3 &	p3
	)

Gets the axis that is most normal to a triangle.

Fires an assertion fail if triangle is degenerate (that is, with its three vertices exactly aligned).

Parameters

[in] p1,p2,p3 the three vertices of the triangle

Returns: the coordinate of the normal vector with the greatest absolute value

Classes

Enumerations

Functions

Detailed Description

Function Documentation

◆ aligned_3d() [1/3]

◆ aligned_3d() [2/3]

◆ aligned_3d() [3/3]

◆ approximate() [1/2]

◆ approximate() [2/2]

◆ det_3d() [1/2]

◆ det_3d() [2/2]

◆ det_4d() [1/2]

◆ det_4d() [2/2]

◆ det_compare_4d()

◆ dot_2d()

◆ dot_3d() [1/2]

◆ dot_3d() [2/2]

◆ dot_compare_3d()

◆ get_SOS_mode()

◆ in_circle_2d_SOS()

◆ in_circle_3d_SOS()

◆ in_circle_3dlifted_SOS()

◆ in_sphere_3d_SOS()

◆ incircle_2d_SOS()

◆ incircle_2d_SOS_with_lengths()

◆ on_segment_3d()

◆ orient_2d() [1/3]

◆ orient_2d() [2/3]

◆ orient_2d() [3/3]

◆ orient_2d_projected()

◆ orient_2dlifted_SOS()

◆ orient_3d() [1/3]

◆ orient_3d() [2/3]

◆ orient_3d() [3/3]

◆ orient_3d_inexact()

◆ orient_3dlifted()

◆ orient_3dlifted_SOS()

◆ points_are_colinear_3d()

◆ points_are_identical_2d()

◆ points_are_identical_3d()

◆ set_SOS_mode()

◆ side1_SOS()

◆ side2_SOS()

◆ side3_3dlifted_SOS()

◆ side3_SOS()

◆ side4_3d()

◆ side4_3d_SOS()

◆ side4_SOS()

◆ SOS()

◆ triangle_normal_axis()