Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
predicates.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40#ifndef GEOGRAM_NUMERICS_PREDICATES
41#define GEOGRAM_NUMERICS_PREDICATES
42
46
52// Uncomment to get full reporting on predicate statistics
53// (but has a non-negligible impact on performance)
54// #define PCK_STATS
55
56namespace GEO {
57
64 namespace PCK {
65
69 enum SOSMode { SOS_ADDRESS, SOS_LEXICO };
70
82 void GEOGRAM_API set_SOS_mode(SOSMode m);
83
89 SOSMode GEOGRAM_API get_SOS_mode();
90
107 Sign GEOGRAM_API side1_SOS(
108 const double* p0, const double* p1,
109 const double* q0,
110 coord_index_t DIM
111 );
112
133 Sign GEOGRAM_API side2_SOS(
134 const double* p0, const double* p1, const double* p2,
135 const double* q0, const double* q1,
136 coord_index_t DIM
137 );
138
162 Sign GEOGRAM_API side3_SOS(
163 const double* p0, const double* p1,
164 const double* p2, const double* p3,
165 const double* q0, const double* q1, const double* q2,
166 coord_index_t DIM
167 );
168
196 const double* p0, const double* p1,
197 const double* p2, const double* p3,
198 double h0, double h1, double h2, double h3,
199 const double* q0, const double* q1, const double* q2,
200 bool SOS=true
201 );
202
230 Sign GEOGRAM_API side4_SOS(
231 const double* p0,
232 const double* p1, const double* p2,
233 const double* p3, const double* p4,
234 const double* q0, const double* q1,
235 const double* q2, const double* q3,
236 coord_index_t DIM
237 );
238
239
264 Sign GEOGRAM_API side4_3d(
265 const double* p0,
266 const double* p1, const double* p2,
267 const double* p3, const double* p4
268 );
269
295 Sign GEOGRAM_API side4_3d_SOS(
296 const double* p0, const double* p1,
297 const double* p2, const double* p3, const double* p4
298 );
299
319 const double* p0, const double* p1,
320 const double* p2, const double* p3,
321 const double* p4
322 );
323
324
341 const double* p0, const double* p1, const double* p2,
342 const double* p3
343 );
344
345
362 const double* p0, const double* p1, const double* p2,
363 const double* p3
364 );
365
366
391 const double* p0, const double* p1, const double* p2,
392 const double* p3,
393 double h0, double h1, double h2, double h3,
394 bool SOS=true
395 );
396
408 Sign GEOGRAM_API orient_2d(
409 const double* p0, const double* p1, const double* p2
410 );
411
412
413#ifndef GEOGRAM_PSM
425 inline Sign orient_2d(
426 const vec2& p0, const vec2& p1, const vec2& p2
427 ) {
428 return orient_2d(p0.data(),p1.data(),p2.data());
429 }
430#endif
431
451 const double* p0, const double* p1,
452 const double* p2, const double* p3,
453 double h0, double h1, double h2, double h3
454 );
455
456
468 Sign GEOGRAM_API orient_3d(
469 const double* p0, const double* p1,
470 const double* p2, const double* p3
471 );
472
473
474#ifndef GEOGRAM_PSM
486 inline Sign orient_3d(
487 const vec3& p0, const vec3& p1,
488 const vec3& p2, const vec3& p3
489 ) {
490 return orient_3d(p0.data(),p1.data(),p2.data(),p3.data());
491 }
492#endif
493
512 const double* p0, const double* p1,
513 const double* p2, const double* p3, const double* p4,
514 double h0, double h1, double h2, double h3, double h4
515 );
516
517
538 const double* p0, const double* p1,
539 const double* p2, const double* p3, const double* p4,
540 double h0, double h1, double h2, double h3, double h4
541 );
542
543
550 Sign GEOGRAM_API det_3d(
551 const double* p0, const double* p1, const double* p2
552 );
553
560 Sign GEOGRAM_API det_4d(
561 const double* p0, const double* p1,
562 const double* p2, const double* p3
563 );
564
573 Sign GEOGRAM_API det_compare_4d(
574 const double* p0, const double* p1,
575 const double* p2, const double* p3,
576 const double* p4
577 );
578
587 bool GEOGRAM_API aligned_3d(
588 const double* p0, const double* p1, const double* p2
589 );
590
598 Sign GEOGRAM_API dot_3d(
599 const double* p0, const double* p1, const double* p2
600 );
601
602#ifndef GEOGRAM_PSM
603
612 inline bool aligned_3d(
613 const vec3& p0, const vec3& p1, const vec3& p2
614 ) {
615 return aligned_3d(p0.data(), p1.data(), p2.data());
616 }
617
625 inline Sign dot_3d(
626 const vec3& p0, const vec3& p1, const vec3& p2
627 ) {
628 return dot_3d(p0.data(), p1.data(), p2.data());
629 }
630#endif
631
637 Sign GEOGRAM_API dot_compare_3d(
638 const double* v0, const double* v1, const double* v2
639 );
640
650 const double* p1,
651 const double* p2
652 );
653
662 bool GEOGRAM_API points_are_identical_3d(
663 const double* p1,
664 const double* p2
665 );
666
675 bool GEOGRAM_API points_are_colinear_3d(
676 const double* p1,
677 const double* p2,
678 const double* p3
679 );
680
696 const double* p0, const double* p1,
697 const double* p2, const double* p3
698 ) {
699 double a11 = p1[0] - p0[0] ;
700 double a12 = p1[1] - p0[1] ;
701 double a13 = p1[2] - p0[2] ;
702
703 double a21 = p2[0] - p0[0] ;
704 double a22 = p2[1] - p0[1] ;
705 double a23 = p2[2] - p0[2] ;
706
707 double a31 = p3[0] - p0[0] ;
708 double a32 = p3[1] - p0[1] ;
709 double a33 = p3[2] - p0[2] ;
710
711 double Delta = det3x3(
712 a11,a12,a13,
713 a21,a22,a23,
714 a31,a32,a33
715 );
716
717 return geo_sgn(Delta);
718 }
719
725 void GEOGRAM_API show_stats();
726
730 void GEOGRAM_API initialize();
731
735 void GEOGRAM_API terminate();
736 }
737}
738
739#endif
740
Common include file, providing basic definitions. Should be included before anything else by all head...
T * data()
Gets modifiable vector data.
Definition vecg.h:147
Geometric functions in 2d and 3d.
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.
bool aligned_3d(const double *p0, const double *p1, const double *p2)
Tests whether three points are aligned.
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.
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.
Sign dot_compare_3d(const double *v0, const double *v1, const double *v2)
Compares two dot products.
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 t...
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.
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 ...
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.
Sign orient_3d_inexact(const double *p0, const double *p1, const double *p2, const double *p3)
Computes the (approximate) orientation predicate in 3d.
Definition predicates.h:695
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.
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.
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) re...
void show_stats()
Displays some statistics about predicates, including the number of calls, the number of exact arithme...
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.
Sign orient_2dlifted_SOS(const vec2HE &p0, const vec2HE &p1, const vec2HE &p2, const vec2HE &p3, double h0, double h1, double h2, double h3)
Computes the 3d orientation test with lifted points.
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 ...
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 ...
Sign dot_3d(const double *p0, const double *p1, const double *p2)
Computes the sign of the dot product between two vectors.
bool points_are_identical_3d(const double *p1, const double *p2)
Tests whether two 3d points are identical.
SOSMode
Mode for symbolic perturbations.
Definition predicates.h:69
bool points_are_colinear_3d(const double *p1, const double *p2, const double *p3)
Tests whether three 3d points are colinear.
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...
bool points_are_identical_2d(const double *p1, const double *p2)
Tests whether two 2d points are identical.
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 t...
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.
void initialize()
Needs to be called before using any predicate.
void terminate()
Needs to be called at the end of the program.
SOSMode get_SOS_mode()
Gets the current mode for handling symbolic perturbations.
void set_SOS_mode(SOSMode m)
Sets the current mode for handling symbolic perturbations (SOS for Simulation Of Simplicity).
Global Vorpaline namespace.
Definition algorithm.h:64
T det3x3(const T &a11, const T &a12, const T &a13, const T &a21, const T &a22, const T &a23, const T &a31, const T &a32, const T &a33)
Computes a three-by-three determinant.
Definition determinant.h:69
Sign geo_sgn(const T &x)
Gets the sign of a value.
Definition numeric.h:246
Sign
Integer constants that represent the sign of a value.
Definition numeric.h:224
geo_coord_index_t coord_index_t
The type for storing coordinate indices, and iterating on the coordinates of a point.
Definition numeric.h:321
Types and functions for numbers manipulation.