|
BWAPI
|
00001 // Copyright (c) 1997-2002 Max-Planck-Institute Saarbruecken (Germany). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under 00005 // the terms of the Q Public License version 1.0. 00006 // See the file LICENSE.QPL distributed with CGAL. 00007 // 00008 // Licensees holding a valid commercial license may use this file in 00009 // accordance with the commercial license agreement provided with the software. 00010 // 00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00013 // 00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Nef_3/include/CGAL/Nef_3/SNC_intersection.h $ 00015 // $Id: SNC_intersection.h 43273 2008-05-22 15:04:50Z hachenb $ 00016 // 00017 // 00018 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de> 00019 // Peter Hachenberger <hachenberger@mpi-sb.mpg.de> 00020 #ifndef CGAL_SNC_INTERSECTION_H 00021 #define CGAL_SNC_INTERSECTION_H 00022 00023 #include <CGAL/basic.h> 00024 00025 #undef CGAL_NEF_DEBUG 00026 #define CGAL_NEF_DEBUG 37 00027 #include <CGAL/Nef_2/debug.h> 00028 00029 CGAL_BEGIN_NAMESPACE 00030 00031 template < class Node, class Object> 00032 struct Project_shalfedge_point { 00033 typedef Node argument_type; 00034 typedef Object result_type; 00035 Object& operator()( Node& x) const { 00036 return x.source()->source()->point(); 00037 /* a Point_3& reference must be returned by D.point() */ 00038 } 00039 const Object& operator()( const Node& x) const { 00040 return x.source()->source()->point(); 00041 /* a Point_3& reference must be returned by D.point() */ 00042 } 00043 }; 00044 00045 template<typename SNC_structure_> 00046 class SNC_intersection : public SNC_const_decorator<SNC_structure_> { 00047 // TODO: granados: is it really necessary to inherit from the decorator? 00048 00049 typedef SNC_structure_ SNC_structure; 00050 typedef SNC_intersection<SNC_structure> Self; 00051 typedef SNC_const_decorator<SNC_structure> Base; 00052 // typedef SNC_const_decorator<SNC_structure> SNC_const_decorator; 00053 00054 typedef typename SNC_structure::SHalfedge SHalfedge; 00055 typedef typename SNC_structure::Halfedge_handle Halfedge_handle; 00056 typedef typename SNC_structure::Halffacet_const_handle 00057 Halffacet_const_handle; 00058 typedef typename SNC_structure::SHalfedge_const_handle SHalfedge_const_handle; 00059 typedef typename SNC_structure::SHalfloop_const_handle SHalfloop_const_handle; 00060 typedef typename SNC_structure::SHalfedge_around_facet_const_circulator 00061 SHalfedge_around_facet_const_circulator; 00062 typedef typename SNC_structure::Halffacet_cycle_const_iterator 00063 Halffacet_cycle_const_iterator; 00064 00065 #ifdef CGAL_NEF3_FACET_WITH_BOX 00066 typedef typename SNC_structure::Partial_facet Partial_facet; 00067 #endif 00068 00069 typedef typename SNC_structure::Point_3 Point_3; 00070 typedef typename SNC_structure::Vector_3 Vector_3; 00071 typedef typename SNC_structure::Segment_3 Segment_3; 00072 typedef typename SNC_structure::Line_3 Line_3; 00073 typedef typename SNC_structure::Ray_3 Ray_3; 00074 typedef typename SNC_structure::Plane_3 Plane_3; 00075 typedef typename SNC_structure::Triangle_3 Triangle_3; 00076 00077 public: 00078 00079 SNC_intersection() : Base() {} 00080 SNC_intersection(const SNC_structure& W) : Base(W) {} 00081 00082 bool does_contain_internally(const Segment_3& s, const Point_3& p) const { 00083 if(!are_strictly_ordered_along_line (s.source(), p, s.target())) 00084 return false; 00085 if(!s.supporting_line().has_on(p)) 00086 return false; 00087 return true; 00088 } 00089 00090 bool does_contain_internally( Halffacet_const_handle f, 00091 const Point_3& p, 00092 bool check_has_on = true) const { 00093 if(check_has_on && !f->plane().has_on(p)) 00094 return false; 00095 return (locate_point_in_halffacet( p, f) == CGAL::ON_BOUNDED_SIDE); 00096 } 00097 00098 #ifdef CGAL_NEF3_FACET_WITH_BOX 00099 bool does_contain_internally( Partial_facet& pf, 00100 const Point_3& p) const { 00101 CGAL_NEF_TRACEN("does point lie in partial facet" << p); 00102 // pf.debug(); 00103 if( !pf.f->plane().has_on(p)) 00104 return false; 00105 return (locate_point_in_halffacet( p, pf) == CGAL::ON_BOUNDED_SIDE); 00106 } 00107 #endif 00108 00109 bool does_contain_on_boundary( Halffacet_const_handle f, const Point_3& p) const { 00110 typedef Project_shalfedge_point 00111 < SHalfedge, const Point_3> Project; 00112 typedef Circulator_project 00113 < SHalfedge_around_facet_const_circulator, Project, 00114 const Point_3&, const Point_3*> Circulator; 00115 Halffacet_cycle_const_iterator fc = f->facet_cycles_begin(); 00116 CGAL_assertion(fc.is_shalfedge()); 00117 if (fc.is_shalfedge() ) { 00118 SHalfedge_const_handle se(fc); 00119 SHalfedge_around_facet_const_circulator hfc(se); 00120 Circulator c(hfc), cp(c), cend(c); 00121 do { 00122 c++; 00123 CGAL_NEF_TRACEN("contained on edge "<<Segment_3( *c, *cp)<<"? "<< 00124 Segment_3( *c, *cp).has_on(p)); 00125 if( Segment_3( *c, *cp).has_on(p)) 00126 return true; 00127 cp++; 00128 } 00129 while( c != cend); 00130 } 00131 Halffacet_cycle_const_iterator fe = f->facet_cycles_end(); 00132 ++fc; 00133 CGAL_For_all(fc, fe) { 00134 if (fc.is_shalfloop() ) { 00135 SHalfloop_const_handle l(fc); 00136 CGAL_NEF_TRACEN("isolated point on "<<l->incident_sface()->center_vertex()->point()<<"? "); 00137 if( l->incident_sface()->center_vertex()->point() == p) 00138 return true; 00139 } 00140 else if (fc.is_shalfedge() ) { 00141 SHalfedge_const_handle se(fc); 00142 SHalfedge_around_facet_const_circulator hfc(se); 00143 Circulator c(hfc), cp(c), cend(c); 00144 do { 00145 c++; 00146 CGAL_NEF_TRACEN("contained on edge "<<Segment_3( *c, *cp)<<"? "<< 00147 Segment_3( *c, *cp).has_on(p)); 00148 if( Segment_3( *c, *cp).has_on(p)) 00149 return true; 00150 cp++; 00151 } 00152 while( c != cend); 00153 } 00154 else 00155 CGAL_error_msg( "Damn wrong handle."); 00156 } 00157 return false; 00158 } 00159 00160 #ifdef LINE3_LINE3_INTERSECTION 00161 00162 bool does_intersect_internally( const Segment_3& s1, 00163 const Segment_3& s2, 00164 Point_3& p) const { 00165 CGAL_NEF_TRACEN("does intersect internally with LINE3_LINE3_INTERSECTION"); 00166 if ( s1.is_degenerate() || s2.is_degenerate()) 00167 /* the segment is degenerate so there is not internal intersection */ 00168 return false; 00169 if ( s1.has_on(s2.source()) || s1.has_on(s2.target()) || 00170 s2.has_on(s1.source()) || s2.has_on(s1.target())) 00171 /* the segments does intersect at one endpoint */ 00172 return false; 00173 Object o = intersection(Line_3(ray), Line_3(s)); 00174 if ( !CGAL::assign(p, o)) 00175 return false; 00176 return( does_contain_internally( s, p)); 00177 } 00178 00179 #else // LINE3_LINE3_INTERSECTION 00180 00181 bool does_intersect_internally( const Segment_3& s1, 00182 const Segment_3& s2, 00183 Point_3& p) const { 00184 if(s2.has_on(s1.target())) 00185 return false; 00186 Ray_3 r(s1.source(), s1.target()); 00187 if(!does_intersect_internally(r, s2, p)) 00188 return false; 00189 Plane_3 pl(s1.target(), r.to_vector()); 00190 return (pl.oriented_side(p) == CGAL::NEGATIVE); 00191 } 00192 00193 bool does_intersect_internally( const Ray_3& s1, 00194 const Segment_3& s2, 00195 Point_3& p) const { 00196 CGAL_NEF_TRACEN("does intersect internally without LINE3_LINE3_INTERSECTION"); 00197 CGAL_assertion(!s1.is_degenerate()); 00198 CGAL_assertion(!s2.is_degenerate()); 00199 if ( orientation( s1.source(), s1.point(1), s2.source(), s2.target()) 00200 != COPLANAR) 00201 // the segments doesn't define a plane 00202 return false; 00203 if ( s1.has_on(s2.source()) || s1.has_on(s2.target()) || 00204 s2.has_on(s1.source())) 00205 // the segments does intersect at one endpoint 00206 return false; 00207 Line_3 ls1(s1), ls2(s2); 00208 if ( ls1.direction() == ls2.direction() || 00209 ls1.direction() == -ls2.direction() ) 00210 // the segments are parallel 00211 return false; 00212 Vector_3 vs1(s1.to_vector()), vs2(s2.to_vector()), 00213 vt(cross_product( vs1, vs2)), 00214 ws1(cross_product( vt, vs1)); // , ws2(cross_product( vt, vs2)); 00215 Plane_3 hs1( s1.source(), ws1); 00216 Object o = intersection(hs1, ls2); 00217 CGAL_assertion(CGAL::assign( p, o)); 00218 // since line(s1) and line(s2) are not parallel they intersects in only 00219 // one point 00220 CGAL::assign( p ,o); 00221 Plane_3 pl(s1.source(), vs1); 00222 if(pl.oriented_side(p) != CGAL::POSITIVE) 00223 return false; 00224 pl = Plane_3(s2.source(), vs2); 00225 if(pl.oriented_side(p) != CGAL::POSITIVE) 00226 return false; 00227 pl = Plane_3(s2.target(), vs2); 00228 return (pl.oriented_side(p) == CGAL::NEGATIVE); 00229 } 00230 00231 #endif // LINE3_LINE3_INTERSECTION 00232 00233 bool does_intersect( const Ray_3& r, const Triangle_3& tr, 00234 Point_3& ip) const { 00235 // Intersection between an open ray and 00236 // a closed 2d-triangular region in the space 00237 CGAL_NEF_TRACEN("-> Intersection triangle - ray"); 00238 CGAL_NEF_TRACEN(" -> Ray: "<<r); 00239 CGAL_NEF_TRACEN(" -> Triangle: "<<tr); 00240 CGAL_assertion( !r.is_degenerate()); 00241 Plane_3 h( tr.supporting_plane()); 00242 CGAL_assertion( !h.is_degenerate()); 00243 if( h.has_on( r.source())) 00244 return false; 00245 Object o = intersection( h, r); 00246 if( !CGAL::assign( ip, o)) 00247 return false; 00248 CGAL_NEF_TRACEN(" -> intersection point: "<<ip); 00249 return tr.has_on(ip); 00250 } 00251 00252 bool does_intersect( const Segment_3& s, const Triangle_3& tr, 00253 Point_3& ip) const { 00254 // Intersection between a open segment and 00255 // a closed 2d-triangular region in the space 00256 CGAL_NEF_TRACEN("-> Intersection triangle - segment"); 00257 CGAL_NEF_TRACEN(" -> Segment: "<<s); 00258 CGAL_NEF_TRACEN(" -> Triangle: "<<tr); 00259 CGAL_assertion( !s.is_degenerate()); 00260 Plane_3 h( tr.supporting_plane()); 00261 CGAL_assertion( !h.is_degenerate()); 00262 if( h.has_on( s.source()) || h.has_on( s.target())) 00263 return false; 00264 Object o = intersection( h, s); 00265 if( !CGAL::assign( ip, o)) 00266 return false; 00267 CGAL_NEF_TRACEN(" -> intersection point: "<<ip); 00268 return tr.has_on(ip); 00269 } 00270 00271 bool does_intersect_internally( const Ray_3& ray, 00272 Halffacet_const_handle f, 00273 Point_3& p, 00274 bool checkHasOn = true) const { 00275 CGAL_NEF_TRACEN("-> Intersection facet - ray"); 00276 Plane_3 h( f->plane()); 00277 CGAL_NEF_TRACEN("-> facet's plane: " << h); 00278 CGAL_NEF_TRACEN("-> a point on the plane: " << h.point()); 00279 CGAL_NEF_TRACEN("-> ray: " << ray); 00280 CGAL_assertion(!ray.is_degenerate()); 00281 if(checkHasOn) { 00282 if(h.has_on(ray.source())) 00283 return false; 00284 } else 00285 CGAL_assertion(!h.has_on(ray.source())); 00286 Object o = intersection( h, ray); 00287 if( !CGAL::assign( p, o)) 00288 return false; 00289 CGAL_NEF_TRACEN( "-> intersection point: " << p ); 00290 CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p)); 00291 return does_contain_internally( f, p, false); 00292 } 00293 00294 #ifdef CGAL_NEF3_FACET_WITH_BOX 00295 bool does_intersect_internally( const Ray_3& ray, 00296 Partial_facet pf, 00297 Point_3& p) const { 00298 CGAL_NEF_TRACEN("-> Intersection facet - ray"); 00299 Plane_3 h( pf.f->plane()); 00300 CGAL_NEF_TRACEN("-> facet's plane: " << h); 00301 CGAL_NEF_TRACEN("-> a point on the plane: " << h.point()); 00302 CGAL_NEF_TRACEN("-> ray: " << ray); 00303 CGAL_assertion(!ray.is_degenerate()); 00304 if( h.has_on( ray.source())) 00305 /* no possible internal intersection */ 00306 return false; 00307 Object o = intersection( h, ray); 00308 if( !CGAL::assign( p, o)) 00309 return false; 00310 CGAL_NEF_TRACEN( "-> intersection point: " << p ); 00311 // CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p)); 00312 return does_contain_internally( pf, p, false); 00313 } 00314 #endif 00315 00316 bool does_intersect_internally( const Segment_3& seg, 00317 Halffacet_const_handle f, 00318 Point_3& p) const { 00319 CGAL_NEF_TRACEN("-> Intersection facet - segment"); 00320 Plane_3 h( f->plane()); 00321 CGAL_NEF_TRACEN("-> facet's plane: " << h); 00322 CGAL_NEF_TRACEN("-> a point on the plane: " << h.point()); 00323 CGAL_NEF_TRACEN("-> segment: " << seg); 00324 CGAL_assertion(!seg.is_degenerate()); 00325 if( h.has_on( seg.source()) || h.has_on(seg.target())) 00326 /* no possible internal intersection */ 00327 return false; 00328 return does_intersect(seg, f, p); 00329 } 00330 00331 bool does_intersect(const Segment_3& seg, 00332 Halffacet_const_handle f, 00333 Point_3& p) const { 00334 Plane_3 h( f->plane()); 00335 Object o = intersection( h, seg); 00336 if( !CGAL::assign( p, o)) 00337 return false; 00338 CGAL_NEF_TRACEN( "-> intersection point: " << p ); 00339 CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p)); 00340 return( does_contain_internally( f, p, false)); 00341 } 00342 00343 #ifdef CGAL_NEF3_FACET_WITH_BOX 00344 bool does_intersect_internally( const Segment_3& seg, 00345 Partial_facet pf, 00346 Point_3& p) const { 00347 CGAL_NEF_TRACEN("-> Intersection partial facet - segment"); 00348 Plane_3 h( pf.f->plane()); 00349 CGAL_NEF_TRACEN("-> facet's plane: " << h); 00350 CGAL_NEF_TRACEN("-> a point on the plane: " << h.point()); 00351 CGAL_NEF_TRACEN("-> segment: " << seg); 00352 CGAL_assertion(!seg.is_degenerate()); 00353 if( h.has_on( seg.source()) || h.has_on(seg.target())) 00354 /* no possible internal intersection */ 00355 return false; 00356 Object o = intersection( h, seg); 00357 if( !CGAL::assign( p, o)) 00358 return false; 00359 CGAL_NEF_TRACEN( "-> intersection point: " << p ); 00360 // CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p)); 00361 return( does_contain_internally( pf, p, false)); 00362 } 00363 #endif 00364 00365 Bounded_side locate_point_in_halffacet( const Point_3& p, 00366 Halffacet_const_handle f) const { 00367 CGAL_NEF_TRACEN("locate point in halffacet " << p << ", " << f->plane()); 00368 typedef Project_shalfedge_point 00369 < SHalfedge, const Point_3> Project; 00370 typedef Circulator_project 00371 < SHalfedge_around_facet_const_circulator, Project, 00372 const Point_3&, const Point_3*> Circulator; 00373 typedef Container_from_circulator<Circulator> Container; 00374 00375 Plane_3 h(f->plane()); 00376 CGAL_assertion(h.has_on(p)); 00377 Halffacet_cycle_const_iterator fc = f->facet_cycles_begin(); 00378 Bounded_side outer_bound_pos(CGAL::ON_BOUNDARY); 00379 if (fc.is_shalfedge() ) { 00380 SHalfedge_const_handle se(fc); 00381 SHalfedge_around_facet_const_circulator hfc(se); 00382 Circulator c(hfc); 00383 Container ct(c); 00384 CGAL_assertion( !is_empty_range(ct.begin(), ct.end())); 00385 outer_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h); 00386 } 00387 else 00388 CGAL_error_msg( "is facet first cycle a SHalfloop?"); 00389 if( outer_bound_pos != CGAL::ON_BOUNDED_SIDE ) 00390 return outer_bound_pos; 00391 /* The point p is not in the relative interior of the outer face cycle 00392 so it is not necesary to know the possition of p with respect to the 00393 inner face cycles */ 00394 Halffacet_cycle_const_iterator fe = f->facet_cycles_end(); 00395 ++fc; 00396 if( fc == fe ) 00397 return outer_bound_pos; 00398 Bounded_side inner_bound_pos(CGAL::ON_BOUNDARY); 00399 CGAL_For_all(fc, fe) { 00400 if (fc.is_shalfloop() ) { 00401 SHalfloop_const_handle l(fc); 00402 if(l->incident_sface()->center_vertex()->point() == p ) 00403 inner_bound_pos = CGAL::ON_BOUNDARY; 00404 else 00405 inner_bound_pos = CGAL::ON_UNBOUNDED_SIDE; 00406 } 00407 else if (fc.is_shalfedge() ) { 00408 SHalfedge_const_handle se(fc); 00409 SHalfedge_around_facet_const_circulator hfc(se); 00410 Circulator c(hfc); 00411 Container ct(c); 00412 CGAL_assertion( !is_empty_range(ct.begin(), ct.end())); 00413 inner_bound_pos = bounded_side_3( ct.begin(), ct.end(), 00414 p, h.opposite()); 00415 } 00416 else 00417 CGAL_error_msg( "Damn wrong handle."); 00418 if( inner_bound_pos != CGAL::ON_UNBOUNDED_SIDE ) 00419 return opposite(inner_bound_pos); 00420 /* At this point the point p belongs to relative interior of the facet's 00421 outer cycle, and its possition is completely known when it belongs 00422 to the clousure of any inner cycle */ 00423 } 00424 return CGAL::ON_BOUNDED_SIDE; 00425 } 00426 00427 #ifdef CGAL_NEF3_FACET_WITH_BOX 00428 Bounded_side locate_point_in_halffacet( const Point_3& p, 00429 Partial_facet pf) const { 00430 00431 if(p.x() < pf.f->b.min_coord(0) || p.x() > pf.f->b.max_coord(0) || 00432 p.y() < pf.f->b.min_coord(1) || p.y() > pf.f->b.max_coord(1) || 00433 p.z() < pf.f->b.min_coord(2) || p.z() > pf.f->b.max_coord(2)) 00434 return CGAL::ON_UNBOUNDED_SIDE; 00435 00436 typedef Project_shalfedge_point 00437 < SHalfedge, Point_3> Project; 00438 typedef Circulator_project 00439 < SHalfedge_around_facet_const_circulator, Project, 00440 const Point_3&, const Point_3*> Circulator; 00441 typedef Container_from_circulator<Circulator> Container; 00442 00443 typedef typename Partial_facet::Outer_cycle_iterator Outer_cycle_iterator; 00444 typedef typename Partial_facet::Inner_cycle_iterator Inner_cycle_iterator; 00445 typedef typename Partial_facet::Isolated_vertex_iterator Isolated_vertex_iterator; 00446 00447 Plane_3 h(pf.f->plane()); 00448 CGAL_assertion(h.has_on(p)); 00449 00450 Bounded_side outer_bound_pos(CGAL::ON_BOUNDED_SIDE); 00451 00452 Outer_cycle_iterator oc = pf.outer_cycles_begin(); 00453 while(oc != pf.outer_cycles_end() && 00454 outer_bound_pos == CGAL::ON_BOUNDED_SIDE) { 00455 if(oc->first == oc->second) { 00456 SHalfedge_around_facet_const_circulator hfc(oc->first); 00457 Circulator c(hfc); 00458 Container ct(c); 00459 CGAL_assertion( !is_empty_range(ct.begin(), ct.end())); 00460 outer_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h); 00461 } else { 00462 outer_bound_pos = bounded_side_3(Circulator(SHalfedge_around_facet_const_circulator(oc->first)), 00463 Circulator(SHalfedge_around_facet_const_circulator(oc->second)), p, h); 00464 } 00465 ++oc; 00466 } 00467 if(outer_bound_pos != CGAL::ON_BOUNDED_SIDE ) 00468 return outer_bound_pos; 00469 00470 Bounded_side inner_bound_pos(CGAL::ON_UNBOUNDED_SIDE); 00471 00472 Inner_cycle_iterator ic = pf.inner_cycles_begin(); 00473 while(ic != pf.inner_cycles_end() && 00474 inner_bound_pos == CGAL::ON_UNBOUNDED_SIDE) { 00475 if(ic->first == ic->second) { 00476 SHalfedge_around_facet_const_circulator hfc(ic->first); 00477 Circulator c(hfc); 00478 Container ct(c); 00479 CGAL_assertion( !is_empty_range(ct.begin(), ct.end())); 00480 inner_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h); 00481 } else { 00482 inner_bound_pos = bounded_side_3(Circulator(SHalfedge_around_facet_const_circulator(ic->first)), 00483 Circulator(SHalfedge_around_facet_const_circulator(ic->second)), p, h); 00484 } 00485 ++ic; 00486 } 00487 if(inner_bound_pos != CGAL::ON_UNBOUNDED_SIDE ) 00488 return opposite(inner_bound_pos); 00489 00490 Isolated_vertex_iterator iv = pf.isolated_vertices_begin(); 00491 while(iv != pf.isolated_vertices_end()) { 00492 if(*iv == p) 00493 return CGAL::ON_BOUNDARY; 00494 ++iv; 00495 } 00496 00497 return CGAL::ON_BOUNDED_SIDE; 00498 } 00499 #endif 00500 }; // SNC_intersection 00501 00502 CGAL_END_NAMESPACE 00503 00504 #endif //CGAL_SNC_INTERSECTION_H
1.7.6.1
