Geogram  Version 1.9.1
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 
541 #ifndef GEOGRAM_PSM
548  inline Sign det_3d(
549  const vec3& p0, const vec3& p1, const vec3& p2
550  ) {
551  return det_3d(p0.data(), p1.data(), p2.data());
552  }
553 #endif
554 
561  Sign GEOGRAM_API det_4d(
562  const double* p0, const double* p1,
563  const double* p2, const double* p3
564  );
565 
566 #ifndef GEOGRAM_PSM
573  inline Sign det_4d(
574  const vec4& p0, const vec4& p1,
575  const vec4& p2, const vec4& p3
576  ) {
577  return det_4d(p0.data(), p1.data(), p2.data(), p3.data());
578  }
579 #endif
580 
589  Sign GEOGRAM_API det_compare_4d(
590  const double* p0, const double* p1,
591  const double* p2, const double* p3,
592  const double* p4
593  );
594 
603  bool GEOGRAM_API aligned_3d(
604  const double* p0, const double* p1, const double* p2
605  );
606 
614  Sign GEOGRAM_API dot_3d(
615  const double* p0, const double* p1, const double* p2
616  );
617 
618 #ifndef GEOGRAM_PSM
619 
628  inline bool aligned_3d(
629  const vec3& p0, const vec3& p1, const vec3& p2
630  ) {
631  return aligned_3d(p0.data(), p1.data(), p2.data());
632  }
633 
641  inline Sign dot_3d(
642  const vec3& p0, const vec3& p1, const vec3& p2
643  ) {
644  return dot_3d(p0.data(), p1.data(), p2.data());
645  }
646 #endif
647 
653  Sign GEOGRAM_API dot_compare_3d(
654  const double* v0, const double* v1, const double* v2
655  );
656 
666  const double* p1,
667  const double* p2
668  );
669 
678  bool GEOGRAM_API points_are_identical_3d(
679  const double* p1,
680  const double* p2
681  );
682 
691  bool GEOGRAM_API points_are_colinear_3d(
692  const double* p1,
693  const double* p2,
694  const double* p3
695  );
696 
710  const double* p0, const double* p1,
711  const double* p2, const double* p3
712  ) {
713  double a11 = p1[0] - p0[0] ;
714  double a12 = p1[1] - p0[1] ;
715  double a13 = p1[2] - p0[2] ;
716 
717  double a21 = p2[0] - p0[0] ;
718  double a22 = p2[1] - p0[1] ;
719  double a23 = p2[2] - p0[2] ;
720 
721  double a31 = p3[0] - p0[0] ;
722  double a32 = p3[1] - p0[1] ;
723  double a33 = p3[2] - p0[2] ;
724 
725  double Delta = det3x3(
726  a11,a12,a13,
727  a21,a22,a23,
728  a31,a32,a33
729  );
730 
731  return geo_sgn(Delta);
732  }
733 
739  void GEOGRAM_API show_stats();
740 
744  void GEOGRAM_API initialize();
745 
749  void GEOGRAM_API terminate();
750  }
751 }
752 
753 #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:709
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.