|
BWAPI
|
00001 // Copyright (c) 1999-2005 Utrecht University (The Netherlands), 00002 // ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany), 00003 // INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg 00004 // (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria), 00005 // and Tel-Aviv University (Israel). All rights reserved. 00006 // 00007 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00008 // modify it under the terms of the GNU Lesser General Public License as 00009 // published by the Free Software Foundation; version 2.1 of the License. 00010 // See the file LICENSE.LGPL distributed with CGAL. 00011 // 00012 // Licensees holding a valid commercial license may use this file in 00013 // accordance with the commercial license agreement provided with the software. 00014 // 00015 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00016 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00017 // 00018 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Cartesian_kernel/include/CGAL/Cartesian/function_objects.h $ 00019 // $Id: function_objects.h 50389 2009-07-06 11:36:33Z afabri $ 00020 // 00021 // 00022 // Author(s) : Stefan Schirra, Sylvain Pion, Michael Hoffmann 00023 00024 #ifndef CGAL_CARTESIAN_FUNCTION_OBJECTS_H 00025 #define CGAL_CARTESIAN_FUNCTION_OBJECTS_H 00026 00027 #include <CGAL/Kernel/function_objects.h> 00028 #include <CGAL/predicates/kernel_ftC2.h> 00029 #include <CGAL/predicates/kernel_ftC3.h> 00030 #include <CGAL/constructions/kernel_ftC2.h> 00031 #include <CGAL/constructions/kernel_ftC3.h> 00032 #include <CGAL/Cartesian/solve_3.h> 00033 00034 CGAL_BEGIN_NAMESPACE 00035 00036 namespace CartesianKernelFunctors { 00037 00038 using namespace CommonKernelFunctors; 00039 00040 template <typename K> 00041 class Angle_2 00042 { 00043 typedef typename K::Point_2 Point_2; 00044 public: 00045 typedef typename K::Angle result_type; 00046 00047 result_type 00048 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 00049 { return angleC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); } 00050 }; 00051 00052 template <typename K> 00053 class Angle_3 00054 { 00055 typedef typename K::Point_3 Point_3; 00056 public: 00057 typedef typename K::Angle result_type; 00058 00059 result_type 00060 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 00061 { 00062 return angleC3(p.x(), p.y(), p.z(), 00063 q.x(), q.y(), q.z(), 00064 r.x(), r.y(), r.z()); 00065 } 00066 }; 00067 00068 template <typename K> 00069 class Are_parallel_2 00070 { 00071 typedef typename K::Line_2 Line_2; 00072 typedef typename K::Segment_2 Segment_2; 00073 typedef typename K::Ray_2 Ray_2; 00074 00075 public: 00076 typedef typename K::Boolean result_type; 00077 00078 result_type 00079 operator()(const Line_2& l1, const Line_2& l2) const 00080 { return parallelC2(l1.a(), l1.b(), l2.a(), l2.b()); } 00081 00082 result_type 00083 operator()(const Segment_2& s1, const Segment_2& s2) const 00084 { return parallelC2(s1.source().x(), s1.source().y(), 00085 s1.target().x(), s1.target().y(), 00086 s2.source().x(), s2.source().y(), 00087 s2.target().x(), s2.target().y()); 00088 } 00089 00090 result_type 00091 operator()(const Ray_2& r1, const Ray_2& r2) const 00092 { return parallelC2(r1.source().x(), r1.source().y(), 00093 r1.second_point().x(), r1.second_point().y(), 00094 r2.source().x(), r2.source().y(), 00095 r2.second_point().x(), r2.second_point().y()); 00096 } 00097 }; 00098 00099 template <typename K> 00100 class Are_parallel_3 00101 { 00102 typedef typename K::Line_3 Line_3; 00103 typedef typename K::Segment_3 Segment_3; 00104 typedef typename K::Ray_3 Ray_3; 00105 typedef typename K::Plane_3 Plane_3; 00106 00107 public: 00108 typedef typename K::Boolean result_type; 00109 00110 result_type 00111 operator()(const Line_3& l1, const Line_3& l2) const 00112 { return parallelC3( 00113 l1.to_vector().x(), l1.to_vector().y(), l1.to_vector().z(), 00114 l2.to_vector().x(), l2.to_vector().y(), l2.to_vector().z()); 00115 } 00116 00117 result_type 00118 operator()(const Plane_3& h1, const Plane_3& h2) const 00119 { return parallelC3(h1.a(), h1.b(), h1.c(), 00120 h2.a(), h2.b(), h2.c()); 00121 } 00122 00123 result_type 00124 operator()(const Segment_3& s1, const Segment_3& s2) const 00125 { return parallelC3(s1.source().x(), s1.source().y(), s1.source().z(), 00126 s1.target().x(), s1.target().y(), s1.target().z(), 00127 s2.source().x(), s2.source().y(), s2.source().z(), 00128 s2.target().x(), s2.target().y(), s2.target().z()); 00129 } 00130 00131 result_type 00132 operator()(const Ray_3& r1, const Ray_3& r2) const 00133 { return parallelC3(r1.source().x(), r1.source().y(), r1.source().z(), 00134 r1.second_point().x(), r1.second_point().y(), r1.second_point().z(), 00135 r2.source().x(), r2.source().y(), r2.source().z(), 00136 r2.second_point().x(), r2.second_point().y(), r2.second_point().z()); 00137 } 00138 }; 00139 00140 template <typename K> 00141 class Bounded_side_2 00142 { 00143 typedef typename K::Point_2 Point_2; 00144 typedef typename K::Circle_2 Circle_2; 00145 typedef typename K::Triangle_2 Triangle_2; 00146 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 00147 public: 00148 typedef typename K::Bounded_side result_type; 00149 00150 result_type 00151 operator()( const Circle_2& c, const Point_2& p) const 00152 { 00153 typename K::Compute_squared_distance_2 squared_distance; 00154 return enum_cast<Bounded_side>(CGAL_NTS compare(c.squared_radius(), 00155 squared_distance(c.center(),p))); 00156 } 00157 00158 result_type 00159 operator()( const Triangle_2& t, const Point_2& p) const 00160 { 00161 typename K::Collinear_are_ordered_along_line_2 00162 collinear_are_ordered_along_line; 00163 typename K::Orientation_2 orientation; 00164 typename K::Orientation o1 = orientation(t.vertex(0), t.vertex(1), p), 00165 o2 = orientation(t.vertex(1), t.vertex(2), p), 00166 o3 = orientation(t.vertex(2), t.vertex(3), p); 00167 00168 if (o2 == o1 && o3 == o1) 00169 return ON_BOUNDED_SIDE; 00170 return 00171 (o1 == COLLINEAR 00172 && collinear_are_ordered_along_line(t.vertex(0), p, t.vertex(1))) || 00173 (o2 == COLLINEAR 00174 && collinear_are_ordered_along_line(t.vertex(1), p, t.vertex(2))) || 00175 (o3 == COLLINEAR 00176 && collinear_are_ordered_along_line(t.vertex(2), p, t.vertex(3))) 00177 ? ON_BOUNDARY 00178 : ON_UNBOUNDED_SIDE; 00179 } 00180 00181 result_type 00182 operator()( const Iso_rectangle_2& r, const Point_2& p) const 00183 { 00184 bool x_incr = (r.xmin() < p.x()) && (p.x() < r.xmax()), 00185 y_incr = (r.ymin() < p.y()) && (p.y() < r.ymax()); 00186 if (x_incr) 00187 { 00188 if (y_incr) 00189 return ON_BOUNDED_SIDE; 00190 if ( (p.y() == r.ymin()) || (r.ymax() == p.y()) ) 00191 return ON_BOUNDARY; 00192 } 00193 if ( (p.x() == r.xmin()) || (r.xmax() == p.x()) ) 00194 if ( y_incr || (p.y() == r.ymin()) || (r.ymax() == p.y()) ) 00195 return ON_BOUNDARY; 00196 00197 return ON_UNBOUNDED_SIDE; 00198 } 00199 }; 00200 00201 template <typename K> 00202 class Bounded_side_3 00203 { 00204 typedef typename K::FT FT; 00205 typedef typename K::Point_3 Point_3; 00206 typedef typename K::Sphere_3 Sphere_3; 00207 typedef typename K::Circle_3 Circle_3; 00208 typedef typename K::Tetrahedron_3 Tetrahedron_3; 00209 typedef typename K::Iso_cuboid_3 Iso_cuboid_3; 00210 public: 00211 typedef typename K::Bounded_side result_type; 00212 00213 result_type 00214 operator()( const Sphere_3& s, const Point_3& p) const 00215 { return s.rep().bounded_side(p); } 00216 00217 result_type 00218 operator()( const Circle_3& s, const Point_3& p) const 00219 { return s.rep().bounded_side(p); } 00220 00221 result_type 00222 operator()( const Tetrahedron_3& t, const Point_3& p) const 00223 { 00224 FT alpha, beta, gamma; 00225 00226 Cartesian_internal::solve(t.vertex(1)-t.vertex(0), 00227 t.vertex(2)-t.vertex(0), 00228 t.vertex(3)-t.vertex(0), 00229 p - t.vertex(0), alpha, beta, gamma); 00230 if ( (alpha < 0) || (beta < 0) || (gamma < 0) 00231 || (alpha + beta + gamma > 1) ) 00232 return ON_UNBOUNDED_SIDE; 00233 00234 if ( (alpha == 0) || (beta == 0) || (gamma == 0) 00235 || (alpha+beta+gamma == 1) ) 00236 return ON_BOUNDARY; 00237 00238 return ON_BOUNDED_SIDE; 00239 } 00240 00241 result_type 00242 operator()( const Iso_cuboid_3& c, const Point_3& p) const 00243 { 00244 return c.rep().bounded_side(p); 00245 } 00246 00247 }; 00248 00249 template <typename K> 00250 class Collinear_are_ordered_along_line_2 00251 { 00252 typedef typename K::Point_2 Point_2; 00253 public: 00254 typedef typename K::Boolean result_type; 00255 00256 result_type 00257 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 00258 { 00259 CGAL_kernel_exactness_precondition( collinear(p, q, r) ); 00260 return collinear_are_ordered_along_lineC2 00261 (p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); 00262 } 00263 }; 00264 00265 template <typename K> 00266 class Collinear_are_ordered_along_line_3 00267 { 00268 typedef typename K::Point_3 Point_3; 00269 public: 00270 typedef typename K::Boolean result_type; 00271 00272 result_type 00273 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 00274 { 00275 CGAL_kernel_exactness_precondition( collinear(p, q, r) ); 00276 return collinear_are_ordered_along_lineC3(p.x(), p.y(), p.z(), 00277 q.x(), q.y(), q.z(), 00278 r.x(), r.y(), r.z()); 00279 } 00280 }; 00281 00282 template <typename K> 00283 class Collinear_are_strictly_ordered_along_line_2 00284 { 00285 typedef typename K::Point_2 Point_2; 00286 public: 00287 typedef typename K::Boolean result_type; 00288 00289 result_type 00290 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 00291 { 00292 CGAL_kernel_exactness_precondition( collinear(p, q, r) ); 00293 return collinear_are_strictly_ordered_along_lineC2 00294 (p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); 00295 } 00296 }; 00297 00298 template <typename K> 00299 class Collinear_are_strictly_ordered_along_line_3 00300 { 00301 typedef typename K::Point_3 Point_3; 00302 public: 00303 typedef typename K::Boolean result_type; 00304 00305 result_type 00306 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 00307 { 00308 CGAL_kernel_exactness_precondition( collinear(p, q, r) ); 00309 return collinear_are_strictly_ordered_along_lineC3(p.x(), p.y(), p.z(), 00310 q.x(), q.y(), q.z(), 00311 r.x(), r.y(), r.z()); 00312 } 00313 }; 00314 00315 template <typename K> 00316 class Collinear_has_on_2 00317 { 00318 typedef typename K::Point_2 Point_2; 00319 typedef typename K::Ray_2 Ray_2; 00320 typedef typename K::Segment_2 Segment_2; 00321 public: 00322 typedef typename K::Boolean result_type; 00323 00324 result_type 00325 operator()( const Ray_2& r, const Point_2& p) const 00326 { 00327 const Point_2 & source = r.source(); 00328 const Point_2 & second = r.second_point(); 00329 switch(make_certain(compare_x(source, second))) { 00330 case SMALLER: 00331 return compare_x(source, p) != LARGER; 00332 case LARGER: 00333 return compare_x(p, source) != LARGER; 00334 default: 00335 switch(make_certain(compare_y(source, second))){ 00336 case SMALLER: 00337 return compare_y(source, p) != LARGER; 00338 case LARGER: 00339 return compare_y(p, source) != LARGER; 00340 default: 00341 return true; // p == source 00342 } 00343 } // switch 00344 } 00345 00346 result_type 00347 operator()( const Segment_2& s, const Point_2& p) const 00348 { 00349 return collinear_are_ordered_along_line(s.source(), p, s.target()); 00350 } 00351 }; 00352 00353 template <typename K> 00354 class Collinear_2 00355 { 00356 typedef typename K::Point_2 Point_2; 00357 typedef typename K::Orientation_2 Orientation_2; 00358 Orientation_2 o; 00359 public: 00360 typedef typename K::Boolean result_type; 00361 00362 Collinear_2() {} 00363 Collinear_2(const Orientation_2 o_) : o(o_) {} 00364 00365 result_type 00366 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 00367 { return o(p, q, r) == COLLINEAR; } 00368 }; 00369 00370 template <typename K> 00371 class Collinear_3 00372 { 00373 typedef typename K::Point_3 Point_3; 00374 public: 00375 typedef typename K::Boolean result_type; 00376 00377 result_type 00378 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 00379 { 00380 return collinearC3(p.x(), p.y(), p.z(), 00381 q.x(), q.y(), q.z(), 00382 r.x(), r.y(), r.z()); 00383 } 00384 }; 00385 00386 template <typename K> 00387 class Compare_angle_with_x_axis_2 00388 { 00389 typedef typename K::Direction_2 Direction_2; 00390 public: 00391 typedef typename K::Comparison_result result_type; 00392 00393 result_type 00394 operator()(const Direction_2& d1, const Direction_2& d2) const 00395 { 00396 return compare_angle_with_x_axisC2(d1.dx(), d1.dy(), d2.dx(), d2.dy()); 00397 } 00398 }; 00399 00400 template <typename K> 00401 class Compare_distance_2 00402 { 00403 typedef typename K::Point_2 Point_2; 00404 public: 00405 typedef typename K::Comparison_result result_type; 00406 00407 result_type 00408 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 00409 { 00410 return cmp_dist_to_pointC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); 00411 } 00412 }; 00413 00414 template <typename K> 00415 class Compare_squared_distance_2 00416 { 00417 typedef typename K::Point_2 Point_2; 00418 typedef typename K::FT FT; 00419 public: 00420 typedef typename K::Comparison_result result_type; 00421 00422 result_type 00423 operator()(const Point_2& p, const Point_2& q, const FT& d2) const 00424 { 00425 return CGAL_NTS compare(squared_distance(p, q), d2); 00426 } 00427 }; 00428 00429 template <typename K> 00430 class Compare_distance_3 00431 { 00432 typedef typename K::Point_3 Point_3; 00433 public: 00434 typedef typename K::Comparison_result result_type; 00435 00436 result_type 00437 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 00438 { 00439 return cmp_dist_to_pointC3(p.x(), p.y(), p.z(), 00440 q.x(), q.y(), q.z(), 00441 r.x(), r.y(), r.z()); 00442 } 00443 }; 00444 00445 template <typename K> 00446 class Compare_squared_distance_3 00447 { 00448 typedef typename K::Point_3 Point_3; 00449 typedef typename K::FT FT; 00450 public: 00451 typedef typename K::Comparison_result result_type; 00452 00453 result_type 00454 operator()(const Point_3& p, const Point_3& q, const FT& d2) const 00455 { 00456 return CGAL_NTS compare(squared_distance(p, q), d2); 00457 } 00458 }; 00459 00460 00461 template <typename K> 00462 class Compare_squared_radius_3 00463 { 00464 typedef typename K::Point_3 Point_3; 00465 typedef typename K::FT FT; 00466 public: 00467 typedef typename K::Comparison_result result_type; 00468 00469 result_type 00470 operator()(const Point_3& p, const Point_3& q, const Point_3& r, const Point_3& s, const FT& ft) const 00471 { 00472 return CGAL_NTS compare(squared_radiusC3(p.x(), p.y(), p.z(), 00473 q.x(), q.y(), q.z(), 00474 r.x(), r.y(), r.z(), 00475 s.x(), s.y(), s.z() ), 00476 ft); 00477 } 00478 00479 result_type 00480 operator()(const Point_3& p, const Point_3& q, const Point_3& r, const FT& ft) const 00481 { 00482 return CGAL_NTS compare(squared_radiusC3(p.x(), p.y(), p.z(), 00483 q.x(), q.y(), q.z(), 00484 r.x(), r.y(), r.z()), 00485 ft); 00486 } 00487 00488 result_type 00489 operator()(const Point_3& p, const Point_3& q, const FT& ft) const 00490 { 00491 return CGAL_NTS compare(squared_radiusC3(p.x(), p.y(), p.z(), 00492 q.x(), q.y(), q.z() ), 00493 ft); 00494 } 00495 }; 00496 00497 00498 00499 template <typename K> 00500 class Compare_slope_2 00501 { 00502 typedef typename K::Line_2 Line_2; 00503 typedef typename K::Segment_2 Segment_2; 00504 public: 00505 typedef typename K::Comparison_result result_type; 00506 00507 result_type 00508 operator()(const Line_2& l1, const Line_2& l2) const 00509 { 00510 return compare_slopesC2(l1.a(), l1.b(), l2.a(), l2.b()); 00511 } 00512 00513 result_type 00514 operator()(const Segment_2& s1, const Segment_2& s2) const 00515 { 00516 return compare_slopesC2(s1.source().x(), s1.source().y(), 00517 s1.target().x(), s1.target().y(), 00518 s2.source().x(), s2.source().y(), 00519 s2.target().x(), s2.target().y()); 00520 } 00521 }; 00522 00523 template <typename K> 00524 class Compare_x_at_y_2 00525 { 00526 typedef typename K::Point_2 Point_2; 00527 typedef typename K::Line_2 Line_2; 00528 public: 00529 typedef typename K::Comparison_result result_type; 00530 00531 result_type 00532 operator()( const Point_2& p, const Line_2& h) const 00533 { return compare_y_at_xC2(p.y(), p.x(), h.b(), h.a(), h.c()); } 00534 00535 result_type 00536 operator()( const Point_2& p, const Line_2& h1, const Line_2& h2) const 00537 { 00538 return compare_y_at_xC2(p.y(), h1.b(), h1.a(), h1.c(), 00539 h2.b(), h2.a(), h2.c()); 00540 } 00541 00542 result_type 00543 operator()( const Line_2& l1, const Line_2& l2, const Line_2& h) const 00544 { 00545 return compare_y_at_xC2(l1.b(), l1.a(), l1.c(), l2.b(), l2.a(), l2.c(), 00546 h.b(), h.a(), h.c()); 00547 } 00548 00549 result_type 00550 operator()( const Line_2& l1, const Line_2& l2, 00551 const Line_2& h1, const Line_2& h2) const 00552 { 00553 return compare_y_at_xC2(l1.b(), l1.a(), l1.c(), l2.b(), l2.a(), l2.c(), 00554 h1.b(), h1.a(), h1.c(), h2.b(), h2.a(), h2.c()); 00555 } 00556 }; 00557 00558 template <typename K> 00559 class Compare_xyz_3 00560 { 00561 typedef typename K::Point_3 Point_3; 00562 public: 00563 typedef typename K::Comparison_result result_type; 00564 00565 result_type 00566 operator()( const Point_3& p, const Point_3& q) const 00567 { 00568 return compare_lexicographically_xyzC3(p.x(), p.y(), p.z(), 00569 q.x(), q.y(), q.z()); 00570 } 00571 }; 00572 00573 template <typename K> 00574 class Compare_xy_2 00575 { 00576 typedef typename K::Point_2 Point_2; 00577 public: 00578 typedef typename K::Comparison_result result_type; 00579 00580 result_type 00581 operator()( const Point_2& p, const Point_2& q) const 00582 { return compare_lexicographically_xyC2(p.x(), p.y(), q.x(), q.y()); } 00583 }; 00584 00585 template <typename K> 00586 class Compare_xy_3 00587 { 00588 typedef typename K::Point_3 Point_3; 00589 public: 00590 typedef typename K::Comparison_result result_type; 00591 00592 result_type 00593 operator()( const Point_3& p, const Point_3& q) const 00594 { return compare_lexicographically_xyC2(p.x(), p.y(), q.x(), q.y()); } 00595 }; 00596 00597 template <typename K> 00598 class Compare_x_2 00599 { 00600 typedef typename K::Point_2 Point_2; 00601 typedef typename K::Line_2 Line_2; 00602 public: 00603 typedef typename K::Comparison_result result_type; 00604 00605 result_type 00606 operator()( const Point_2& p, const Point_2& q) const 00607 { return CGAL_NTS compare(p.x(), q.x()); } 00608 00609 result_type 00610 operator()( const Point_2& p, const Line_2& l, const Line_2& h) const 00611 { return compare_xC2(p.x(), l.a(), l.b(), l.c(), h.a(), h.b(), h.c()); } 00612 00613 result_type 00614 operator()( const Line_2& l, const Line_2& h1, const Line_2& h2) const 00615 { 00616 return compare_xC2(l.a(), l.b(), l.c(), h1.a(), h1.b(), h1.c(), 00617 h2.a(), h2.b(), h2.c()); 00618 } 00619 00620 result_type 00621 operator()( const Line_2& l1, const Line_2& l2, 00622 const Line_2& h1, const Line_2& h2) const 00623 { 00624 return compare_xC2(l1.a(), l1.b(), l1.c(), l2.a(), l2.b(), l2.c(), 00625 h1.a(), h1.b(), h1.c(), h2.a(), h2.b(), h2.c()); 00626 } 00627 }; 00628 00629 template <typename K> 00630 class Compare_x_3 00631 { 00632 typedef typename K::Point_3 Point_3; 00633 public: 00634 typedef typename K::Comparison_result result_type; 00635 00636 result_type 00637 operator()( const Point_3& p, const Point_3& q) const 00638 { return CGAL_NTS compare(p.x(), q.x()); } 00639 }; 00640 00641 template <typename K> 00642 class Compare_yx_2 00643 { 00644 typedef typename K::Point_2 Point_2; 00645 public: 00646 typedef typename K::Comparison_result result_type; 00647 00648 result_type 00649 operator()( const Point_2& p, const Point_2& q) const 00650 { return compare_lexicographically_xyC2(p.y(), p.x(), q.y(), q.x()); } 00651 }; 00652 00653 template <typename K> 00654 class Compare_y_at_x_2 00655 { 00656 typedef typename K::Point_2 Point_2; 00657 typedef typename K::Line_2 Line_2; 00658 typedef typename K::Segment_2 Segment_2; 00659 public: 00660 typedef typename K::Comparison_result result_type; 00661 00662 result_type 00663 operator()( const Point_2& p, const Line_2& h) const 00664 { return compare_y_at_xC2(p.x(), p.y(), h.a(), h.b(), h.c()); } 00665 00666 result_type 00667 operator()( const Point_2& p, const Line_2& h1, const Line_2& h2) const 00668 { 00669 return compare_y_at_xC2(p.x(), h1.a(), h1.b(), h1.c(), 00670 h2.a(), h2.b(), h2.c()); 00671 } 00672 00673 result_type 00674 operator()( const Line_2& l1, const Line_2& l2, const Line_2& h) const 00675 { 00676 return compare_y_at_xC2(l1.a(), l1.b(), l1.c(), l2.a(), l2.b(), l2.c(), 00677 h.a(), h.b(), h.c()); 00678 } 00679 00680 result_type 00681 operator()( const Line_2& l1, const Line_2& l2, 00682 const Line_2& h1, const Line_2& h2) const 00683 { 00684 return compare_y_at_xC2(l1.a(), l1.b(), l1.c(), l2.a(), l2.b(), l2.c(), 00685 h1.a(), h1.b(), h1.c(), h2.a(), h2.b(), h2.c()); 00686 } 00687 00688 result_type 00689 operator()( const Point_2& p, const Segment_2& s) const 00690 { 00691 return compare_y_at_xC2(p.x(), p.y(), 00692 s.source().x(), s.source().y(), 00693 s.target().x(), s.target().y()); 00694 } 00695 00696 result_type 00697 operator()( const Point_2& p, 00698 const Segment_2& s1, const Segment_2& s2) const 00699 { 00700 return compare_y_at_x_segment_C2(p.x(), 00701 s1.source().x(), s1.source().y(), 00702 s1.target().x(), s1.target().y(), 00703 s2.source().x(), s2.source().y(), 00704 s2.target().x(), s2.target().y()); 00705 } 00706 }; 00707 00708 template <typename K> 00709 class Compare_y_2 00710 { 00711 typedef typename K::Point_2 Point_2; 00712 typedef typename K::Line_2 Line_2; 00713 public: 00714 typedef typename K::Comparison_result result_type; 00715 00716 result_type 00717 operator()( const Point_2& p, const Point_2& q) const 00718 { return CGAL_NTS compare(p.y(), q.y()); } 00719 00720 result_type 00721 operator()( const Point_2& p, const Line_2& l1, const Line_2& l2) const 00722 { 00723 return compare_xC2(p.y(), 00724 l1.b(), l1.a(), l1.c(), 00725 l2.b(), l2.a(), l2.c()); 00726 } 00727 00728 result_type 00729 operator()( const Line_2& l, const Line_2& h1, const Line_2& h2) const 00730 { 00731 return compare_xC2(l.b(), l.a(), l.c(), h1.b(), h1.a(), h1.c(), 00732 l.b(), l.a(), l.c(), h2.b(), h2.a(), h2.c()); 00733 } 00734 00735 result_type 00736 operator()( const Line_2& l1, const Line_2& l2, 00737 const Line_2& h1, const Line_2& h2) const 00738 { 00739 return compare_xC2(l1.b(), l1.a(), l1.c(), l2.b(), l2.a(), l2.c(), 00740 h1.b(), h1.a(), h1.c(), h2.b(), h2.a(), h2.c()); 00741 } 00742 }; 00743 00744 template <typename K> 00745 class Compare_y_3 00746 { 00747 typedef typename K::Point_3 Point_3; 00748 public: 00749 typedef typename K::Comparison_result result_type; 00750 00751 result_type 00752 operator()( const Point_3& p, const Point_3& q) const 00753 { return CGAL_NTS compare(p.y(), q.y()); } 00754 }; 00755 00756 template <typename K> 00757 class Compare_z_3 00758 { 00759 typedef typename K::Point_3 Point_3; 00760 public: 00761 typedef typename K::Comparison_result result_type; 00762 00763 result_type 00764 operator()( const Point_3& p, const Point_3& q) const 00765 { return CGAL_NTS compare(p.z(), q.z()); } 00766 }; 00767 00768 template <class K> 00769 class Compute_approximate_area_3 00770 { 00771 typedef typename K::Circle_3 Circle_3; 00772 typedef typename K::FT FT; 00773 00774 public: 00775 00776 typedef double result_type; 00777 00778 result_type 00779 operator() (const Circle_3 & c) const 00780 // { return c.rep().approximate_area(); } 00781 { return CGAL_PI * to_double(c.squared_radius()); } 00782 }; 00783 00784 template <class K> 00785 class Compute_approximate_squared_length_3 00786 { 00787 typedef typename K::Circle_3 Circle_3; 00788 typedef typename K::FT FT; 00789 00790 public: 00791 00792 typedef double result_type; 00793 00794 result_type 00795 operator() (const Circle_3 & c) const 00796 // { return c.rep().approximate_squared_length(); } 00797 { return CGAL_PI * CGAL_PI * 4.0 * to_double(c.squared_radius()); } 00798 }; 00799 00800 00801 template <typename K> 00802 class Compute_area_2 00803 { 00804 typedef typename K::FT FT; 00805 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 00806 typedef typename K::Triangle_2 Triangle_2; 00807 typedef typename K::Point_2 Point_2; 00808 public: 00809 typedef FT result_type; 00810 00811 result_type 00812 operator()( const Point_2& p, const Point_2& q, const Point_2& r ) const 00813 { 00814 FT v1x = q.x() - p.x(); 00815 FT v1y = q.y() - p.y(); 00816 FT v2x = r.x() - p.x(); 00817 FT v2y = r.y() - p.y(); 00818 return determinant(v1x, v1y, v2x, v2y)/2; 00819 } 00820 00821 result_type 00822 operator()( const Iso_rectangle_2& r ) const 00823 { return (r.xmax()-r.xmin()) * (r.ymax()-r.ymin()); } 00824 00825 result_type 00826 operator()( const Triangle_2& t ) const 00827 { return t.area(); } 00828 }; 00829 00830 template <typename K> 00831 class Compute_area_divided_by_pi_3 00832 { 00833 typedef typename K::Circle_3 Circle_3; 00834 typedef typename K::FT FT; 00835 00836 public: 00837 00838 typedef FT result_type; 00839 00840 result_type 00841 operator()(const Circle_3 & c) const 00842 { return c.rep().area_divided_by_pi(); } 00843 00844 }; 00845 00846 template <typename K> 00847 class Compute_determinant_2 00848 { 00849 typedef typename K::FT FT; 00850 typedef typename K::Vector_2 Vector_2; 00851 public: 00852 typedef FT result_type; 00853 00854 result_type 00855 operator()(const Vector_2& v, const Vector_2& w) const 00856 { 00857 return determinant(v.x(), v.y(), w.x(), w.y()); 00858 } 00859 }; 00860 00861 template <typename K> 00862 class Compute_determinant_3 00863 { 00864 typedef typename K::FT FT; 00865 typedef typename K::Vector_3 Vector_3; 00866 public: 00867 typedef FT result_type; 00868 00869 result_type 00870 operator()(const Vector_3& v, const Vector_3& w, const Vector_3& t) const 00871 { 00872 return determinant(v.x(), v.y(), v.z(), 00873 w.x(), w.y(), w.z(), 00874 t.x(), t.y(), t.z()); 00875 } 00876 }; 00877 00878 template <typename K> 00879 class Compute_scalar_product_2 00880 { 00881 typedef typename K::FT FT; 00882 typedef typename K::Vector_2 Vector_2; 00883 public: 00884 typedef FT result_type; 00885 00886 result_type 00887 operator()(const Vector_2& v, const Vector_2& w) const 00888 { 00889 return v.x() * w.x() + v.y() * w.y(); 00890 } 00891 }; 00892 00893 template <typename K> 00894 class Compute_scalar_product_3 00895 { 00896 typedef typename K::FT FT; 00897 typedef typename K::Vector_3 Vector_3; 00898 public: 00899 typedef FT result_type; 00900 00901 result_type 00902 operator()(const Vector_3& v, const Vector_3& w) const 00903 { 00904 return v.x() * w.x() + v.y() * w.y() + v.z() * w.z(); 00905 } 00906 }; 00907 00908 template <typename K> 00909 class Compute_squared_area_3 00910 { 00911 typedef typename K::FT FT; 00912 typedef typename K::Point_3 Point_3; 00913 typedef typename K::Triangle_3 Triangle_3; 00914 public: 00915 typedef FT result_type; 00916 00917 result_type 00918 operator()( const Triangle_3& t ) const 00919 { 00920 return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2)); 00921 } 00922 00923 result_type 00924 operator()( const Point_3& p, const Point_3& q, const Point_3& r ) const 00925 { 00926 return squared_areaC3(p.x(), p.y(), p.z(), 00927 q.x(), q.y(), q.z(), 00928 r.x(), r.y(), r.z()); 00929 } 00930 }; 00931 00932 // FIXME 00933 template <typename K> 00934 class Compute_squared_distance_Point_Point_2 00935 { 00936 typedef typename K::FT FT; 00937 typedef typename K::Point_2 Point_2; 00938 public: 00939 typedef FT result_type; 00940 00941 result_type 00942 operator()( const Point_2& p, const Point_2& q) const 00943 { 00944 return squared_distanceC2(p.x(), p.y(), q.x(), q.y()); 00945 } 00946 }; 00947 00948 template <class K> 00949 class Compute_squared_length_divided_by_pi_square_3 00950 { 00951 typedef typename K::Circle_3 Circle_3; 00952 typedef typename K::FT FT; 00953 00954 public: 00955 00956 typedef FT result_type; 00957 00958 result_type 00959 operator() (const Circle_3 & c) const 00960 { return c.rep().squared_length_divided_by_pi_square(); } 00961 00962 }; 00963 00964 // TODO ... 00965 template <typename K> 00966 class Compute_squared_radius_2 00967 { 00968 typedef typename K::FT FT; 00969 typedef typename K::Point_2 Point_2; 00970 typedef typename K::Circle_2 Circle_2; 00971 public: 00972 typedef FT result_type; 00973 00974 const result_type& 00975 operator()( const Circle_2& c) const 00976 { return c.rep().squared_radius(); } 00977 00978 result_type 00979 operator()( const Point_2& p) const 00980 { return FT(0); } 00981 00982 result_type 00983 operator()( const Point_2& p, const Point_2& q) const 00984 { return squared_radiusC2(p.x(), p.y(), q.x(), q.y()); } 00985 00986 result_type 00987 operator()( const Point_2& p, const Point_2& q, const Point_2& r) const 00988 { return squared_radiusC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); } 00989 }; 00990 00991 } //namespace CartesianKernelFunctors 00992 00993 #ifndef CGAL_CFG_DONT_OVERLOAD_TOO_MUCH 00994 template < typename K> 00995 struct Qualified_result_of<CartesianKernelFunctors::Compute_squared_radius_2<K>, 00996 typename K::Circle_2> 00997 { 00998 typedef typename K::FT const & type; 00999 }; 01000 #endif 01001 01002 // For the non specialized template will do the right thing, 01003 // namely return a copy of an FT 01004 01005 namespace CartesianKernelFunctors { 01006 01007 template <typename K> 01008 class Compute_squared_radius_3 01009 { 01010 typedef typename K::FT FT; 01011 typedef typename K::Point_3 Point_3; 01012 typedef typename K::Sphere_3 Sphere_3; 01013 typedef typename K::Circle_3 Circle_3; 01014 public: 01015 typedef FT result_type; 01016 01017 result_type 01018 operator()( const Sphere_3& s) const 01019 { return s.rep().squared_radius(); } 01020 01021 result_type 01022 operator()( const Circle_3& c) const 01023 { return c.rep().squared_radius(); } 01024 01025 result_type 01026 operator()( const Point_3& p) const 01027 { return FT(0); } 01028 01029 result_type 01030 operator()( const Point_3& p, const Point_3& q) const 01031 { 01032 return squared_radiusC3(p.x(), p.y(), p.z(), 01033 q.x(), q.y(), q.z()); 01034 } 01035 01036 result_type 01037 operator()( const Point_3& p, const Point_3& q, const Point_3& r) const 01038 { 01039 return squared_radiusC3(p.x(), p.y(), p.z(), 01040 q.x(), q.y(), q.z(), 01041 r.x(), r.y(), r.z()); 01042 } 01043 01044 result_type 01045 operator()( const Point_3& p, const Point_3& q, 01046 const Point_3& r, const Point_3& s) const 01047 { 01048 return squared_radiusC3(p.x(), p.y(), p.z(), 01049 q.x(), q.y(), q.z(), 01050 r.x(), r.y(), r.z(), 01051 s.x(), s.y(), s.z()); 01052 } 01053 }; 01054 01055 template <typename K> 01056 class Compute_volume_3 01057 { 01058 typedef typename K::FT FT; 01059 typedef typename K::Point_3 Point_3; 01060 typedef typename K::Tetrahedron_3 Tetrahedron_3; 01061 typedef typename K::Iso_cuboid_3 Iso_cuboid_3; 01062 public: 01063 typedef FT result_type; 01064 01065 result_type 01066 operator()(const Point_3& p0, const Point_3& p1, 01067 const Point_3& p2, const Point_3& p3) const 01068 { 01069 return determinant<FT>(p1.x()-p0.x(), p1.y()-p0.y(), p1.z()-p0.z(), 01070 p2.x()-p0.x(), p2.y()-p0.y(), p2.z()-p0.z(), 01071 p3.x()-p0.x(), p3.y()-p0.y(), p3.z()-p0.z())/6; 01072 } 01073 01074 result_type 01075 operator()( const Tetrahedron_3& t ) const 01076 { 01077 return this->operator()(t.vertex(0), t.vertex(1), 01078 t.vertex(2), t.vertex(3)); 01079 } 01080 01081 result_type 01082 operator()( const Iso_cuboid_3& c ) const 01083 { return c.rep().volume(); } 01084 }; 01085 01086 01087 template <typename K> 01088 class Compute_x_2 : Has_qrt 01089 { 01090 typedef typename K::FT FT; 01091 typedef typename K::Point_2 Point_2; 01092 typedef typename K::Vector_2 Vector_2; 01093 01094 public: 01095 typedef FT result_type; 01096 01097 const result_type & 01098 operator()(const Point_2& p) const 01099 { 01100 return p.rep().x(); 01101 } 01102 01103 const result_type & 01104 operator()(const Vector_2& v) const 01105 { 01106 return v.rep().x(); 01107 } 01108 }; 01109 01110 template <typename K> 01111 class Compute_x_3 : Has_qrt 01112 { 01113 typedef typename K::FT FT; 01114 typedef typename K::Point_3 Point_3; 01115 typedef typename K::Vector_3 Vector_3; 01116 01117 public: 01118 typedef FT result_type; 01119 01120 const result_type & 01121 operator()(const Point_3& p) const 01122 { 01123 return p.rep().x(); 01124 } 01125 01126 const result_type & 01127 operator()(const Vector_3& v) const 01128 { 01129 return v.rep().x(); 01130 } 01131 }; 01132 01133 01134 template <typename K> 01135 class Compute_y_2 : Has_qrt 01136 { 01137 typedef typename K::FT FT; 01138 typedef typename K::Point_2 Point_2; 01139 typedef typename K::Vector_2 Vector_2; 01140 01141 public: 01142 typedef FT result_type; 01143 01144 const result_type & 01145 operator()(const Point_2& p) const 01146 { 01147 return p.rep().y(); 01148 } 01149 01150 const result_type & 01151 operator()(const Vector_2& v) const 01152 { 01153 return v.rep().y(); 01154 } 01155 }; 01156 01157 01158 template <typename K> 01159 class Compute_y_3 : Has_qrt 01160 { 01161 typedef typename K::FT FT; 01162 typedef typename K::Point_3 Point_3; 01163 typedef typename K::Vector_3 Vector_3; 01164 01165 public: 01166 typedef FT result_type; 01167 01168 const result_type & 01169 operator()(const Point_3& p) const 01170 { 01171 return p.rep().y(); 01172 } 01173 01174 const result_type & 01175 operator()(const Vector_3& v) const 01176 { 01177 return v.rep().y(); 01178 } 01179 }; 01180 01181 template <typename K> 01182 class Compute_z_3 : Has_qrt 01183 { 01184 typedef typename K::FT FT; 01185 typedef typename K::Point_3 Point_3; 01186 typedef typename K::Vector_3 Vector_3; 01187 01188 public: 01189 typedef FT result_type; 01190 01191 const result_type & 01192 operator()(const Point_3& p) const 01193 { 01194 return p.rep().z(); 01195 } 01196 01197 const result_type & 01198 operator()(const Vector_3& v) const 01199 { 01200 return v.rep().z(); 01201 } 01202 }; 01203 01204 01205 01206 template <typename K> 01207 class Compute_dx_2 : public Has_qrt 01208 { 01209 typedef typename K::FT FT; 01210 typedef typename K::Direction_2 Direction_2; 01211 01212 public: 01213 typedef FT result_type; 01214 01215 const result_type & 01216 operator()(const Direction_2& d) const 01217 { 01218 return d.rep().dx(); 01219 } 01220 }; 01221 01222 template <typename K> 01223 class Compute_dx_3 : public Has_qrt 01224 { 01225 typedef typename K::FT FT; 01226 typedef typename K::Direction_3 Direction_3; 01227 01228 public: 01229 typedef FT result_type; 01230 01231 const result_type & 01232 operator()(const Direction_3& d) const 01233 { 01234 return d.rep().dx(); 01235 } 01236 }; 01237 01238 template <typename K> 01239 class Compute_dy_2 : public Has_qrt 01240 { 01241 typedef typename K::FT FT; 01242 typedef typename K::Direction_2 Direction_2; 01243 01244 public: 01245 typedef FT result_type; 01246 01247 const result_type & 01248 operator()(const Direction_2& d) const 01249 { 01250 return d.rep().dy(); 01251 } 01252 }; 01253 01254 template <typename K> 01255 class Compute_dy_3 : public Has_qrt 01256 { 01257 typedef typename K::FT FT; 01258 typedef typename K::Direction_3 Direction_3; 01259 01260 public: 01261 typedef FT result_type; 01262 01263 const result_type & 01264 operator()(const Direction_3& d) const 01265 { 01266 return d.rep().dy(); 01267 } 01268 }; 01269 01270 template <typename K> 01271 class Compute_dz_3 : public Has_qrt 01272 { 01273 typedef typename K::FT FT; 01274 typedef typename K::Direction_3 Direction_3; 01275 01276 public: 01277 typedef FT result_type; 01278 01279 const result_type & 01280 operator()(const Direction_3& d) const 01281 { 01282 return d.rep().dz(); 01283 } 01284 }; 01285 01286 template <typename K> 01287 class Compute_hx_2 : public Has_qrt 01288 { 01289 typedef typename K::FT FT; 01290 typedef typename K::Point_2 Point_2; 01291 typedef typename K::Vector_2 Vector_2; 01292 01293 public: 01294 typedef FT result_type; 01295 01296 const result_type & 01297 operator()(const Point_2& p) const 01298 { 01299 return p.rep().hx(); 01300 } 01301 01302 const result_type & 01303 operator()(const Vector_2& v) const 01304 { 01305 return v.rep().hx(); 01306 } 01307 }; 01308 01309 template <typename K> 01310 class Compute_hx_3 : public Has_qrt 01311 { 01312 typedef typename K::FT FT; 01313 typedef typename K::Point_3 Point_3; 01314 typedef typename K::Vector_3 Vector_3; 01315 01316 public: 01317 typedef FT result_type; 01318 01319 const result_type & 01320 operator()(const Point_3& p) const 01321 { 01322 return p.rep().hx(); 01323 } 01324 01325 const result_type & 01326 operator()(const Vector_3& v) const 01327 { 01328 return v.rep().hx(); 01329 } 01330 }; 01331 01332 template <typename K> 01333 class Compute_hy_2 : public Has_qrt 01334 { 01335 typedef typename K::FT FT; 01336 typedef typename K::Point_2 Point_2; 01337 typedef typename K::Vector_2 Vector_2; 01338 01339 public: 01340 typedef FT result_type; 01341 01342 const result_type & 01343 operator()(const Point_2& p) const 01344 { 01345 return p.rep().hy(); 01346 } 01347 01348 const result_type & 01349 operator()(const Vector_2& v) const 01350 { 01351 return v.rep().hy(); 01352 } 01353 }; 01354 01355 template <typename K> 01356 class Compute_hy_3 : public Has_qrt 01357 { 01358 typedef typename K::FT FT; 01359 typedef typename K::Point_3 Point_3; 01360 typedef typename K::Vector_3 Vector_3; 01361 01362 public: 01363 typedef FT result_type; 01364 01365 const result_type & 01366 operator()(const Point_3& p) const 01367 { 01368 return p.rep().hy(); 01369 } 01370 01371 const result_type & 01372 operator()(const Vector_3& v) const 01373 { 01374 return v.rep().hy(); 01375 } 01376 }; 01377 01378 template <typename K> 01379 class Compute_hz_3 : public Has_qrt 01380 { 01381 typedef typename K::FT FT; 01382 typedef typename K::Point_3 Point_3; 01383 typedef typename K::Vector_3 Vector_3; 01384 01385 public: 01386 typedef FT result_type; 01387 01388 const result_type & 01389 operator()(const Point_3& p) const 01390 { 01391 return p.rep().hz(); 01392 } 01393 01394 const result_type & 01395 operator()(const Vector_3& v) const 01396 { 01397 return v.rep().hz(); 01398 } 01399 }; 01400 01401 template <typename K> 01402 class Compute_hw_2 : public Has_qrt 01403 { 01404 typedef typename K::FT FT; 01405 typedef typename K::Point_2 Point_2; 01406 typedef typename K::Vector_2 Vector_2; 01407 01408 public: 01409 typedef FT result_type; 01410 01411 const result_type & 01412 operator()(const Point_2& p) const 01413 { 01414 return p.rep().hw(); 01415 } 01416 01417 const result_type & 01418 operator()(const Vector_2& v) const 01419 { 01420 return v.rep().hw(); 01421 } 01422 }; 01423 01424 template <typename K> 01425 class Compute_hw_3 : public Has_qrt 01426 { 01427 typedef typename K::FT FT; 01428 typedef typename K::Point_3 Point_3; 01429 typedef typename K::Vector_3 Vector_3; 01430 01431 public: 01432 typedef FT result_type; 01433 01434 const result_type & 01435 operator()(const Point_3& p) const 01436 { 01437 return p.rep().hw(); 01438 } 01439 01440 const result_type & 01441 operator()(const Vector_3& v) const 01442 { 01443 return v.rep().hw(); 01444 } 01445 }; 01446 01447 01448 template <typename K> 01449 class Compute_xmin_2 : public Has_qrt 01450 { 01451 typedef typename K::FT FT; 01452 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 01453 01454 public: 01455 typedef FT result_type; 01456 01457 const result_type & 01458 operator()(const Iso_rectangle_2& r) const 01459 { 01460 return (r.min)().x(); 01461 } 01462 }; 01463 01464 template <typename K> 01465 class Compute_xmax_2 : public Has_qrt 01466 { 01467 typedef typename K::FT FT; 01468 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 01469 01470 public: 01471 typedef FT result_type; 01472 01473 const result_type & 01474 operator()(const Iso_rectangle_2& r) const 01475 { 01476 return (r.max)().x(); 01477 } 01478 }; 01479 01480 template <typename K> 01481 class Compute_ymin_2 : public Has_qrt 01482 { 01483 typedef typename K::FT FT; 01484 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 01485 01486 public: 01487 typedef FT result_type; 01488 01489 const result_type & 01490 operator()(const Iso_rectangle_2& r) const 01491 { 01492 return (r.min)().y(); 01493 } 01494 }; 01495 01496 template <typename K> 01497 class Compute_ymax_2 : public Has_qrt 01498 { 01499 typedef typename K::FT FT; 01500 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 01501 01502 public: 01503 typedef FT result_type; 01504 01505 const result_type & 01506 operator()(const Iso_rectangle_2& r) const 01507 { 01508 return (r.max)().y(); 01509 } 01510 }; 01511 01512 01513 template <typename K> 01514 class Construct_barycenter_2 01515 { 01516 typedef typename K::FT FT; 01517 typedef typename K::Point_2 Point_2; 01518 public: 01519 typedef Point_2 result_type; 01520 01521 result_type 01522 operator()(const Point_2& p1, const FT&w1, const Point_2& p2) const 01523 { 01524 typename K::Construct_point_2 construct_point_2; 01525 FT x, y; 01526 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), x, y); 01527 return construct_point_2(x, y); 01528 } 01529 01530 result_type 01531 operator()(const Point_2& p1, const FT& w1, const Point_2& p2, const FT& w2) const 01532 { 01533 typename K::Construct_point_2 construct_point_2; 01534 FT x, y; 01535 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), w2, x, y); 01536 return construct_point_2(x, y); 01537 } 01538 01539 result_type 01540 operator()(const Point_2& p1, const FT& w1, const Point_2& p2, const FT& w2, 01541 const Point_2& p3) const 01542 { 01543 typename K::Construct_point_2 construct_point_2; 01544 FT x, y; 01545 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), w2, p3.x(), p3.y(), x, y); 01546 return construct_point_2(x, y); 01547 } 01548 01549 result_type 01550 operator()(const Point_2& p1, const FT& w1, const Point_2& p2, const FT& w2, 01551 const Point_2& p3, const FT& w3) const 01552 { 01553 typename K::Construct_point_2 construct_point_2; 01554 FT x, y; 01555 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), w2, p3.x(), p3.y(), w3, x, y); 01556 return construct_point_2(x, y); 01557 } 01558 01559 result_type 01560 operator()(const Point_2& p1, const FT& w1, const Point_2& p2, const FT& w2, 01561 const Point_2& p3, const FT& w3, const Point_2& p4) const 01562 { 01563 typename K::Construct_point_2 construct_point_2; 01564 FT x, y; 01565 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), w2, p3.x(), p3.y(), w3, p4.x(), p4.y(), x, y); 01566 return construct_point_2(x, y); 01567 } 01568 01569 result_type 01570 operator()(const Point_2& p1, const FT& w1, const Point_2& p2, const FT& w2, 01571 const Point_2& p3, const FT& w3, const Point_2& p4, const FT& w4) const 01572 { 01573 typename K::Construct_point_2 construct_point_2; 01574 FT x, y; 01575 barycenterC2(p1.x(), p1.y(), w1, p2.x(), p2.y(), w2, p3.x(), p3.y(), w3, p4.x(), p4.y(), w4, x, y); 01576 return construct_point_2(x, y); 01577 } 01578 01579 }; 01580 01581 template <typename K> 01582 class Construct_barycenter_3 01583 { 01584 typedef typename K::FT FT; 01585 typedef typename K::Point_3 Point_3; 01586 public: 01587 typedef Point_3 result_type; 01588 01589 result_type 01590 operator()(const Point_3& p1, const FT&w1, const Point_3& p2) const 01591 { 01592 typename K::Construct_point_3 construct_point_3; 01593 FT x, y, z; 01594 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), x, y, z); 01595 return construct_point_3(x, y, z); 01596 } 01597 01598 result_type 01599 operator()(const Point_3& p1, const FT& w1, const Point_3& p2, const FT& w2) const 01600 { 01601 typename K::Construct_point_3 construct_point_3; 01602 FT x, y, z; 01603 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), w2, x, y, z); 01604 return construct_point_3(x, y, z); 01605 } 01606 01607 result_type 01608 operator()(const Point_3& p1, const FT& w1, const Point_3& p2, const FT& w2, 01609 const Point_3& p3) const 01610 { 01611 typename K::Construct_point_3 construct_point_3; 01612 FT x, y, z; 01613 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), w2, p3.x(), p3.y(), p3.z(), x, y, z); 01614 return construct_point_3(x, y, z); 01615 } 01616 01617 result_type 01618 operator()(const Point_3& p1, const FT& w1, const Point_3& p2, const FT& w2, 01619 const Point_3& p3, const FT& w3) const 01620 { 01621 typename K::Construct_point_3 construct_point_3; 01622 FT x, y, z; 01623 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), w2, 01624 p3.x(), p3.y(), p3.z(), w3, x, y, z); 01625 return construct_point_3(x, y, z); 01626 } 01627 01628 result_type 01629 operator()(const Point_3& p1, const FT& w1, const Point_3& p2, const FT& w2, 01630 const Point_3& p3, const FT& w3, const Point_3& p4) const 01631 { 01632 typename K::Construct_point_3 construct_point_3; 01633 FT x, y, z; 01634 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), w2, 01635 p3.x(), p3.y(), p3.z(), w3, p4.x(), p4.y(), p4.z(), x, y, z); 01636 return construct_point_3(x, y, z); 01637 } 01638 01639 result_type 01640 operator()(const Point_3& p1, const FT& w1, const Point_3& p2, const FT& w2, 01641 const Point_3& p3, const FT& w3, const Point_3& p4, const FT& w4) const 01642 { 01643 typename K::Construct_point_3 construct_point_3; 01644 FT x, y, z; 01645 barycenterC3(p1.x(), p1.y(), p1.z(), w1, p2.x(), p2.y(), p2.z(), w2, 01646 p3.x(), p3.y(), p3.z(), w3, p4.x(), p4.y(), p4.z(), w4, x, y, z); 01647 return construct_point_3(x, y, z); 01648 } 01649 01650 }; 01651 01652 01653 template <typename K> 01654 class Construct_base_vector_3 01655 { 01656 typedef typename K::Vector_3 Vector_3; 01657 typedef typename K::Plane_3 Plane_3; 01658 typedef typename K::FT FT; 01659 typedef typename K::Construct_cross_product_vector_3 01660 Construct_cross_product_vector_3; 01661 typedef typename K::Construct_orthogonal_vector_3 01662 Construct_orthogonal_vector_3; 01663 Construct_cross_product_vector_3 cp; 01664 Construct_orthogonal_vector_3 co; 01665 public: 01666 typedef Vector_3 result_type; 01667 01668 Construct_base_vector_3() {} 01669 Construct_base_vector_3(const Construct_cross_product_vector_3& cp_, 01670 const Construct_orthogonal_vector_3& co_) 01671 : cp(cp_), co(co_) 01672 {} 01673 01674 result_type 01675 operator()( const Plane_3& h, int index ) const 01676 { 01677 if (index == 1) { 01678 if ( CGAL_NTS is_zero(h.a()) ) // parallel to x-axis 01679 return Vector_3(FT(1), FT(0), FT(0)); 01680 01681 if ( CGAL_NTS is_zero(h.b()) ) // parallel to y-axis 01682 return Vector_3(FT(0), FT(1), FT(0)); 01683 01684 if ( CGAL_NTS is_zero(h.c()) ) // parallel to z-axis 01685 return Vector_3(FT(0), FT(0), FT(1)); 01686 01687 return Vector_3(-h.b(), h.a(), FT(0)); 01688 } else { 01689 return cp(co(h), this->operator()(h,1)); 01690 } 01691 } 01692 }; 01693 01694 01695 template <typename K> 01696 class Construct_bbox_2 01697 { 01698 typedef typename K::Point_2 Point_2; 01699 typedef typename K::Segment_2 Segment_2; 01700 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 01701 typedef typename K::Triangle_2 Triangle_2; 01702 typedef typename K::Circle_2 Circle_2; 01703 public: 01704 typedef Bbox_2 result_type; 01705 01706 result_type 01707 operator()(const Point_2& p) const 01708 { 01709 std::pair<double,double> xp = CGAL_NTS to_interval(p.x()); 01710 std::pair<double,double> yp = CGAL_NTS to_interval(p.y()); 01711 return Bbox_2(xp.first, yp.first, xp.second, yp.second); 01712 } 01713 01714 result_type 01715 operator()(const Segment_2& s) const 01716 { return s.source().bbox() + s.target().bbox(); } 01717 01718 result_type 01719 operator()(const Triangle_2& t) const 01720 { 01721 typename K::Construct_bbox_2 construct_bbox_2; 01722 return construct_bbox_2(t.vertex(0)) 01723 + construct_bbox_2(t.vertex(1)) 01724 + construct_bbox_2(t.vertex(2)); 01725 } 01726 01727 result_type 01728 operator()(const Iso_rectangle_2& r) const 01729 { 01730 typename K::Construct_bbox_2 construct_bbox_2; 01731 return construct_bbox_2((r.min)()) + construct_bbox_2((r.max)()); 01732 } 01733 01734 result_type 01735 operator()(const Circle_2& c) const 01736 { 01737 typename K::Construct_bbox_2 construct_bbox_2; 01738 Bbox_2 b = construct_bbox_2(c.center()); 01739 01740 Interval_nt<> x (b.xmin(), b.xmax()); 01741 Interval_nt<> y (b.ymin(), b.ymax()); 01742 01743 Interval_nt<> sqr = CGAL_NTS to_interval(c.squared_radius()); 01744 Interval_nt<> r = CGAL::sqrt(sqr); 01745 Interval_nt<> minx = x-r; 01746 Interval_nt<> maxx = x+r; 01747 Interval_nt<> miny = y-r; 01748 Interval_nt<> maxy = y+r; 01749 01750 return Bbox_2(minx.inf(), miny.inf(), maxx.sup(), maxy.sup()); 01751 } 01752 }; 01753 01754 01755 template <typename K> 01756 class Construct_bbox_3 01757 { 01758 typedef typename K::Point_3 Point_3; 01759 typedef typename K::Segment_3 Segment_3; 01760 typedef typename K::Iso_cuboid_3 Iso_cuboid_3; 01761 typedef typename K::Triangle_3 Triangle_3; 01762 typedef typename K::Tetrahedron_3 Tetrahedron_3; 01763 typedef typename K::Sphere_3 Sphere_3; 01764 typedef typename K::Circle_3 Circle_3; 01765 public: 01766 typedef Bbox_3 result_type; 01767 01768 Bbox_3 01769 operator()(const Point_3& p) const 01770 { 01771 std::pair<double,double> xp = CGAL_NTS to_interval(p.x()); 01772 std::pair<double,double> yp = CGAL_NTS to_interval(p.y()); 01773 std::pair<double,double> zp = CGAL_NTS to_interval(p.z()); 01774 return Bbox_3(xp.first, yp.first, zp.first, 01775 xp.second, yp.second, zp.second); 01776 } 01777 01778 Bbox_3 01779 operator()(const Segment_3& s) const 01780 { return s.source().bbox() + s.target().bbox(); } 01781 01782 Bbox_3 01783 operator()(const Triangle_3& t) const 01784 { 01785 typename K::Construct_bbox_3 construct_bbox_3; 01786 return construct_bbox_3(t.vertex(0)) 01787 + construct_bbox_3(t.vertex(1)) 01788 + construct_bbox_3(t.vertex(2)); 01789 } 01790 01791 Bbox_3 01792 operator()(const Iso_cuboid_3& r) const 01793 { 01794 typename K::Construct_bbox_3 construct_bbox_3; 01795 return construct_bbox_3((r.min)()) + construct_bbox_3((r.max)()); 01796 } 01797 01798 Bbox_3 01799 operator()(const Tetrahedron_3& t) const 01800 { 01801 typename K::Construct_bbox_3 construct_bbox_3; 01802 return construct_bbox_3(t.vertex(0)) + construct_bbox_3(t.vertex(1)) 01803 + construct_bbox_3(t.vertex(2)) + construct_bbox_3(t.vertex(3)); 01804 } 01805 01806 Bbox_3 01807 operator()(const Sphere_3& s) const 01808 { 01809 typename K::Construct_bbox_3 construct_bbox_3; 01810 Bbox_3 b = construct_bbox_3(s.center()); 01811 01812 Interval_nt<> x (b.xmin(), b.xmax()); 01813 Interval_nt<> y (b.ymin(), b.ymax()); 01814 Interval_nt<> z (b.zmin(), b.zmax()); 01815 01816 Interval_nt<> sqr = CGAL_NTS to_interval(s.squared_radius()); 01817 Interval_nt<> r = CGAL::sqrt(sqr); 01818 Interval_nt<> minx = x-r; 01819 Interval_nt<> maxx = x+r; 01820 Interval_nt<> miny = y-r; 01821 Interval_nt<> maxy = y+r; 01822 Interval_nt<> minz = z-r; 01823 Interval_nt<> maxz = z+r; 01824 01825 return Bbox_3(minx.inf(), miny.inf(), minz.inf(), 01826 maxx.sup(), maxy.sup(), maxz.sup()); 01827 } 01828 01829 Bbox_3 01830 operator()(const Circle_3& c) const 01831 { return c.rep().bbox(); } 01832 01833 }; 01834 01835 01836 template <typename K> 01837 class Construct_bisector_2 01838 { 01839 typedef typename K::FT FT; 01840 typedef typename K::Point_2 Point_2; 01841 typedef typename K::Line_2 Line_2; 01842 public: 01843 typedef Line_2 result_type; 01844 01845 result_type 01846 operator()(const Point_2& p, const Point_2& q) const 01847 { 01848 FT a, b, c; 01849 bisector_of_pointsC2(p.x(), p.y(), q.x(), q.y(), a, b, c); 01850 return Line_2(a, b, c); 01851 } 01852 01853 result_type 01854 operator()(const Line_2& p, const Line_2& q) const 01855 { 01856 FT a, b, c; 01857 bisector_of_linesC2(p.a(), p.b(), p.c(), 01858 q.a(), q.b(), q.c(), 01859 a, b, c); 01860 return Line_2(a, b, c); 01861 } 01862 }; 01863 01864 template <typename K> 01865 class Construct_bisector_3 01866 { 01867 typedef typename K::FT FT; 01868 typedef typename K::Point_3 Point_3; 01869 typedef typename K::Plane_3 Plane_3; 01870 public: 01871 typedef Plane_3 result_type; 01872 01873 result_type 01874 operator()(const Point_3& p, const Point_3& q) const 01875 { 01876 FT a, b, c, d; 01877 bisector_of_pointsC3(p.x(), p.y(), p.z(), 01878 q.x(), q.y(), q.z(), 01879 a, b, c, d); 01880 return Plane_3(a, b, c, d); 01881 } 01882 01883 result_type 01884 operator()(const Plane_3& p, const Plane_3& q) const 01885 { 01886 FT a, b, c, d; 01887 bisector_of_planesC3(p.a(), p.b(), p.c(), p.d(), 01888 q.a(), q.b(), q.c(), q.d(), 01889 a, b, c, d); 01890 return Plane_3(a, b, c, d); 01891 } 01892 }; 01893 01894 template <typename K> 01895 class Construct_centroid_2 01896 { 01897 typedef typename K::FT FT; 01898 typedef typename K::Point_2 Point_2; 01899 typedef typename K::Triangle_2 Triangle_2; 01900 public: 01901 typedef Point_2 result_type; 01902 01903 result_type 01904 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 01905 { 01906 typename K::Construct_point_2 construct_point_2; 01907 FT x, y; 01908 centroidC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), x, y); 01909 return construct_point_2(x, y); 01910 } 01911 01912 result_type 01913 operator()(const Triangle_2& t) const 01914 { 01915 return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2)); 01916 } 01917 01918 result_type 01919 operator()(const Point_2& p, const Point_2& q, 01920 const Point_2& r, const Point_2& s) const 01921 { 01922 typename K::Construct_point_2 construct_point_2; 01923 FT x, y; 01924 centroidC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), s.x(), s.y(), x, y); 01925 return construct_point_2(x, y); 01926 } 01927 }; 01928 01929 template <typename K> 01930 class Construct_centroid_3 01931 { 01932 typedef typename K::FT FT; 01933 typedef typename K::Point_3 Point_3; 01934 typedef typename K::Triangle_3 Triangle_3; 01935 typedef typename K::Tetrahedron_3 Tetrahedron_3; 01936 public: 01937 typedef Point_3 result_type; 01938 01939 result_type 01940 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 01941 { 01942 typename K::Construct_point_3 construct_point_3; 01943 FT x, y, z; 01944 centroidC3(p.x(), p.y(), p.z(), 01945 q.x(), q.y(), q.z(), 01946 r.x(), r.y(), r.z(), 01947 x, y, z); 01948 return construct_point_3(x, y, z); 01949 } 01950 01951 result_type 01952 operator()(const Point_3& p, const Point_3& q, 01953 const Point_3& r, const Point_3& s) const 01954 { 01955 typename K::Construct_point_3 construct_point_3; 01956 FT x, y, z; 01957 centroidC3(p.x(), p.y(), p.z(), 01958 q.x(), q.y(), q.z(), 01959 r.x(), r.y(), r.z(), 01960 s.x(), s.y(), s.z(), 01961 x, y, z); 01962 return construct_point_3(x, y, z); 01963 } 01964 01965 result_type 01966 operator()(const Triangle_3& t) const 01967 { 01968 return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2)); 01969 } 01970 01971 result_type 01972 operator()(const Tetrahedron_3& t) const 01973 { 01974 return this->operator()(t.vertex(0), t.vertex(1), 01975 t.vertex(2), t.vertex(3)); 01976 } 01977 }; 01978 01979 template <typename K> 01980 class Construct_circumcenter_2 01981 { 01982 typedef typename K::Point_2 Point_2; 01983 typedef typename K::Triangle_2 Triangle_2; 01984 public: 01985 typedef Point_2 result_type; 01986 01987 Point_2 01988 operator()(const Point_2& p, const Point_2& q) const 01989 { 01990 typename K::Construct_midpoint_2 construct_midpoint_2; 01991 return construct_midpoint_2(p, q); 01992 } 01993 01994 result_type 01995 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 01996 { 01997 typename K::Construct_point_2 construct_point_2; 01998 typedef typename K::FT FT; 01999 FT x, y; 02000 circumcenterC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), x, y); 02001 return construct_point_2(x, y); 02002 } 02003 02004 result_type 02005 operator()(const Triangle_2& t) const 02006 { 02007 return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2)); 02008 } 02009 }; 02010 02011 template <typename K> 02012 class Construct_circumcenter_3 02013 { 02014 typedef typename K::FT FT; 02015 typedef typename K::Tetrahedron_3 Tetrahedron_3; 02016 typedef typename K::Triangle_3 Triangle_3; 02017 typedef typename K::Point_3 Point_3; 02018 public: 02019 typedef Point_3 result_type; 02020 02021 Point_3 02022 operator()(const Point_3& p, const Point_3& q) const 02023 { 02024 typename K::Construct_midpoint_3 construct_midpoint_3; 02025 return construct_midpoint_3(p, q); 02026 } 02027 02028 Point_3 02029 operator()(const Point_3& p, const Point_3& q, const Point_3& s) const 02030 { 02031 typename K::Construct_point_3 construct_point_3; 02032 // Translate s to origin to simplify the expression. 02033 FT psx = p.x()-s.x(); 02034 FT psy = p.y()-s.y(); 02035 FT psz = p.z()-s.z(); 02036 FT ps2 = CGAL_NTS square(psx) + CGAL_NTS square(psy) + CGAL_NTS square(psz); 02037 FT qsx = q.x()-s.x(); 02038 FT qsy = q.y()-s.y(); 02039 FT qsz = q.z()-s.z(); 02040 FT qs2 = CGAL_NTS square(qsx) + CGAL_NTS square(qsy) + CGAL_NTS square(qsz); 02041 FT rsx = psy*qsz-psz*qsy; 02042 FT rsy = psz*qsx-psx*qsz; 02043 FT rsz = psx*qsy-psy*qsx; 02044 02045 // The following determinants can be developped and simplified. 02046 // 02047 // FT num_x = determinant(psy,psz,ps2, 02048 // qsy,qsz,qs2, 02049 // rsy,rsz,0); 02050 // FT num_y = determinant(psx,psz,ps2, 02051 // qsx,qsz,qs2, 02052 // rsx,rsz,0); 02053 // FT num_z = determinant(psx,psy,ps2, 02054 // qsx,qsy,qs2, 02055 // rsx,rsy,0); 02056 02057 FT num_x = ps2 * determinant(qsy,qsz,rsy,rsz) 02058 - qs2 * determinant(psy,psz,rsy,rsz); 02059 FT num_y = ps2 * determinant(qsx,qsz,rsx,rsz) 02060 - qs2 * determinant(psx,psz,rsx,rsz); 02061 FT num_z = ps2 * determinant(qsx,qsy,rsx,rsy) 02062 - qs2 * determinant(psx,psy,rsx,rsy); 02063 02064 FT den = determinant(psx,psy,psz, 02065 qsx,qsy,qsz, 02066 rsx,rsy,rsz); 02067 02068 CGAL_kernel_assertion( den != 0 ); 02069 FT inv = 1 / (2 * den); 02070 02071 FT x = s.x() + num_x*inv; 02072 FT y = s.y() - num_y*inv; 02073 FT z = s.z() + num_z*inv; 02074 return construct_point_3(x, y, z); 02075 } 02076 02077 Point_3 02078 operator()(const Triangle_3& t) const 02079 { 02080 return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2)); 02081 } 02082 02083 Point_3 02084 operator()(const Point_3& p, const Point_3& q, 02085 const Point_3& r, const Point_3& s) const 02086 { 02087 typename K::Construct_point_3 construct_point_3; 02088 // Translate p to origin to simplify the expression. 02089 FT qpx = q.x()-p.x(); 02090 FT qpy = q.y()-p.y(); 02091 FT qpz = q.z()-p.z(); 02092 FT qp2 = CGAL_NTS square(qpx) + CGAL_NTS square(qpy) + CGAL_NTS square(qpz); 02093 FT rpx = r.x()-p.x(); 02094 FT rpy = r.y()-p.y(); 02095 FT rpz = r.z()-p.z(); 02096 FT rp2 = CGAL_NTS square(rpx) + CGAL_NTS square(rpy) + CGAL_NTS square(rpz); 02097 FT spx = s.x()-p.x(); 02098 FT spy = s.y()-p.y(); 02099 FT spz = s.z()-p.z(); 02100 FT sp2 = CGAL_NTS square(spx) + CGAL_NTS square(spy) + CGAL_NTS square(spz); 02101 02102 FT num_x = determinant(qpy,qpz,qp2, 02103 rpy,rpz,rp2, 02104 spy,spz,sp2); 02105 FT num_y = determinant(qpx,qpz,qp2, 02106 rpx,rpz,rp2, 02107 spx,spz,sp2); 02108 FT num_z = determinant(qpx,qpy,qp2, 02109 rpx,rpy,rp2, 02110 spx,spy,sp2); 02111 FT den = determinant(qpx,qpy,qpz, 02112 rpx,rpy,rpz, 02113 spx,spy,spz); 02114 CGAL_kernel_assertion( ! CGAL_NTS is_zero(den) ); 02115 FT inv = 1 / (2 * den); 02116 02117 FT x = p.x() + num_x*inv; 02118 FT y = p.y() - num_y*inv; 02119 FT z = p.z() + num_z*inv; 02120 return construct_point_3(x, y, z); 02121 } 02122 02123 Point_3 02124 operator()(const Tetrahedron_3& t) const 02125 { 02126 return this->operator()(t.vertex(0), t.vertex(1), 02127 t.vertex(2), t.vertex(3)); 02128 } 02129 }; 02130 02131 template <typename K> 02132 class Construct_cross_product_vector_3 02133 { 02134 typedef typename K::Vector_3 Vector_3; 02135 public: 02136 typedef Vector_3 result_type; 02137 02138 Vector_3 02139 operator()(const Vector_3& v, const Vector_3& w) const 02140 { 02141 return Vector_3(v.y() * w.z() - v.z() * w.y(), 02142 v.z() * w.x() - v.x() * w.z(), 02143 v.x() * w.y() - v.y() * w.x()); 02144 } 02145 }; 02146 02147 template <typename K> 02148 class Construct_lifted_point_3 02149 { 02150 typedef typename K::Point_2 Point_2; 02151 typedef typename K::Point_3 Point_3; 02152 typedef typename K::Plane_3 Plane_3; 02153 typedef typename K::Construct_base_vector_3 Construct_base_vector_3; 02154 typedef typename K::Construct_point_on_3 Construct_point_on_3; 02155 typedef typename K::Construct_scaled_vector_3 Construct_scaled_vector_3; 02156 typedef typename K::Construct_translated_point_3 02157 Construct_translated_point_3; 02158 Construct_base_vector_3 cb; 02159 Construct_point_on_3 cp; 02160 Construct_scaled_vector_3 cs; 02161 Construct_translated_point_3 ct; 02162 public: 02163 typedef Point_3 result_type; 02164 02165 Construct_lifted_point_3() {} 02166 Construct_lifted_point_3(const Construct_base_vector_3& cb_, 02167 const Construct_point_on_3& cp_, 02168 const Construct_scaled_vector_3& cs_, 02169 const Construct_translated_point_3& ct_) 02170 : cb(cb_), cp(cp_), cs(cs_), ct(ct_) 02171 {} 02172 02173 Point_3 02174 operator()(const Plane_3& h, const Point_2& p) const 02175 { 02176 return ct(ct(cp(h), cs(cb(h,1), p.x())), cs(cb(h,2), p.y())); 02177 } 02178 }; 02179 02180 template <typename K> 02181 class Construct_direction_2 02182 { 02183 typedef typename K::Direction_2 Direction_2; 02184 typedef typename Direction_2::Rep Rep; 02185 typedef typename K::Point_2 Point_2; 02186 typedef typename K::Vector_2 Vector_2; 02187 typedef typename K::Line_2 Line_2; 02188 typedef typename K::Ray_2 Ray_2; 02189 typedef typename K::Segment_2 Segment_2; 02190 typedef typename K::RT RT; 02191 02192 public: 02193 typedef Direction_2 result_type; 02194 02195 Rep // Direction_2 02196 operator()(Return_base_tag, const RT& x, const RT& y) const 02197 { return Rep(x, y); } 02198 02199 Rep // Direction_2 02200 operator()(Return_base_tag, const Vector_2& v) const 02201 { 02202 return Rep(v.x(),v.y()); } 02203 02204 Rep // Direction_2 02205 operator()(Return_base_tag, const Line_2& l) const 02206 { return Rep(l.b(), -l.a()); } 02207 02208 Rep // Direction_2 02209 operator()(Return_base_tag, const Point_2& p, const Point_2& q) const 02210 { 02211 return Rep(q.x() - p.x(), q.y() - p.y()); 02212 } 02213 02214 Rep // Direction_2 02215 operator()(Return_base_tag, const Ray_2& r) const 02216 { 02217 return this->operator()(Return_base_tag(), r.source(), r.second_point()); 02218 } 02219 02220 Rep // Direction_2 02221 operator()(Return_base_tag, const Segment_2& s) const 02222 { 02223 return this->operator()(Return_base_tag(), s.source(), s.target()); 02224 } 02225 02226 02227 Direction_2 02228 operator()(const RT& x, const RT& y) const 02229 { return this->operator()(Return_base_tag(), x, y); } 02230 02231 Direction_2 02232 operator()(const Vector_2& v) const 02233 { 02234 return this->operator()(Return_base_tag(), v); } 02235 02236 Direction_2 02237 operator()(const Line_2& l) const 02238 { return this->operator()(Return_base_tag(), l); } 02239 02240 Direction_2 02241 operator()(const Point_2& p, const Point_2& q) const 02242 { 02243 return this->operator()(Return_base_tag(), p, q); 02244 } 02245 02246 Direction_2 02247 operator()(const Ray_2& r) const 02248 { 02249 return this->operator()(Return_base_tag(), r); 02250 } 02251 02252 Direction_2 02253 operator()(const Segment_2& s) const 02254 { 02255 return this->operator()(Return_base_tag(), s); 02256 } 02257 }; 02258 02259 template <typename K> 02260 class Construct_direction_3 02261 { 02262 typedef typename K::Direction_3 Direction_3; 02263 typedef typename K::Vector_3 Vector_3; 02264 typedef typename K::Line_3 Line_3; 02265 typedef typename K::Ray_3 Ray_3; 02266 typedef typename K::Segment_3 Segment_3; 02267 typedef typename K::RT RT; 02268 typedef typename Direction_3::Rep Rep; 02269 public: 02270 typedef Direction_3 result_type; 02271 02272 Rep // Direction_3 02273 operator()(Return_base_tag, const RT& x, const RT& y, const RT& z) const 02274 { return Rep(x, y, z); } 02275 02276 Rep // Direction_3 02277 operator()(Return_base_tag, const Vector_3& v) const 02278 { return Rep(v); } 02279 02280 Rep // Direction_3 02281 operator()(Return_base_tag, const Line_3& l) const 02282 { return Rep(l); } 02283 02284 Rep // Direction_3 02285 operator()(Return_base_tag, const Ray_3& r) const 02286 { return Rep(r); } 02287 02288 Rep // Direction_3 02289 operator()(Return_base_tag, const Segment_3& s) const 02290 { return Rep(s); } 02291 02292 02293 Direction_3 02294 operator()(const RT& x, const RT& y, const RT& z) const 02295 { return this->operator()(Return_base_tag(), x, y, z); } 02296 02297 Direction_3 02298 operator()(const Vector_3& v) const 02299 { return this->operator()(Return_base_tag(), v); } 02300 02301 Direction_3 02302 operator()(const Line_3& l) const 02303 { return this->operator()(Return_base_tag(), l); } 02304 02305 Direction_3 02306 operator()(const Ray_3& r) const 02307 { return this->operator()(Return_base_tag(), r); } 02308 02309 Direction_3 02310 operator()(const Segment_3& s) const 02311 { return this->operator()(Return_base_tag(), s); } 02312 }; 02313 02314 template <typename K> 02315 class Construct_equidistant_line_3 02316 { 02317 typedef typename K::FT FT; 02318 typedef typename K::Point_3 Point_3; 02319 typedef typename K::Vector_3 Vector_3; 02320 typedef typename K::Line_3 Line_3; 02321 typedef typename Line_3::Rep Rep; 02322 public: 02323 typedef Line_3 result_type; 02324 02325 Line_3 02326 operator()( const Point_3& p, const Point_3& q, const Point_3& s) const 02327 { 02328 CGAL_kernel_precondition(! collinear(p, q, s)); 02329 02330 // Translate s to origin to simplify the expression. 02331 FT psx = p.x()-s.x(); 02332 FT psy = p.y()-s.y(); 02333 FT psz = p.z()-s.z(); 02334 FT ps2 = CGAL_NTS square(psx) + CGAL_NTS square(psy) + CGAL_NTS square(psz); 02335 FT qsx = q.x()-s.x(); 02336 FT qsy = q.y()-s.y(); 02337 FT qsz = q.z()-s.z(); 02338 FT qs2 = CGAL_NTS square(qsx) + CGAL_NTS square(qsy) + CGAL_NTS square(qsz); 02339 FT rsx = psy*qsz-psz*qsy; 02340 FT rsy = psz*qsx-psx*qsz; 02341 FT rsz = psx*qsy-psy*qsx; 02342 02343 // The following determinants can be developped and simplified. 02344 // 02345 // FT num_x = determinant(psy,psz,ps2, 02346 // qsy,qsz,qs2, 02347 // rsy,rsz,0); 02348 // FT num_y = determinant(psx,psz,ps2, 02349 // qsx,qsz,qs2, 02350 // rsx,rsz,0); 02351 // FT num_z = determinant(psx,psy,ps2, 02352 // qsx,qsy,qs2, 02353 // rsx,rsy,0); 02354 02355 FT num_x = ps2 * determinant(qsy,qsz,rsy,rsz) 02356 - qs2 * determinant(psy,psz,rsy,rsz); 02357 FT num_y = ps2 * determinant(qsx,qsz,rsx,rsz) 02358 - qs2 * determinant(psx,psz,rsx,rsz); 02359 FT num_z = ps2 * determinant(qsx,qsy,rsx,rsy) 02360 - qs2 * determinant(psx,psy,rsx,rsy); 02361 02362 FT den = determinant(psx,psy,psz, 02363 qsx,qsy,qsz, 02364 rsx,rsy,rsz); 02365 02366 CGAL_kernel_assertion( den != 0 ); 02367 FT inv = 1 / (2 * den); 02368 02369 FT x = s.x() + num_x*inv; 02370 FT y = s.y() - num_y*inv; 02371 FT z = s.z() + num_z*inv; 02372 return Rep(Point_3(x, y, z), Vector_3(rsx, rsy, rsz)); 02373 } 02374 02375 }; 02376 02377 template <typename K> 02378 class Construct_iso_rectangle_2 02379 { 02380 typedef typename K::RT RT; 02381 typedef typename K::FT FT; 02382 typedef typename K::Point_2 Point_2; 02383 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 02384 typedef typename Iso_rectangle_2::Rep Rep; 02385 02386 public: 02387 typedef Iso_rectangle_2 result_type; 02388 02389 Rep // Iso_rectangle_2 02390 operator()(Return_base_tag, const Point_2& p, const Point_2& q, int) const 02391 { 02392 // I have to remove the assertions, because of Cartesian_converter. 02393 // CGAL_kernel_assertion(p.x()<=q.x()); 02394 // CGAL_kernel_assertion(p.y()<=q.y()); 02395 return Rep(p, q, 0); 02396 } 02397 02398 Rep // Iso_rectangle_2 02399 operator()(Return_base_tag, const Point_2& p, const Point_2& q) const 02400 { 02401 FT minx, maxx, miny, maxy; 02402 if (p.x() < q.x()) { minx = p.x(); maxx = q.x(); } 02403 else { minx = q.x(); maxx = p.x(); } 02404 if (p.y() < q.y()) { miny = p.y(); maxy = q.y(); } 02405 else { miny = q.y(); maxy = p.y(); } 02406 02407 return Rep(Point_2(minx, miny), 02408 Point_2(maxx, maxy), 0); 02409 } 02410 02411 Rep // Iso_rectangle_2 02412 operator()(Return_base_tag, const Point_2 &left, const Point_2 &right, 02413 const Point_2 &bottom, const Point_2 &top) const 02414 { 02415 CGAL_kernel_assertion_code(typename K::Less_x_2 less_x;) 02416 CGAL_kernel_assertion_code(typename K::Less_y_2 less_y;) 02417 CGAL_kernel_assertion(!less_x(right, left)); 02418 CGAL_kernel_assertion(!less_y(top, bottom)); 02419 return Rep(Point_2(left.x(), bottom.y()), 02420 Point_2(right.x(), top.y()), 0); 02421 } 02422 02423 Rep // Iso_rectangle_2 02424 operator()(Return_base_tag, const RT& min_hx, const RT& min_hy, 02425 const RT& max_hx, const RT& max_hy) const 02426 { 02427 CGAL_kernel_precondition(min_hx <= max_hx); 02428 CGAL_kernel_precondition(min_hy <= max_hy); 02429 return Rep(Point_2(min_hx, min_hy), 02430 Point_2(max_hx, max_hy), 0); 02431 } 02432 02433 Rep // Iso_rectangle_2 02434 operator()(Return_base_tag, const RT& min_hx, const RT& min_hy, 02435 const RT& max_hx, const RT& max_hy, const RT& hw) const 02436 { 02437 if (hw == 1) 02438 return Rep(Point_2(min_hx, min_hy), 02439 Point_2(max_hx, max_hy), 0); 02440 return Rep(Point_2(min_hx/hw, min_hy/hw), 02441 Point_2(max_hx/hw, max_hy/hw), 0); 02442 } 02443 02444 02445 Iso_rectangle_2 02446 operator()(const Point_2& p, const Point_2& q, int i) const 02447 { 02448 return this->operator()(Return_base_tag(), p, q, i); 02449 } 02450 02451 Iso_rectangle_2 02452 operator()(const Point_2& p, const Point_2& q) const 02453 { 02454 return this->operator()(Return_base_tag(), p, q); 02455 } 02456 02457 Iso_rectangle_2 02458 operator()(const Point_2 &left, const Point_2 &right, 02459 const Point_2 &bottom, const Point_2 &top) const 02460 { 02461 return this->operator()(Return_base_tag(), left, right, bottom, top); 02462 } 02463 02464 Iso_rectangle_2 02465 operator()(const RT& min_hx, const RT& min_hy, 02466 const RT& max_hx, const RT& max_hy) const 02467 { 02468 return this->operator()(Return_base_tag(), min_hx, min_hy, max_hx, max_hy); 02469 } 02470 02471 Iso_rectangle_2 02472 operator()(const RT& min_hx, const RT& min_hy, 02473 const RT& max_hx, const RT& max_hy, const RT& hw) const 02474 { 02475 return this->operator()(Return_base_tag(), min_hx, min_hy, max_hx, max_hy, hw); 02476 } 02477 }; 02478 02479 template <typename K> 02480 class Construct_line_2 02481 { 02482 typedef typename K::RT RT; 02483 typedef typename K::FT FT; 02484 typedef typename K::Point_2 Point_2; 02485 typedef typename K::Direction_2 Direction_2; 02486 typedef typename K::Vector_2 Vector_2; 02487 typedef typename K::Segment_2 Segment_2; 02488 typedef typename K::Ray_2 Ray_2; 02489 typedef typename K::Line_2 Line_2; 02490 typedef typename Line_2::Rep Rep; 02491 typedef typename K::Construct_point_on_2 Construct_point_on_2; 02492 Construct_point_on_2 c; 02493 public: 02494 typedef Line_2 result_type; 02495 02496 Construct_line_2() {} 02497 Construct_line_2(const Construct_point_on_2& c_) : c(c_) {} 02498 02499 Rep // Line_2 02500 operator()(Return_base_tag, const RT& a, const RT& b, const RT& cc) const 02501 { return Rep(a, b, cc); } 02502 02503 Rep // Line_2 02504 operator()(Return_base_tag, const Point_2& p, const Point_2& q) const 02505 { 02506 FT a, b, cc; 02507 line_from_pointsC2(p.x(), p.y(), q.x(), q.y(), a, b, cc); 02508 return Rep(a, b, cc); 02509 } 02510 02511 Rep // Line_2 02512 operator()(Return_base_tag, const Point_2& p, const Direction_2& d) const 02513 { 02514 FT a, b, cc; 02515 line_from_point_directionC2(p.x(), p.y(), d.dx(), d.dy(), a, b, cc); 02516 return Rep(a, b, cc); 02517 } 02518 02519 Rep // Line_2 02520 operator()(Return_base_tag, const Point_2& p, const Vector_2& v) const 02521 { 02522 FT a, b, cc; 02523 line_from_point_directionC2(p.x(), p.y(), v.x(), v.y(), a, b, cc); 02524 return Rep(a, b, cc); 02525 } 02526 02527 Rep // Line_2 02528 operator()(Return_base_tag, const Segment_2& s) const 02529 { return this->operator()(Return_base_tag(), c(s, 0), c(s, 1)); } 02530 02531 Rep // Line_2 02532 operator()(Return_base_tag, const Ray_2& r) const 02533 { return this->operator()(Return_base_tag(), c(r, 0), c(r, 1)); } 02534 02535 02536 Line_2 02537 operator()(const RT& a, const RT& b, const RT& cc) const 02538 { return this->operator()(Return_base_tag(), a, b, cc); } 02539 02540 Line_2 02541 operator()(const Point_2& p, const Point_2& q) const 02542 { return this->operator()(Return_base_tag(), p, q); } 02543 02544 Line_2 02545 operator()(const Point_2& p, const Direction_2& d) const 02546 { return this->operator()(Return_base_tag(), p, d); } 02547 02548 Line_2 02549 operator()(const Point_2& p, const Vector_2& v) const 02550 { return this->operator()(Return_base_tag(), p, v); } 02551 02552 Line_2 02553 operator()(const Segment_2& s) const 02554 { return this->operator()(Return_base_tag(), s); } 02555 02556 Line_2 02557 operator()(const Ray_2& r) const 02558 { return this->operator()(Return_base_tag(), r); } 02559 }; 02560 02561 template <typename K> 02562 class Construct_line_3 02563 { 02564 typedef typename K::Point_3 Point_3; 02565 typedef typename K::Direction_3 Direction_3; 02566 typedef typename K::Segment_3 Segment_3; 02567 typedef typename K::Ray_3 Ray_3; 02568 typedef typename K::Line_3 Line_3; 02569 typedef typename K::Vector_3 Vector_3; 02570 typedef typename Line_3::Rep Rep; 02571 public: 02572 typedef Line_3 result_type; 02573 02574 Rep // Line_3 02575 operator()(Return_base_tag, const Point_3& p, const Point_3& q) const 02576 { return Rep(p, Vector_3(p, q)); } 02577 02578 Rep // Line_3 02579 operator()(Return_base_tag, const Point_3& p, const Direction_3& d) const 02580 { return operator()(Return_base_tag(), p, Vector_3(d.dx(), d.dy(), d.dz())); } 02581 02582 Rep // Line_3 02583 operator()(Return_base_tag, const Point_3& p, const Vector_3& v) const 02584 { return Rep(p, v); } 02585 02586 Rep // Line_3 02587 operator()(Return_base_tag, const Segment_3& s) const 02588 { return Rep(s.source(), Vector_3(s.source(), s.target())); } 02589 02590 Rep // Line_3 02591 operator()(Return_base_tag, const Ray_3& r) const 02592 { return Rep(r.source(), Vector_3(r.source(), r.second_point())); } 02593 02594 02595 Line_3 02596 operator()(const Point_3& p, const Point_3& q) const 02597 { return this->operator()(Return_base_tag(), p, q); } 02598 02599 Line_3 02600 operator()(const Point_3& p, const Direction_3& d) const 02601 { return this->operator()(Return_base_tag(), p, d); } 02602 02603 Line_3 02604 operator()(const Point_3& p, const Vector_3& v) const 02605 { return this->operator()(Return_base_tag(), p, v); } 02606 02607 Line_3 02608 operator()(const Segment_3& s) const 02609 { return this->operator()(Return_base_tag(), s); } 02610 02611 Line_3 02612 operator()(const Ray_3& r) const 02613 { return this->operator()(Return_base_tag(), r); } 02614 }; 02615 02616 template <typename K> 02617 class Construct_midpoint_2 02618 { 02619 typedef typename K::FT FT; 02620 typedef typename K::Point_2 Point_2; 02621 public: 02622 typedef Point_2 result_type; 02623 02624 Point_2 02625 operator()(const Point_2& p, const Point_2& q) const 02626 { 02627 typename K::Construct_point_2 construct_point_2; 02628 FT x, y; 02629 midpointC2(p.x(), p.y(), q.x(), q.y(), x, y); 02630 return construct_point_2(x, y); 02631 } 02632 }; 02633 02634 template <typename K> 02635 class Construct_midpoint_3 02636 { 02637 typedef typename K::FT FT; 02638 typedef typename K::Point_3 Point_3; 02639 public: 02640 typedef Point_3 result_type; 02641 02642 Point_3 02643 operator()(const Point_3& p, const Point_3& q) const 02644 { 02645 typename K::Construct_point_3 construct_point_3; 02646 FT x, y, z; 02647 midpointC3(p.x(), p.y(), p.z(), q.x(), q.y(), q.z(), x, y, z); 02648 return construct_point_3(x, y, z); 02649 } 02650 }; 02651 02652 template <typename K> 02653 class Construct_opposite_vector_2 02654 { 02655 typedef typename K::Vector_2 Vector_2; 02656 public: 02657 typedef Vector_2 result_type; 02658 02659 Vector_2 02660 operator()( const Vector_2& v) const 02661 { return Vector_2(-v.x(), -v.y()); } 02662 }; 02663 02664 template <typename K> 02665 class Construct_difference_of_vectors_2 02666 { 02667 typedef typename K::Vector_2 Vector_2; 02668 public: 02669 typedef Vector_2 result_type; 02670 02671 Vector_2 02672 operator()( const Vector_2& v, const Vector_2& w) const 02673 { return Vector_2(v.x()-w.x(), v.y()-w.y()); } 02674 }; 02675 02676 template <typename K> 02677 class Construct_difference_of_vectors_3 02678 { 02679 typedef typename K::Vector_3 Vector_3; 02680 public: 02681 typedef Vector_3 result_type; 02682 02683 Vector_3 02684 operator()( const Vector_3& v, const Vector_3& w) const 02685 { return Vector_3(v.x()-w.x(), v.y()-w.y(), v.z()-w.z()); } 02686 }; 02687 02688 template <typename K> 02689 class Construct_sum_of_vectors_2 02690 { 02691 typedef typename K::Vector_2 Vector_2; 02692 public: 02693 typedef Vector_2 result_type; 02694 02695 Vector_2 02696 operator()( const Vector_2& v, const Vector_2& w) const 02697 { return Vector_2(v.x()+w.x(), v.y()+w.y()); } 02698 }; 02699 02700 template <typename K> 02701 class Construct_sum_of_vectors_3 02702 { 02703 typedef typename K::Vector_3 Vector_3; 02704 public: 02705 typedef Vector_3 result_type; 02706 02707 Vector_3 02708 operator()( const Vector_3& v, const Vector_3& w) const 02709 { return Vector_3(v.x()+w.x(), v.y()+w.y(), v.z()+w.z()); } 02710 }; 02711 02712 template <typename K> 02713 class Construct_opposite_vector_3 02714 { 02715 typedef typename K::Vector_3 Vector_3; 02716 public: 02717 typedef Vector_3 result_type; 02718 02719 Vector_3 02720 operator()( const Vector_3& v) const 02721 { return Vector_3(-v.x(), -v.y(), -v.z()); } 02722 }; 02723 02724 template <typename K> 02725 class Construct_orthogonal_vector_3 02726 { 02727 typedef typename K::FT FT; 02728 typedef typename K::Point_3 Point_3; 02729 typedef typename K::Vector_3 Vector_3; 02730 typedef typename K::Plane_3 Plane_3; 02731 public: 02732 typedef Vector_3 result_type; 02733 02734 Vector_3 02735 operator()( const Plane_3& p ) const 02736 { return Vector_3(p.a(), p.b(), p.c()); } 02737 02738 Vector_3 02739 operator()( const Point_3& p, const Point_3& q, const Point_3& r ) const 02740 { 02741 FT rpx = p.x()-r.x(); 02742 FT rpy = p.y()-r.y(); 02743 FT rpz = p.z()-r.z(); 02744 FT rqx = q.x()-r.x(); 02745 FT rqy = q.y()-r.y(); 02746 FT rqz = q.z()-r.z(); 02747 // Cross product rp * rq 02748 FT vx = rpy*rqz - rqy*rpz; 02749 FT vy = rpz*rqx - rqz*rpx; 02750 FT vz = rpx*rqy - rqx*rpy; 02751 typename K::Construct_vector_3 construct_vector; 02752 02753 return construct_vector(vx, vy, vz); 02754 } 02755 }; 02756 02757 template <typename K> 02758 class Construct_perpendicular_vector_2 02759 { 02760 typedef typename K::Vector_2 Vector_2; 02761 public: 02762 typedef Vector_2 result_type; 02763 02764 Vector_2 02765 operator()( const Vector_2& v, Orientation o) const 02766 { 02767 CGAL_kernel_precondition( o != COLLINEAR ); 02768 if (o == COUNTERCLOCKWISE) 02769 return K().construct_vector_2_object()(-v.y(), v.x()); 02770 else 02771 return K().construct_vector_2_object()(v.y(), -v.x()); 02772 } 02773 }; 02774 02775 template <typename K> 02776 class Construct_perpendicular_direction_2 02777 { 02778 typedef typename K::Direction_2 Direction_2; 02779 public: 02780 typedef Direction_2 result_type; 02781 02782 Direction_2 02783 operator()( const Direction_2& d, Orientation o) const 02784 { 02785 CGAL_kernel_precondition( o != COLLINEAR ); 02786 if (o == COUNTERCLOCKWISE) 02787 return K().construct_direction_2_object()(-d.dy(), d.dx()); 02788 else 02789 return K().construct_direction_2_object()(d.dy(), -d.dx()); 02790 } 02791 }; 02792 02793 02794 template <typename K> 02795 class Construct_perpendicular_line_2 02796 { 02797 typedef typename K::Line_2 Line_2; 02798 typedef typename K::Point_2 Point_2; 02799 public: 02800 typedef Line_2 result_type; 02801 02802 Line_2 02803 operator()( const Line_2& l, const Point_2& p) const 02804 { 02805 typename K::FT fta, ftb, ftc; 02806 perpendicular_through_pointC2(l.a(), l.b(), p.x(), p.y(), fta, ftb, ftc); 02807 return Line_2(fta, ftb, ftc); 02808 } 02809 }; 02810 02811 02812 template <typename K> 02813 class Construct_point_2 02814 { 02815 typedef typename K::RT RT; 02816 typedef typename K::Point_2 Point_2; 02817 typedef typename K::Line_2 Line_2; 02818 typedef typename Point_2::Rep Rep; 02819 public: 02820 typedef Point_2 result_type; 02821 02822 Rep // Point_2 02823 operator()(Return_base_tag, Origin o) const 02824 { return Rep(o); } 02825 02826 Rep // Point_2 02827 operator()(Return_base_tag, const RT& x, const RT& y) const 02828 { return Rep(x, y); } 02829 02830 Rep // Point_2 02831 operator()(Return_base_tag, const RT& x, const RT& y, const RT& w) const 02832 { return Rep(x, y, w); } 02833 02834 Point_2 02835 operator()(const Line_2& l) const 02836 { 02837 typename K::Construct_point_2 construct_point_2; 02838 typename K::FT x, y; 02839 line_get_pointC2(l.a(), l.b(), l.c(), 0, x, y); 02840 return construct_point_2(x,y); 02841 } 02842 02843 Point_2 02844 operator()(const Line_2& l, int i) const 02845 { 02846 typename K::Construct_point_2 construct_point_2; 02847 typename K::FT x, y; 02848 line_get_pointC2(l.a(), l.b(), l.c(), i, x, y); 02849 return construct_point_2(x,y); 02850 } 02851 02852 02853 Point_2 02854 operator()(Origin o) const 02855 { return this->operator()(Return_base_tag(), o); } 02856 02857 Point_2 02858 operator()(const RT& x, const RT& y) const 02859 { return this->operator()(Return_base_tag(), x, y); } 02860 02861 Point_2 02862 operator()(const RT& x, const RT& y, const RT& w) const 02863 { return this->operator()(Return_base_tag(), x, y, w); } 02864 }; 02865 02866 template <typename K> 02867 class Construct_point_3 02868 { 02869 typedef typename K::RT RT; 02870 typedef typename K::Point_3 Point_3; 02871 typedef typename Point_3::Rep Rep; 02872 public: 02873 typedef Point_3 result_type; 02874 02875 Rep // Point_3 02876 operator()(Return_base_tag, Origin o) const 02877 { return Rep(o); } 02878 02879 Rep // Point_3 02880 operator()(Return_base_tag, const RT& x, const RT& y, const RT& z) const 02881 { return Rep(x, y, z); } 02882 02883 Rep // Point_3 02884 operator()(Return_base_tag, const RT& x, const RT& y, const RT& z, const RT& w) const 02885 { return Rep(x, y, z, w); } 02886 02887 02888 Point_3 02889 operator()(Origin o) const 02890 { return this->operator()(Return_base_tag(), o); } 02891 02892 Point_3 02893 operator()(const RT& x, const RT& y, const RT& z) const 02894 { return this->operator()(Return_base_tag(), x, y, z); } 02895 02896 Point_3 02897 operator()(const RT& x, const RT& y, const RT& z, const RT& w) const 02898 { return this->operator()(Return_base_tag(), x, y, z, w); } 02899 }; 02900 02901 02902 template <typename K> 02903 class Construct_projected_point_2 02904 { 02905 typedef typename K::Point_2 Point_2; 02906 typedef typename K::Line_2 Line_2; 02907 public: 02908 typedef Point_2 result_type; 02909 02910 Point_2 02911 operator()( const Line_2& l, const Point_2& p ) const 02912 { 02913 typename K::FT x, y; 02914 typename K::Construct_point_2 construct_point_2; 02915 line_project_pointC2(l.a(), l.b(), l.c(), p.x(), p.y(), x, y); 02916 return construct_point_2(x, y); 02917 } 02918 }; 02919 02920 02921 template <typename K> 02922 class Construct_projected_point_3 02923 { 02924 typedef typename K::Point_3 Point_3; 02925 typedef typename K::Plane_3 Plane_3; 02926 typedef typename K::Line_3 Line_3; 02927 typedef typename K::FT FT; 02928 public: 02929 typedef Point_3 result_type; 02930 02931 Point_3 02932 operator()( const Line_3& l, const Point_3& p ) const 02933 { 02934 // projects p on the line l 02935 FT lpx = l.point().x(); 02936 FT lpy = l.point().y(); 02937 FT lpz = l.point().z(); 02938 FT ldx = l.direction().dx(); 02939 FT ldy = l.direction().dy(); 02940 FT ldz = l.direction().dz(); 02941 FT dpx = p.x()-lpx; 02942 FT dpy = p.y()-lpy; 02943 FT dpz = p.z()-lpz; 02944 FT lambda = (ldx*dpx+ldy*dpy+ldz*dpz) / (ldx*ldx+ldy*ldy+ldz*ldz); 02945 return Point_3(lpx + lambda * ldx, 02946 lpy + lambda * ldy, 02947 lpz + lambda * ldz); 02948 } 02949 02950 Point_3 02951 operator()( const Plane_3& h, const Point_3& p ) const 02952 { return h.rep().projection(p); } 02953 }; 02954 02955 template <class K> 02956 class Construct_radical_line_2 02957 { 02958 typedef typename K::Line_2 Line_2; 02959 typedef typename K::Circle_2 Circle_2; 02960 typedef typename K::FT FT; 02961 02962 public: 02963 02964 typedef Line_2 result_type; 02965 02966 result_type 02967 operator() (const Circle_2 & c1, const Circle_2 & c2) const 02968 { 02969 // Concentric Circles don't have radical line 02970 CGAL_kernel_precondition (c1.center() != c2.center()); 02971 const FT a = 2*(c2.center().x() - c1.center().x()); 02972 const FT b = 2*(c2.center().y() - c1.center().y()); 02973 const FT c = CGAL::square(c1.center().x()) + 02974 CGAL::square(c1.center().y()) - c1.squared_radius() - 02975 CGAL::square(c2.center().x()) - 02976 CGAL::square(c2.center().y()) + c2.squared_radius(); 02977 return Line_2(a, b, c); 02978 } 02979 }; 02980 02981 template <class K> 02982 class Construct_radical_plane_3 02983 { 02984 typedef typename K::Plane_3 Plane_3; 02985 typedef typename K::Sphere_3 Sphere_3; 02986 typedef typename K::FT FT; 02987 02988 public: 02989 02990 typedef Plane_3 result_type; 02991 02992 result_type 02993 operator() (const Sphere_3 & s1, const Sphere_3 & s2) const 02994 { 02995 // Concentric Spheres don't have radical plane 02996 CGAL_kernel_precondition (s1.center() != s2.center()); 02997 const FT a = 2*(s2.center().x() - s1.center().x()); 02998 const FT b = 2*(s2.center().y() - s1.center().y()); 02999 const FT c = 2*(s2.center().z() - s1.center().z()); 03000 const FT d = CGAL::square(s1.center().x()) + 03001 CGAL::square(s1.center().y()) + 03002 CGAL::square(s1.center().z()) - s1.squared_radius() - 03003 CGAL::square(s2.center().x()) - 03004 CGAL::square(s2.center().y()) - 03005 CGAL::square(s2.center().z()) + s2.squared_radius(); 03006 return Plane_3(a, b, c, d); 03007 } 03008 }; 03009 03010 03011 template <typename K> 03012 class Construct_scaled_vector_2 03013 { 03014 typedef typename K::FT FT; 03015 typedef typename K::Vector_2 Vector_2; 03016 public: 03017 typedef Vector_2 result_type; 03018 03019 Vector_2 03020 operator()( const Vector_2& v, const FT& c) const 03021 { 03022 return Vector_2(c * v.x(), c * v.y()); 03023 } 03024 }; 03025 03026 template <typename K> 03027 class Construct_divided_vector_2 03028 { 03029 typedef typename K::FT FT; 03030 typedef typename K::Vector_2 Vector_2; 03031 public: 03032 typedef Vector_2 result_type; 03033 03034 Vector_2 03035 operator()( const Vector_2& v, const FT& c) const 03036 { 03037 return Vector_2(v.x()/c, v.y()/c); 03038 } 03039 }; 03040 03041 template <typename K> 03042 class Construct_divided_vector_3 03043 { 03044 typedef typename K::FT FT; 03045 typedef typename K::Vector_3 Vector_3; 03046 public: 03047 typedef Vector_3 result_type; 03048 03049 Vector_3 03050 operator()( const Vector_3& v, const FT& c) const 03051 { 03052 return Vector_3(v.x()/c, v.y()/c, v.z()/c); 03053 } 03054 }; 03055 03056 template <typename K> 03057 class Construct_scaled_vector_3 03058 { 03059 typedef typename K::FT FT; 03060 typedef typename K::Vector_3 Vector_3; 03061 public: 03062 typedef Vector_3 result_type; 03063 03064 Vector_3 03065 operator()( const Vector_3& w, const FT& c) const 03066 { 03067 return Vector_3(c * w.x(), c * w.y(), c * w.z()); 03068 } 03069 }; 03070 03071 template <typename K> 03072 class Construct_translated_point_2 03073 { 03074 typedef typename K::Point_2 Point_2; 03075 typedef typename K::Vector_2 Vector_2; 03076 public: 03077 typedef Point_2 result_type; 03078 03079 Point_2 03080 operator()( const Point_2& p, const Vector_2& v) const 03081 { 03082 typename K::Construct_point_2 construct_point_2; 03083 return construct_point_2(p.x() + v.x(), p.y() + v.y()); 03084 } 03085 03086 Point_2 03087 operator()( const Origin& , const Vector_2& v) const 03088 { 03089 typename K::Construct_point_2 construct_point_2; 03090 return construct_point_2(v.x(), v.y()); 03091 } 03092 }; 03093 03094 template <typename K> 03095 class Construct_translated_point_3 03096 { 03097 typedef typename K::Point_3 Point_3; 03098 typedef typename K::Vector_3 Vector_3; 03099 public: 03100 typedef Point_3 result_type; 03101 03102 Point_3 03103 operator()( const Point_3& p, const Vector_3& v) const 03104 { 03105 typename K::Construct_point_3 construct_point_3; 03106 return construct_point_3(p.x() + v.x(), p.y() + v.y(), p.z() + v.z()); 03107 } 03108 03109 Point_3 03110 operator()( const Origin& , const Vector_3& v) const 03111 { 03112 typename K::Construct_point_3 construct_point_3; 03113 return construct_point_3(v.x(), v.y(), v.z()); 03114 } 03115 }; 03116 03117 template <typename K> 03118 class Construct_vector_2 03119 { 03120 typedef typename K::RT RT; 03121 typedef typename K::FT FT; 03122 typedef typename K::Segment_2 Segment_2; 03123 typedef typename K::Ray_2 Ray_2; 03124 typedef typename K::Line_2 Line_2; 03125 typedef typename K::Vector_2 Vector_2; 03126 typedef typename K::Point_2 Point_2; 03127 typedef typename K::Direction_2 Direction_2; 03128 typedef typename Vector_2::Rep Rep; 03129 public: 03130 typedef Vector_2 result_type; 03131 03132 Rep // Vector_2 03133 operator()(Return_base_tag, const Point_2& p, const Point_2& q) const 03134 { return Rep(q.x() - p.x(), q.y() - p.y()); } 03135 03136 Rep // Vector_2 03137 operator()(Return_base_tag, const Origin&, const Point_2& q) const 03138 { return Rep(q.x(), q.y()); } 03139 03140 Rep // Vector_2 03141 operator()(Return_base_tag, const Point_2& p, const Origin& ) const 03142 { return Rep(-p.x(), -p.y()); } 03143 03144 Rep // Vector_2 03145 operator()(Return_base_tag, const Direction_2& d ) const 03146 { return Rep(d.dx(), d.dy()); } 03147 03148 Vector_2 03149 operator()(Return_base_tag, const Segment_2& s) const 03150 { return s.to_vector(); } 03151 03152 Vector_2 03153 operator()(Return_base_tag, const Ray_2& r) const 03154 { return r.to_vector(); } 03155 03156 Rep // Vector_2 03157 operator()(Return_base_tag, const Line_2& l) const 03158 { return Rep(l.b(), -l.a()); } 03159 03160 Rep // Vector_2 03161 operator()(Return_base_tag, Null_vector) const 03162 { return Rep(FT(0), FT(0)); } 03163 03164 Rep // Vector_2 03165 operator()(Return_base_tag, const RT& x, const RT& y) const 03166 { return Rep(x, y); } 03167 03168 Rep // Vector_2 03169 operator()(Return_base_tag, const RT& x, const RT& y, const RT& w) const 03170 { return Rep(x, y, w); } 03171 03172 03173 03174 Vector_2 03175 operator()( const Point_2& p, const Point_2& q) const 03176 { return this->operator()(Return_base_tag(), p, q); } 03177 03178 Vector_2 03179 operator()( const Origin& o, const Point_2& q) const 03180 { return this->operator()(Return_base_tag(), o, q); } 03181 03182 Vector_2 03183 operator()( const Point_2& p, const Origin& o) const 03184 { return this->operator()(Return_base_tag(), p, o); } 03185 03186 Vector_2 03187 operator()( const Direction_2& d ) const 03188 { return this->operator()(Return_base_tag(), d); } 03189 03190 Vector_2 03191 operator()( const Segment_2& s) const 03192 { return this->operator()(Return_base_tag(), s); } 03193 03194 Vector_2 03195 operator()( const Ray_2& r) const 03196 { return this->operator()(Return_base_tag(), r); } 03197 03198 Vector_2 03199 operator()( const Line_2& l) const 03200 { return this->operator()(Return_base_tag(), l); } 03201 03202 Vector_2 03203 operator()( Null_vector n) const 03204 { return this->operator()(Return_base_tag(), n); } 03205 03206 Vector_2 03207 operator()( const RT& x, const RT& y) const 03208 { return this->operator()(Return_base_tag(), x, y); } 03209 03210 Vector_2 03211 operator()( const RT& x, const RT& y, const RT& w) const 03212 { return this->operator()(Return_base_tag(), x, y, w); } 03213 }; 03214 03215 template <typename K> 03216 class Construct_vector_3 03217 { 03218 typedef typename K::RT RT; 03219 typedef typename K::FT FT; 03220 typedef typename K::Segment_3 Segment_3; 03221 typedef typename K::Direction_3 Direction_3; 03222 typedef typename K::Ray_3 Ray_3; 03223 typedef typename K::Line_3 Line_3; 03224 typedef typename K::Vector_3 Vector_3; 03225 typedef typename K::Point_3 Point_3; 03226 typedef typename Vector_3::Rep Rep; 03227 public: 03228 typedef Vector_3 result_type; 03229 03230 Rep // Vector_3 03231 operator()(Return_base_tag, const Point_3& p, const Point_3& q) const 03232 { 03233 return Rep(q.x() - p.x(), q.y() - p.y(), q.z() - p.z()); 03234 } 03235 03236 Rep // Vector_3 03237 operator()(Return_base_tag, const Origin&, const Point_3& q) const 03238 { 03239 return Rep(q.x(), q.y(), q.z()); 03240 } 03241 03242 Rep // Vector_3 03243 operator()(Return_base_tag, const Point_3& p, const Origin&) const 03244 { 03245 return Rep(- p.x(), - p.y(), - p.z()); 03246 } 03247 03248 Rep // Vector_3 03249 operator()(Return_base_tag, const Direction_3& d) const 03250 { return d.rep().to_vector(); } 03251 03252 Rep // Vector_3 03253 operator()(Return_base_tag, const Segment_3& s) const 03254 { return s.rep().to_vector(); } 03255 03256 Rep // Vector_3 03257 operator()(Return_base_tag, const Ray_3& r) const 03258 { return r.rep().to_vector(); } 03259 03260 Rep // Vector_3 03261 operator()(Return_base_tag, const Line_3& l) const 03262 { return l.rep().to_vector(); } 03263 03264 Rep // Vector_3 03265 operator()(Return_base_tag, const Null_vector&) const 03266 { return Rep(FT(0), FT(0), FT(0)); } 03267 03268 Rep // Vector_3 03269 operator()(Return_base_tag, const RT& x, const RT& y, const RT& z) const 03270 { return Rep(x, y, z); } 03271 03272 Rep // Vector_3 03273 operator()(Return_base_tag, const RT& x, const RT& y, const RT& z, const RT& w) const 03274 { return Rep(x, y, z, w); } 03275 03276 03277 Vector_3 03278 operator()( const Point_3& p, const Point_3& q) const 03279 { return this->operator()(Return_base_tag(), p, q); } 03280 03281 Vector_3 03282 operator()( const Origin& o, const Point_3& q) const 03283 { return this->operator()(Return_base_tag(), o, q); } 03284 03285 Vector_3 03286 operator()( const Point_3& p, const Origin& q) const 03287 { return this->operator()(Return_base_tag(), p, q); } 03288 03289 Vector_3 03290 operator()( const Direction_3& d) const 03291 { return this->operator()(Return_base_tag(), d); } 03292 03293 Vector_3 03294 operator()( const Segment_3& s) const 03295 { return this->operator()(Return_base_tag(), s); } 03296 03297 Vector_3 03298 operator()( const Ray_3& r) const 03299 { return this->operator()(Return_base_tag(), r); } 03300 03301 Vector_3 03302 operator()( const Line_3& l) const 03303 { return this->operator()(Return_base_tag(), l); } 03304 03305 Vector_3 03306 operator()( const Null_vector& n) const 03307 { return this->operator()(Return_base_tag(), n); } 03308 03309 Vector_3 03310 operator()( int x, int y, int z) const 03311 { return this->operator()(Return_base_tag(), x, y, z); } 03312 03313 Vector_3 03314 operator()( const RT& x, const RT& y, const RT& z) const 03315 { return this->operator()(Return_base_tag(), x, y, z); } 03316 03317 Vector_3 03318 operator()( const RT& x, const RT& y, const RT& z, const RT& w) const 03319 { return this->operator()(Return_base_tag(), x, y, z, w); } 03320 }; 03321 03322 template <typename K> 03323 class Construct_vertex_2 03324 { 03325 typedef typename K::Point_2 Point_2; 03326 typedef typename K::Segment_2 Segment_2; 03327 typedef typename K::Iso_rectangle_2 Iso_rectangle_2; 03328 typedef typename K::Triangle_2 Triangle_2; 03329 public: 03330 typedef Point_2 result_type; 03331 03332 const Point_2 & 03333 operator()( const Segment_2& s, int i) const 03334 { return s.vertex(i); } 03335 03336 const Point_2 & 03337 operator()( const Triangle_2& t, int i) const 03338 { return t.rep().vertex(i); } 03339 03340 Point_2 03341 operator()( const Iso_rectangle_2& r, int i) const 03342 { 03343 switch (i%4) { 03344 case 0: return (r.min)(); 03345 case 1: return Point_2(r.xmax(), r.ymin()); 03346 case 2: return (r.max)(); 03347 default: return Point_2(r.xmin(), r.ymax()); 03348 } 03349 } 03350 }; 03351 03352 } //namespace CartesianKernelFunctors 03353 03354 #ifndef CGAL_CFG_DONT_OVERLOAD_TOO_MUCH 03355 template < typename K> 03356 struct Qualified_result_of<CartesianKernelFunctors::Construct_vertex_2<K>, typename K::Segment_2, int > 03357 { 03358 typedef typename K::Point_2 const & type; 03359 }; 03360 03361 template < typename K> 03362 struct Qualified_result_of<CartesianKernelFunctors::Construct_vertex_2<K>, typename K::Triangle_2, int > 03363 { 03364 typedef typename K::Point_2 const & type; 03365 }; 03366 #endif 03367 03368 // For Iso_rectangle the non specialized template will do the right thing, namely return a copy of a point 03369 03370 namespace CartesianKernelFunctors { 03371 03372 template <typename K> 03373 class Coplanar_orientation_3 03374 { 03375 typedef typename K::Point_3 Point_3; 03376 #ifdef CGAL_kernel_exactness_preconditions 03377 typedef typename K::Coplanar_3 Coplanar_3; 03378 typedef typename K::Collinear_3 Collinear_3; 03379 Coplanar_3 cp; 03380 Collinear_3 cl; 03381 #endif // CGAL_kernel_exactness_preconditions 03382 public: 03383 typedef typename K::Orientation result_type; 03384 03385 #ifdef CGAL_kernel_exactness_preconditions 03386 Coplanar_orientation_3() {} 03387 Coplanar_orientation_3(const Coplanar_3& cp_, const Collinear_3& cl_) 03388 : cp(cp_), cl(cl_) 03389 {} 03390 #endif // CGAL_kernel_exactness_preconditions 03391 03392 result_type 03393 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 03394 { 03395 return coplanar_orientationC3(p.x(), p.y(), p.z(), 03396 q.x(), q.y(), q.z(), 03397 r.x(), r.y(), r.z()); 03398 } 03399 03400 result_type 03401 operator()( const Point_3& p, const Point_3& q, 03402 const Point_3& r, const Point_3& s) const 03403 { 03404 // p,q,r,s supposed to be coplanar 03405 // p,q,r supposed to be non collinear 03406 // tests whether s is on the same side of p,q as r 03407 // returns : 03408 // COLLINEAR if pqr collinear 03409 // POSITIVE if qrp and qrs have the same orientation 03410 // NEGATIVE if qrp and qrs have opposite orientations 03411 CGAL_kernel_exactness_precondition( ! cl(p, q, r) ); 03412 CGAL_kernel_exactness_precondition( cp(p, q, r, s) ); 03413 return coplanar_orientationC3(p.x(), p.y(), p.z(), 03414 q.x(), q.y(), q.z(), 03415 r.x(), r.y(), r.z(), 03416 s.x(), s.y(), s.z()); 03417 } 03418 }; 03419 03420 template <typename K> 03421 class Coplanar_side_of_bounded_circle_3 03422 { 03423 typedef typename K::Point_3 Point_3; 03424 #ifdef CGAL_kernel_exactness_preconditions 03425 typedef typename K::Coplanar_3 Coplanar_3; 03426 typedef typename K::Collinear_3 Collinear_3; 03427 Coplanar_3 cp; 03428 Collinear_3 cl; 03429 #endif // CGAL_kernel_exactness_preconditions 03430 public: 03431 typedef typename K::Bounded_side result_type; 03432 03433 #ifdef CGAL_kernel_exactness_preconditions 03434 Coplanar_side_of_bounded_circle_3() {} 03435 Coplanar_side_of_bounded_circle_3(const Coplanar_3& cp_, 03436 const Collinear_3& cl_) 03437 : cp(cp_), cl(cl_) 03438 {} 03439 #endif // CGAL_kernel_exactness_preconditions 03440 03441 result_type 03442 operator()( const Point_3& p, const Point_3& q, 03443 const Point_3& r, const Point_3& t) const 03444 { 03445 // p,q,r,t are supposed to be coplanar. 03446 // p,q,r determine an orientation of this plane (not collinear). 03447 // returns the equivalent of side_of_bounded_circle(p,q,r,t) 03448 // in this plane 03449 CGAL_kernel_exactness_precondition( cp(p,q,r,t) ); 03450 CGAL_kernel_exactness_precondition( !cl(p,q,r) ); 03451 return coplanar_side_of_bounded_circleC3(p.x(), p.y(), p.z(), 03452 q.x(), q.y(), q.z(), 03453 r.x(), r.y(), r.z(), 03454 t.x(), t.y(), t.z()); 03455 } 03456 }; 03457 03458 template <typename K> 03459 class Equal_xy_3 03460 { 03461 typedef typename K::Point_3 Point_3; 03462 public: 03463 typedef typename K::Boolean result_type; 03464 03465 result_type 03466 operator()( const Point_3& p, const Point_3& q) const 03467 { 03468 return CGAL_AND( p.x() == q.x() , p.y() == q.y() ); 03469 } 03470 }; 03471 03472 template <typename K> 03473 class Equal_x_2 03474 { 03475 typedef typename K::Point_2 Point_2; 03476 public: 03477 typedef typename K::Boolean result_type; 03478 03479 result_type 03480 operator()( const Point_2& p, const Point_2& q) const 03481 { return p.x() == q.x(); } 03482 }; 03483 03484 template <typename K> 03485 class Equal_x_3 03486 { 03487 typedef typename K::Point_3 Point_3; 03488 public: 03489 typedef typename K::Boolean result_type; 03490 03491 result_type 03492 operator()( const Point_3& p, const Point_3& q) const 03493 { return p.x() == q.x(); } 03494 }; 03495 03496 template <typename K> 03497 class Equal_y_2 03498 { 03499 typedef typename K::Point_2 Point_2; 03500 public: 03501 typedef typename K::Boolean result_type; 03502 03503 result_type 03504 operator()( const Point_2& p, const Point_2& q) const 03505 { return p.y() == q.y(); } 03506 }; 03507 03508 template <typename K> 03509 class Equal_y_3 03510 { 03511 typedef typename K::Point_3 Point_3; 03512 public: 03513 typedef typename K::Boolean result_type; 03514 03515 result_type 03516 operator()( const Point_3& p, const Point_3& q) const 03517 { return p.y() == q.y(); } 03518 }; 03519 03520 template <typename K> 03521 class Equal_z_3 03522 { 03523 typedef typename K::Point_3 Point_3; 03524 public: 03525 typedef typename K::Boolean result_type; 03526 03527 result_type 03528 operator()( const Point_3& p, const Point_3& q) const 03529 { return p.z() == q.z(); } 03530 }; 03531 03532 template <typename K> 03533 class Has_on_3 03534 { 03535 typedef typename K::FT FT; 03536 typedef typename K::Point_3 Point_3; 03537 typedef typename K::Vector_3 Vector_3; 03538 typedef typename K::Line_3 Line_3; 03539 typedef typename K::Ray_3 Ray_3; 03540 typedef typename K::Segment_3 Segment_3; 03541 typedef typename K::Plane_3 Plane_3; 03542 typedef typename K::Triangle_3 Triangle_3; 03543 typedef typename K::Circle_3 Circle_3; 03544 typedef typename K::Sphere_3 Sphere_3; 03545 public: 03546 typedef typename K::Boolean result_type; 03547 03548 result_type 03549 operator()( const Line_3& l, const Point_3& p) const 03550 { return l.rep().has_on(p); } 03551 03552 result_type 03553 operator()( const Ray_3& r, const Point_3& p) const 03554 { return r.rep().has_on(p); } 03555 03556 result_type 03557 operator()( const Segment_3& s, const Point_3& p) const 03558 { return s.has_on(p); } 03559 03560 result_type 03561 operator()( const Plane_3& pl, const Point_3& p) const 03562 { return pl.rep().has_on(p); } 03563 03564 result_type 03565 operator()( const Plane_3& pl, const Line_3& l) const 03566 { return pl.rep().has_on(l); } 03567 03568 result_type 03569 operator()( const Triangle_3& t, const Point_3& p) const 03570 { 03571 Point_3 o = t.vertex(0) + t.supporting_plane().orthogonal_vector(); 03572 Vector_3 v0 = t.vertex(0)-o, 03573 v1 = t.vertex(1)-o, 03574 v2 = t.vertex(2)-o; 03575 03576 FT alpha, beta, gamma; 03577 Cartesian_internal::solve(v0, v1, v2, p-o, alpha, beta, gamma); 03578 return (alpha >= FT(0)) && (beta >= FT(0)) && (gamma >= FT(0)) 03579 && ((alpha+beta+gamma == FT(1))); 03580 } 03581 03582 result_type 03583 operator()(const Circle_3 &a, const Point_3 &p) const 03584 { return a.rep().has_on(p); } 03585 03586 result_type 03587 operator()(const Sphere_3 &a, const Circle_3 &p) const 03588 { return a.rep().has_on(p); } 03589 03590 result_type 03591 operator()(const Sphere_3 &a, const Point_3 &p) const 03592 { return a.rep().has_on(p); } 03593 03594 result_type 03595 operator()(const Plane_3 &a, const Circle_3 &p) const 03596 { return a.rep().has_on(p); } 03597 03598 03599 }; 03600 03601 template <typename K> 03602 class Less_distance_to_point_2 03603 { 03604 typedef typename K::Point_2 Point_2; 03605 public: 03606 typedef typename K::Boolean result_type; 03607 03608 result_type 03609 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 03610 { 03611 return has_smaller_dist_to_pointC2(p.x(), p.y(), 03612 q.x(), q.y(), 03613 r.x(), r.y()); 03614 } 03615 }; 03616 03617 template <typename K> 03618 class Less_distance_to_point_3 03619 { 03620 typedef typename K::Point_3 Point_3; 03621 public: 03622 typedef typename K::Boolean result_type; 03623 03624 result_type 03625 operator()(const Point_3& p, const Point_3& q, const Point_3& r) const 03626 { 03627 return has_smaller_dist_to_pointC3(p.x(), p.y(), p.z(), 03628 q.x(), q.y(), q.z(), 03629 r.x(), r.y(), r.z()); 03630 } 03631 }; 03632 03633 // TODO ... 03634 template <typename K> 03635 class Less_signed_distance_to_line_2 03636 { 03637 typedef typename K::Point_2 Point_2; 03638 typedef typename K::Line_2 Line_2; 03639 typedef typename K::Equal_2 Equal_2; 03640 public: 03641 typedef typename K::Boolean result_type; 03642 03643 result_type 03644 operator()(const Point_2& a, const Point_2& b, 03645 const Point_2& c, const Point_2& d) const 03646 { 03647 CGAL_kernel_precondition_code(Equal_2 equal;) 03648 CGAL_kernel_precondition(! equal(a,b)); 03649 return cmp_signed_dist_to_lineC2( a.x(), a.y(), 03650 b.x(), b.y(), 03651 c.x(), c.y(), 03652 d.x(), d.y()) == SMALLER; 03653 } 03654 03655 result_type 03656 operator()(const Line_2& l, const Point_2& p, const Point_2& q) const 03657 { 03658 return has_smaller_signed_dist_to_directionC2(l.a(), l.b(), 03659 p.x(), p.y(), 03660 q.x(), q.y()); 03661 } 03662 }; 03663 03664 template <typename K> 03665 class Less_signed_distance_to_plane_3 03666 { 03667 typedef typename K::Point_3 Point_3; 03668 typedef typename K::Plane_3 Plane_3; 03669 typedef typename K::Collinear_3 Collinear_3; 03670 public: 03671 typedef typename K::Boolean result_type; 03672 03673 result_type 03674 operator()( const Plane_3& h, const Point_3& p, const Point_3& q) const 03675 { 03676 return has_smaller_signed_dist_to_directionC3(h.a(), h.b(), h.c(), 03677 p.x(), p.y(), p.z(), 03678 q.x(), q.y(), q.z()); 03679 } 03680 03681 result_type 03682 operator()( const Point_3& hp, const Point_3& hq, const Point_3& hr, 03683 const Point_3& p, const Point_3& q) const 03684 { 03685 CGAL_kernel_precondition_code(Collinear_3 collinear_3;) 03686 CGAL_kernel_precondition(! collinear_3(hp, hq, hr)); 03687 return has_smaller_signed_dist_to_planeC3(hp.x(), hp.y(), hp.z(), 03688 hq.x(), hq.y(), hq.z(), 03689 hr.x(), hr.y(), hr.z(), 03690 p.x(), p.y(), p.z(), 03691 q.x(), q.y(), q.z());; 03692 } 03693 }; 03694 03695 template <typename K> 03696 class Less_xyz_3 03697 { 03698 typedef typename K::Point_3 Point_3; 03699 typedef typename K::Compare_xyz_3 Compare_xyz_3; 03700 Compare_xyz_3 c; 03701 public: 03702 typedef typename K::Boolean result_type; 03703 03704 Less_xyz_3() {} 03705 Less_xyz_3(const Compare_xyz_3& c_) : c(c_) {} 03706 03707 result_type 03708 operator()( const Point_3& p, const Point_3& q) const 03709 { return c(p, q) == SMALLER; } 03710 }; 03711 03712 template <typename K> 03713 class Less_xy_2 03714 { 03715 typedef typename K::Point_2 Point_2; 03716 typedef typename K::Compare_xy_2 Compare_xy_2; 03717 Compare_xy_2 c; 03718 public: 03719 typedef typename K::Boolean result_type; 03720 03721 Less_xy_2() {} 03722 Less_xy_2(const Compare_xy_2& c_) : c(c_) {} 03723 03724 result_type 03725 operator()( const Point_2& p, const Point_2& q) const 03726 { return c(p, q) == SMALLER; } 03727 }; 03728 03729 template <typename K> 03730 class Less_xy_3 03731 { 03732 typedef typename K::Point_3 Point_3; 03733 typedef typename K::Compare_xy_3 Compare_xy_3; 03734 Compare_xy_3 c; 03735 public: 03736 typedef typename K::Boolean result_type; 03737 03738 Less_xy_3() {} 03739 Less_xy_3(const Compare_xy_3& c_) : c(c_) {} 03740 03741 result_type 03742 operator()( const Point_3& p, const Point_3& q) const 03743 { return c(p, q) == SMALLER; } 03744 }; 03745 03746 template <typename K> 03747 class Less_x_2 03748 { 03749 typedef typename K::Point_2 Point_2; 03750 public: 03751 typedef typename K::Boolean result_type; 03752 03753 result_type 03754 operator()( const Point_2& p, const Point_2& q) const 03755 { return p.x() < q.x(); } 03756 }; 03757 03758 template <typename K> 03759 class Less_x_3 03760 { 03761 typedef typename K::Point_3 Point_3; 03762 public: 03763 typedef typename K::Boolean result_type; 03764 03765 result_type 03766 operator()( const Point_3& p, const Point_3& q) const 03767 { return p.x() < q.x(); } 03768 }; 03769 03770 template <typename K> 03771 class Less_yx_2 03772 { 03773 typedef typename K::Point_2 Point_2; 03774 public: 03775 typedef typename K::Boolean result_type; 03776 03777 result_type 03778 operator()( const Point_2& p, const Point_2& q) const 03779 { 03780 return compare_lexicographically_xyC2(p.y(), p.x(), 03781 q.y(), q.x()) == SMALLER; 03782 } 03783 }; 03784 03785 template <typename K> 03786 class Less_y_2 03787 { 03788 typedef typename K::Point_2 Point_2; 03789 public: 03790 typedef typename K::Boolean result_type; 03791 03792 result_type 03793 operator()( const Point_2& p, const Point_2& q) const 03794 { return p.y() < q.y(); } 03795 }; 03796 03797 template <typename K> 03798 class Less_y_3 03799 { 03800 typedef typename K::Point_3 Point_3; 03801 public: 03802 typedef typename K::Boolean result_type; 03803 03804 result_type 03805 operator()( const Point_3& p, const Point_3& q) const 03806 { return p.y() < q.y(); } 03807 }; 03808 03809 template <typename K> 03810 class Less_z_3 03811 { 03812 typedef typename K::Point_3 Point_3; 03813 public: 03814 typedef typename K::Boolean result_type; 03815 03816 result_type 03817 operator()( const Point_3& p, const Point_3& q) const 03818 { return p.z() < q.z(); } 03819 }; 03820 03821 template <typename K> 03822 class Orientation_2 03823 { 03824 typedef typename K::Point_2 Point_2; 03825 typedef typename K::Vector_2 Vector_2; 03826 typedef typename K::Circle_2 Circle_2; 03827 public: 03828 typedef typename K::Orientation result_type; 03829 03830 result_type 03831 operator()(const Point_2& p, const Point_2& q, const Point_2& r) const 03832 { 03833 return orientationC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); 03834 } 03835 03836 result_type 03837 operator()(const Vector_2& u, const Vector_2& v) const 03838 { 03839 return orientationC2(u.x(), u.y(), v.x(), v.y()); 03840 } 03841 03842 result_type 03843 operator()(const Circle_2& c) const 03844 { 03845 return c.rep().orientation(); 03846 } 03847 }; 03848 03849 template <typename K> 03850 class Orientation_3 03851 { 03852 typedef typename K::Point_3 Point_3; 03853 typedef typename K::Vector_3 Vector_3; 03854 typedef typename K::Tetrahedron_3 Tetrahedron_3; 03855 typedef typename K::Sphere_3 Sphere_3; 03856 public: 03857 typedef typename K::Orientation result_type; 03858 03859 result_type 03860 operator()( const Point_3& p, const Point_3& q, 03861 const Point_3& r, const Point_3& s) const 03862 { 03863 return orientationC3(p.x(), p.y(), p.z(), 03864 q.x(), q.y(), q.z(), 03865 r.x(), r.y(), r.z(), 03866 s.x(), s.y(), s.z()); 03867 } 03868 03869 result_type 03870 operator()( const Vector_3& u, const Vector_3& v, const Vector_3& w) const 03871 { 03872 return orientationC3(u.x(), u.y(), u.z(), 03873 v.x(), v.y(), v.z(), 03874 w.x(), w.y(), w.z()); 03875 } 03876 03877 result_type 03878 operator()( const Tetrahedron_3& t) const 03879 { 03880 return t.rep().orientation(); 03881 } 03882 03883 result_type 03884 operator()(const Sphere_3& s) const 03885 { 03886 return s.rep().orientation(); 03887 } 03888 }; 03889 03890 template <typename K> 03891 class Oriented_side_2 03892 { 03893 typedef typename K::Point_2 Point_2; 03894 typedef typename K::Circle_2 Circle_2; 03895 typedef typename K::Line_2 Line_2; 03896 typedef typename K::Triangle_2 Triangle_2; 03897 public: 03898 typedef typename K::Oriented_side result_type; 03899 03900 result_type 03901 operator()( const Circle_2& c, const Point_2& p) const 03902 { return enum_cast<Oriented_side>(c.bounded_side(p)) * c.orientation(); } 03903 03904 result_type 03905 operator()( const Line_2& l, const Point_2& p) const 03906 { return side_of_oriented_lineC2(l.a(), l.b(), l.c(), p.x(), p.y()); } 03907 03908 result_type 03909 operator()( const Triangle_2& t, const Point_2& p) const 03910 { 03911 typename K::Collinear_are_ordered_along_line_2 03912 collinear_are_ordered_along_line; 03913 typename K::Orientation_2 orientation; 03914 // depends on the orientation of the vertices 03915 typename K::Orientation 03916 o1 = orientation(t.vertex(0), t.vertex(1), p), 03917 o2 = orientation(t.vertex(1), t.vertex(2), p), 03918 o3 = orientation(t.vertex(2), t.vertex(3), p), 03919 ot = orientation(t.vertex(0), t.vertex(1), t.vertex(2)); 03920 03921 if (o1 == ot && o2 == ot && o3 == ot) // ot cannot be COLLINEAR 03922 return ot; 03923 return 03924 (o1 == COLLINEAR 03925 && collinear_are_ordered_along_line(t.vertex(0), p, t.vertex(1))) || 03926 (o2 == COLLINEAR 03927 && collinear_are_ordered_along_line(t.vertex(1), p, t.vertex(2))) || 03928 (o3 == COLLINEAR 03929 && collinear_are_ordered_along_line(t.vertex(2), p, t.vertex(3))) 03930 ? result_type(ON_ORIENTED_BOUNDARY) 03931 : opposite(ot); 03932 } 03933 }; 03934 03935 template <typename K> 03936 class Side_of_bounded_circle_2 03937 { 03938 typedef typename K::Point_2 Point_2; 03939 public: 03940 typedef typename K::Bounded_side result_type; 03941 03942 result_type 03943 operator()( const Point_2& p, const Point_2& q, const Point_2& t) const 03944 { 03945 return side_of_bounded_circleC2(p.x(), p.y(), 03946 q.x(), q.y(), 03947 t.x(), t.y()); 03948 } 03949 03950 result_type 03951 operator()( const Point_2& p, const Point_2& q, 03952 const Point_2& r, const Point_2& t) const 03953 { 03954 return side_of_bounded_circleC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), 03955 t.x(), t.y()); 03956 } 03957 }; 03958 03959 template <typename K> 03960 class Side_of_bounded_sphere_3 03961 { 03962 typedef typename K::Point_3 Point_3; 03963 public: 03964 typedef typename K::Bounded_side result_type; 03965 03966 result_type 03967 operator()( const Point_3& p, const Point_3& q, const Point_3& test) const 03968 { 03969 return side_of_bounded_sphereC3(p.x(), p.y(), p.z(), 03970 q.x(), q.y(), q.z(), 03971 test.x(), test.y(), test.z()); 03972 } 03973 03974 result_type 03975 operator()( const Point_3& p, const Point_3& q, 03976 const Point_3& r, const Point_3& test) const 03977 { 03978 return side_of_bounded_sphereC3(p.x(), p.y(), p.z(), 03979 q.x(), q.y(), q.z(), 03980 r.x(), r.y(), r.z(), 03981 test.x(), test.y(), test.z()); 03982 } 03983 03984 result_type 03985 operator()( const Point_3& p, const Point_3& q, const Point_3& r, 03986 const Point_3& s, const Point_3& test) const 03987 { 03988 return side_of_bounded_sphereC3(p.x(), p.y(), p.z(), 03989 q.x(), q.y(), q.z(), 03990 r.x(), r.y(), r.z(), 03991 s.x(), s.y(), s.z(), 03992 test.x(), test.y(), test.z()); 03993 } 03994 }; 03995 03996 template <typename K> 03997 class Side_of_oriented_circle_2 03998 { 03999 typedef typename K::Point_2 Point_2; 04000 public: 04001 typedef typename K::Oriented_side result_type; 04002 04003 result_type 04004 operator()( const Point_2& p, const Point_2& q, 04005 const Point_2& r, const Point_2& t) const 04006 { 04007 return side_of_oriented_circleC2(p.x(), p.y(), 04008 q.x(), q.y(), 04009 r.x(), r.y(), 04010 t.x(), t.y()); 04011 } 04012 }; 04013 04014 template <typename K> 04015 class Side_of_oriented_sphere_3 04016 { 04017 typedef typename K::Point_3 Point_3; 04018 public: 04019 typedef typename K::Oriented_side result_type; 04020 04021 result_type 04022 operator()( const Point_3& p, const Point_3& q, const Point_3& r, 04023 const Point_3& s, const Point_3& test) const 04024 { 04025 return side_of_oriented_sphereC3(p.x(), p.y(), p.z(), 04026 q.x(), q.y(), q.z(), 04027 r.x(), r.y(), r.z(), 04028 s.x(), s.y(), s.z(), 04029 test.x(), test.y(), test.z()); 04030 } 04031 }; 04032 04033 } // namespace CartesianKernelFunctors 04034 04035 CGAL_END_NAMESPACE 04036 04037 #endif // CGAL_CARTESIAN_FUNCTION_OBJECTS_H
1.7.6.1
