Geogram  Version 1.9.1-rc
A programming library of geometric algorithms
GEO::PCK Namespace Reference

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_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_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,p2the three points
Return values
trueif the three points are aligned.
falseotherwise.

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,p2the three points
Return values
trueif the three points are aligned.
falseotherwise.

Function to be tested, use points_are_colinear_3d() instead.

Definition at line 599 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,p2the three points, in homogeneous coordinates, represented in exact form.
Return values
trueif the three points are aligned (or if two of them or more are identical)
falseotherwise

◆ 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]pa 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]pa const reference to the point with homogeneous exact coordinates as expansion_nt
Returns
a floating-point approximation of p

◆ det_3d()

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,p2the three points
Returns
the sign of the determinant of the matrix.

◆ det_4d()

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,p3the four points
Returns
the sign of the determinant of the matrix.

◆ 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,p4the 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,p2the 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,p2three 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,p2three 3d points.
Returns
the sign of the dot product between the vectors p0p1 and p0p2.

Definition at line 612 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,v2three 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,p2vertices of the triangle
[in]p3the point to be tested
Return values
POSITIVEwhenever p3 is inside the circumscribed circle of the triangle p0, p1, p2
NEGATIVEwhenever 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,p2vertices of the triangle
[in]p3the point to be tested
Return values
POSITIVEwhenever p3 is inside the circumscribed circle of the triangle p0, p1, p2
NEGATIVEwhenever 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,p2vertices of the triangle
[in]p3the point to be tested
[in]h0,h1,h2lifted coordinate of the triangle vertices
[in]h3lifted coordinate of the point to be tested
[in]SOSif true, do the symbolic perturbation in the degenerate cases
Return values
POSITIVEwhenever (p3, h3) is inside the circumscribed circle of the triangle (p0,h0) (p1,h1), (p2, h2)
NEGATIVEwhenever (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,p3the four vertices of the tetrahedron
[in]p4the point
Return values
POSITIVEwhenever p4 is inside the circumscribed sphere of the tetrahedron p0, p1, p2, p3
NEGATIVEwhenever 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,p3the four points, in homogeneous coordinates,represented in exact form.
Return values
POSITIVEif p3 is inside the circumscribed circle of p0, p1, p2
NEGATIVEif p3 is outside the circumscribed circle of p0, p1, p2
acoherent 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,p3the four points, in homogeneous coordinates,represented in exact form.
[in]l0,l1,l2,l3the four approximated pre-computed lengths li = (xi^2 + yi^2) / wi^2 as double coordinates
Return values
POSITIVEif p3 is inside the circumscribed circle of p0, p1, p2
NEGATIVEif p3 is outside the circumscribed circle of p0, p1, p2
acoherent 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]pthe point in homogeneous coordinates, in exact form
[in]q1,q2the two extremities of the segment in homogeneous coordinates, in exact form
Return values
trueif p is on the segment q1 , q2
falseotherwise

◆ 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,p2vertices of the triangle
Return values
POSITIVEif the triangle is oriented counter-clockwise
ZEROif the triangle is flat
NEGATIVEif 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,p2vertices of the triangle
Return values
POSITIVEif the triangle is oriented counter-clockwise
ZEROif the triangle is flat
NEGATIVEif 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,p2vertices of the triangle as 2d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).
Return values
POSITIVEif the triangle is oriented counter-clockwise
ZEROif the triangle is flat
NEGATIVEif 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,p2vertices of the triangle as 3d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).
Return values
POSITIVEif the projected triangle is oriented counter-clockwise
ZEROif the projected triangle is flat
NEGATIVEif 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,p3first 2 coordinates of the vertices of the 3-simplex
[in]h0,h1,h2,h3heights of the vertices of the 3-simplex
Return values
POSITIVEif p3' lies below the plane
NEGATIVEif 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,p3vertices of the tetrahedron
Return values
POSITIVEif the tetrahedron is oriented positively
ZEROif the tetrahedron is flat
NEGATIVEif 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,p3vertices of the tetrahedron
Return values
POSITIVEif the tetrahedron is oriented positively
ZEROif the tetrahedron is flat
NEGATIVEif 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,p3vertices of the tetrahedron as 3d vectors with homogeneous coordinates stored as expansion_nt (arbitrary precision).
Return values
POSITIVEif the tetrahedron is oriented positively
ZEROif the tetrahedron is flat
NEGATIVEif 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]p0first vertex of the tetrahedron
[in]p1second vertex of the tetrahedron
[in]p2third vertex of the tetrahedron
[in]p3fourth vertex of the tetrahedron
Return values
POSITIVEif the tetrahedron is oriented positively
ZEROif the tetrahedron is flat
NEGATIVEif the tetrahedron is oriented negatively

Definition at line 680 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,p4first 3 coordinates of the vertices of the 4-simplex
[in]h0,h1,h2,h3,h4heights of the vertices of the 4-simplex
Return values
POSITIVEif p4' lies below the hyperplane
NEGATIVEif p4' lies above the hyperplane
ZEROif 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,p4first 3 coordinates of the vertices of the 4-simplex
[in]h0,h1,h2,h3,h4heights of the vertices of the 4-simplex
Return values
POSITIVEif p4' lies below the hyperplane
NEGATIVEif 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]p1first point
[in]p2second point
[in]p3third point
Return values
trueif 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]p1first point
[in]p2second point
Return values
trueif p1 and p2 have exactly the same coordinates
falseotherwise

◆ 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]p1first point
[in]p2second point
Return values
trueif p1 and p2 have exactly the same coordinates
falseotherwise

◆ 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]mone 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,p1extremities of the bisector
[in]q0point to be tested
[in]DIMnumber of coordinates of the point
Return values
POSITIVEif d(p0,q0) < d(p1,q0)
NEGATIVEif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (against which orientation is tested)
[in]q0,q1extremities of the segment (that defines the intersection q)
Return values
POSITIVEif d(p0,q) < d(p2,q)
NEGATIVEif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (that defines the intersection q)
[in]p3second extremity of the third bisector (against which orientation is tested)
h0,h1,h2,h3lifted coordinates of p0, p1, p2 and p3
[in]q0,q1,q2vertices of the triangle (that defines the intersection q)
[in]SOSif true, do the symbolic perturbation in the degenerate case
Return values
POSITIVEif d(p0 hp0,q) < d(p3 hp3, q)
NEGATIVEif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (that defines the intersection q)
[in]p3second extremity of the third bisector (against which orientation is tested)
[in]q0,q1,q2vertices of the triangle (that defines the intersection q)
Return values
POSITIVEif d(p0,q) < d(p3,q)
NEGATIVEif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (that defines the intersection q)
[in]p3second extremity of the third bisector (that defines the intersection q)
[in]p4second extremity of the fourth bisector (against which orientation is tested)
Return values
POSITIVEif d(p0,q) < d(p4,q)
NEGATIVEif d(p0,q) > d(p4,q)
ZEROif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (that defines the intersection q)
[in]p3second extremity of the third bisector (that defines the intersection q)
[in]p4second extremity of the fourth bisector (against which orientation is tested)
Return values
POSITIVEif d(p0,q) < d(p4,q)
NEGATIVEif 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]p0first extremity of the bisectors
[in]p1second extremity of the first bisector (that defines the intersection q)
[in]p2second extremity of the second bisector (that defines the intersection q)
[in]p3second extremity of the third bisector (that defines the intersection q)
[in]p4second extremity of the fourth bisector (against which orientation is tested)
[in]q0,q1,q2,q3vertices of the tetrahedron (that defines the intersection q) (that defines the intersection q)
Return values
POSITIVEif d(p0,q) < d(p4,q)
NEGATIVEif 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]comparea comparator for sorting the points
[in]p1,p2,p3,p4the four points
[in]sos_p1,sos_p2,sos_p3,sos_p4the 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))
);
#define SOS_result(x)
Shorthand for writing lambdas for symbolic perturbations.
Definition: PCK.h:145
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
Definition: PCK.h:172

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,p3the three vertices of the triangle
Returns
the coordinate of the normal vector with the greatest absolute value