1 // Copyright (c) 2001,2004 INRIA Sophia-Antipolis (France). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org) 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Filtered_kernel/include/CGAL/internal/Static_filters/Coplanar_orientation_3.h $ 7 // $Id: Coplanar_orientation_3.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Sylvain Pion 12 13 #ifndef CGAL_INTERNAL_STATIC_FILTERS_COPLANAR_ORIENTATION_3_H 14 #define CGAL_INTERNAL_STATIC_FILTERS_COPLANAR_ORIENTATION_3_H 15 16 #include <CGAL/Simple_cartesian.h> 17 #include <CGAL/MP_Float.h> 18 #include <CGAL/Profile_counter.h> 19 20 namespace CGAL { namespace internal { namespace Static_filters_predicates { 21 22 // XXX : 23 // Is this really useful to optimize this predicate ? 24 // I de-prioritize it for now. 25 26 27 // This one is easy : it's just 3 Orientation_2. 28 29 template < typename P3 > 30 struct Point_23_xy { 31 const P3 &p; 32 Point_23_xyPoint_23_xy33 Point_23_xy(const P3& pp) : p(pp) {} 34 xPoint_23_xy35 const FT& x() const { return p.x(); } yPoint_23_xy36 const FT& y() const { return p.y(); } 37 }; 38 39 template < typename Kernel > 40 class Coplanar_orientation_3 41 : public Kernel::Coplanar_orientation_3 42 { 43 typedef typename Kernel::Point_3 Point_3; 44 typedef typename Kernel::Coplanar_orientation_3 Base; 45 46 public: 47 typedef Orientation result_type; 48 operator()49 Orientation operator()(const Point_3 &p, const Point_3 &q, const Point_3 &r) const 50 { 51 return opti_coplanar_orientationC3( 52 to_double(p.x()), to_double(p.y()), to_double(p.z()), 53 to_double(q.x()), to_double(q.y()), to_double(q.z()), 54 to_double(r.x()), to_double(r.y()), to_double(r.z())); 55 } 56 operator()57 Orientation operator()(const Point_3 &p, const Point_3 &q, 58 const Point_3 &r, const Point_3 &s) const 59 { 60 return opti_coplanar_orientationC3( 61 to_double(p.x()), to_double(p.y()), to_double(p.z()), 62 to_double(q.x()), to_double(q.y()), to_double(q.z()), 63 to_double(r.x()), to_double(r.y()), to_double(r.z()), 64 to_double(s.x()), to_double(s.y()), to_double(s.z())); 65 } 66 67 private: 68 Orientation opti_coplanar_orientationC3(double px,double py,double pz,double qx,double qy,double qz,double rx,double ry,double rz)69 opti_coplanar_orientationC3(double px, double py, double pz, 70 double qx, double qy, double qz, 71 double rx, double ry, double rz) const 72 { 73 CGAL_PROFILER("Coplanar_orientation_3 #1 calls"); 74 75 std::pair<bool, Orientation> oxy_pqr = orient_2d(px,py,qx,qy,rx,ry); 76 if (oxy_pqr != COLLINEAR) 77 return oxy_pqr; 78 79 CGAL_PROFILER("Coplanar_orientation_3 #1 step2"); 80 81 Orientation oyz_pqr = orient_2d(py,pz,qy,qz,ry,rz); 82 if (oyz_pqr != COLLINEAR) 83 return oyz_pqr; 84 85 CGAL_PROFILER("Coplanar_orientation_3 #1 step3"); 86 87 return orient_2d(px,pz,qx,qz,rx,rz); 88 89 } 90 91 Orientation opti_coplanar_orientationC3(double px,double py,double pz,double qx,double qy,double qz,double rx,double ry,double rz,double sx,double sy,double sz)92 opti_coplanar_orientationC3(double px, double py, double pz, 93 double qx, double qy, double qz, 94 double rx, double ry, double rz, 95 double sx, double sy, double sz) const 96 { 97 CGAL_PROFILER("Coplanar_orientation_3 #2 calls"); 98 99 Orientation oxy_pqr = orient_2d(px,py,qx,qy,rx,ry); 100 if (oxy_pqr != COLLINEAR) 101 return Orientation( oxy_pqr * 102 orient_2d(px,py,qx,qy,sx,sy)); 103 104 CGAL_PROFILER("Coplanar_orientation_3 #2 step2"); 105 106 Orientation oyz_pqr = orient_2d(py,pz,qy,qz,ry,rz); 107 if (oyz_pqr != COLLINEAR) 108 return Orientation( oyz_pqr * 109 orient_2d(py,pz,qy,qz,sy,sz)); 110 111 CGAL_PROFILER("Coplanar_orientation_3 #2 step3"); 112 113 Orientation oxz_pqr = orient_2d(px,pz,qx,qz,rx,rz); 114 CGAL_kernel_assertion(oxz_pqr != COLLINEAR); 115 return Orientation( oxz_pqr * orient_2d(px,pz,qx,qz,sx,sz)); 116 } 117 118 // FIXME : Some code duplicated from Orientation_2... 119 std::pair<bool, Orientation> orient_2d(double px,double py,double qx,double qy,double rx,double ry)120 orient_2d(double px, double py, double qx, double qy, double rx, double ry) const 121 { 122 /* 123 double px = p.x(); 124 double py = p.y(); 125 double qx = q.x(); 126 double qy = q.y(); 127 double rx = r.x(); 128 double ry = r.y(); 129 */ 130 131 CGAL_PROFILER("orient2d calls"); 132 133 double pqx = qx-px; 134 double pqy = qy-py; 135 double prx = rx-px; 136 double pry = ry-py; 137 138 double det = determinant(pqx, pqy, 139 prx, pry); 140 141 // Then semi-static filter. 142 double maxx = CGAL::abs(px); 143 double maxy = CGAL::abs(py); 144 145 double aqx = CGAL::abs(qx); 146 double aqy = CGAL::abs(qy); 147 148 double arx = CGAL::abs(rx); 149 double ary = CGAL::abs(ry); 150 151 if (maxx < aqx) maxx = aqx; 152 if (maxx < arx) maxx = arx; 153 if (maxy < aqy) maxy = aqy; 154 if (maxy < ary) maxy = ary; 155 double eps = 3.55271e-15 * maxx * maxy; 156 157 if (det > eps) return std::make_pair(true, POSITIVE); 158 if (det < -eps) return std::make_pair(true, NEGATIVE); 159 160 CGAL_PROFILER("orient2d semi-static failures"); 161 162 return std::make_pair(false, ZERO); 163 } 164 165 }; 166 167 } } } // namespace CGAL::internal::Static_filters_predicates 168 169 #endif // CGAL_INTERNAL_STATIC_FILTERS_COPLANAR_ORIENTATION_3_H 170