Geogram  Version 1.9.1-rc
A programming library of geometric algorithms
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 
43 #include <geogram/basic/common.h>
44 #include <geogram/basic/numeric.h>
45 #include <geogram/basic/geometry.h>
46 #include <geogram/numerics/PCK.h>
47 
54 namespace GEO {
55 
62  namespace PCK {
63 
67  enum SOSMode { SOS_ADDRESS, SOS_LEXICO };
68 
80  void GEOGRAM_API set_SOS_mode(SOSMode m);
81 
87  SOSMode GEOGRAM_API get_SOS_mode();
88 
105  Sign GEOGRAM_API side1_SOS(
106  const double* p0, const double* p1,
107  const double* q0,
108  coord_index_t DIM
109  );
110 
131  Sign GEOGRAM_API side2_SOS(
132  const double* p0, const double* p1, const double* p2,
133  const double* q0, const double* q1,
134  coord_index_t DIM
135  );
136 
160  Sign GEOGRAM_API side3_SOS(
161  const double* p0, const double* p1,
162  const double* p2, const double* p3,
163  const double* q0, const double* q1, const double* q2,
164  coord_index_t DIM
165  );
166 
194  const double* p0, const double* p1,
195  const double* p2, const double* p3,
196  double h0, double h1, double h2, double h3,
197  const double* q0, const double* q1, const double* q2,
198  bool SOS=true
199  );
200 
228  Sign GEOGRAM_API side4_SOS(
229  const double* p0,
230  const double* p1, const double* p2,
231  const double* p3, const double* p4,
232  const double* q0, const double* q1,
233  const double* q2, const double* q3,
234  coord_index_t DIM
235  );
236 
237 
262  Sign GEOGRAM_API side4_3d(
263  const double* p0,
264  const double* p1, const double* p2,
265  const double* p3, const double* p4
266  );
267 
293  Sign GEOGRAM_API side4_3d_SOS(
294  const double* p0, const double* p1,
295  const double* p2, const double* p3, const double* p4
296  );
297 
313  Sign GEOGRAM_API in_sphere_3d_SOS(
314  const double* p0, const double* p1,
315  const double* p2, const double* p3,
316  const double* p4
317  );
318 
319 
335  Sign GEOGRAM_API in_circle_2d_SOS(
336  const double* p0, const double* p1, const double* p2,
337  const double* p3
338  );
339 
340 
356  Sign GEOGRAM_API in_circle_3d_SOS(
357  const double* p0, const double* p1, const double* p2,
358  const double* p3
359  );
360 
361 
386  const double* p0, const double* p1, const double* p2,
387  const double* p3,
388  double h0, double h1, double h2, double h3,
389  bool SOS=true
390  );
391 
401  Sign GEOGRAM_API orient_2d(
402  const double* p0, const double* p1, const double* p2
403  );
404 
405 
406 #ifndef GEOGRAM_PSM
416  inline Sign orient_2d(
417  const vec2& p0, const vec2& p1, const vec2& p2
418  ) {
419  return orient_2d(p0.data(),p1.data(),p2.data());
420  }
421 #endif
422 
442  const double* p0, const double* p1,
443  const double* p2, const double* p3,
444  double h0, double h1, double h2, double h3
445  );
446 
447 
457  Sign GEOGRAM_API orient_3d(
458  const double* p0, const double* p1,
459  const double* p2, const double* p3
460  );
461 
462 
463 #ifndef GEOGRAM_PSM
473  inline Sign orient_3d(
474  const vec3& p0, const vec3& p1,
475  const vec3& p2, const vec3& p3
476  ) {
477  return orient_3d(p0.data(),p1.data(),p2.data(),p3.data());
478  }
479 #endif
480 
498  Sign GEOGRAM_API orient_3dlifted(
499  const double* p0, const double* p1,
500  const double* p2, const double* p3, const double* p4,
501  double h0, double h1, double h2, double h3, double h4
502  );
503 
504 
525  const double* p0, const double* p1,
526  const double* p2, const double* p3, const double* p4,
527  double h0, double h1, double h2, double h3, double h4
528  );
529 
530 
537  Sign GEOGRAM_API det_3d(
538  const double* p0, const double* p1, const double* p2
539  );
540 
547  Sign GEOGRAM_API det_4d(
548  const double* p0, const double* p1,
549  const double* p2, const double* p3
550  );
551 
560  Sign GEOGRAM_API det_compare_4d(
561  const double* p0, const double* p1,
562  const double* p2, const double* p3,
563  const double* p4
564  );
565 
574  bool GEOGRAM_API aligned_3d(
575  const double* p0, const double* p1, const double* p2
576  );
577 
585  Sign GEOGRAM_API dot_3d(
586  const double* p0, const double* p1, const double* p2
587  );
588 
589 #ifndef GEOGRAM_PSM
590 
599  inline bool aligned_3d(
600  const vec3& p0, const vec3& p1, const vec3& p2
601  ) {
602  return aligned_3d(p0.data(), p1.data(), p2.data());
603  }
604 
612  inline Sign dot_3d(
613  const vec3& p0, const vec3& p1, const vec3& p2
614  ) {
615  return dot_3d(p0.data(), p1.data(), p2.data());
616  }
617 #endif
618 
624  Sign GEOGRAM_API dot_compare_3d(
625  const double* v0, const double* v1, const double* v2
626  );
627 
637  const double* p1,
638  const double* p2
639  );
640 
649  bool GEOGRAM_API points_are_identical_3d(
650  const double* p1,
651  const double* p2
652  );
653 
662  bool GEOGRAM_API points_are_colinear_3d(
663  const double* p1,
664  const double* p2,
665  const double* p3
666  );
667 
681  const double* p0, const double* p1,
682  const double* p2, const double* p3
683  ) {
684  double a11 = p1[0] - p0[0] ;
685  double a12 = p1[1] - p0[1] ;
686  double a13 = p1[2] - p0[2] ;
687 
688  double a21 = p2[0] - p0[0] ;
689  double a22 = p2[1] - p0[1] ;
690  double a23 = p2[2] - p0[2] ;
691 
692  double a31 = p3[0] - p0[0] ;
693  double a32 = p3[1] - p0[1] ;
694  double a33 = p3[2] - p0[2] ;
695 
696  double Delta = det3x3(
697  a11,a12,a13,
698  a21,a22,a23,
699  a31,a32,a33
700  );
701 
702  return geo_sgn(Delta);
703  }
704 
710  void GEOGRAM_API show_stats();
711 
715  void GEOGRAM_API initialize();
716 
720  void GEOGRAM_API terminate();
721  }
722 }
723 
724 #endif
Utilities to write geometric predicates (Predicate Construction Kit).
T * data()
Gets modifiable vector data.
Definition: vecg.h:161
Common include file, providing basic definitions. Should be included before anything else by all head...
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.
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_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.
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:680
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 orient_2d(const vec2HE &p0, const vec2HE &p1, const vec2HE &p2)
Computes the orientation predicate in 2d.
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
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 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:67
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.
bool aligned_3d(const vec3HE &p0, const vec3HE &p1, const vec3HE &p2)
Tests whether three 3d points are aligned.
Sign orient_3d(const vec3HE &p0, const vec3HE &p1, const vec3HE &p2, const vec3HE &p3)
Computes the orientation predicate in 3d.
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: basic.h:55
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:90
Sign
Integer constants that represent the sign of a value.
Definition: numeric.h:68
geo_coord_index_t coord_index_t
The type for storing coordinate indices, and iterating on the coordinates of a point.
Definition: numeric.h:363
Types and functions for numbers manipulation.