snc_intersection.h

很多二维 三维几何计算算法 C++ 类库

    Plane_3 h( tr.supporting_plane());
    CGAL_assertion( !h.is_degenerate());
    if( h.has_on( s.source()) || h.has_on( s.target()))
      return false;
    Object o = intersection( h, s);
    if( !CGAL::assign( ip, o))
      return false;
    CGAL_NEF_TRACEN(" -> intersection point: "<<ip);
    return tr.has_on(ip);
  }

  bool does_intersect_internally( const Ray_3& ray,
				  Halffacet_const_handle f,
				  Point_3& p) const { 
    CGAL_NEF_TRACEN("-> Intersection facet - ray");
    Plane_3 h( f->plane());
    CGAL_NEF_TRACEN("-> facet's plane: " << h);
    CGAL_NEF_TRACEN("-> a point on the plane: " << h.point());
    CGAL_NEF_TRACEN("-> ray: " << ray);
    if( ray.is_degenerate())
      /* no possible internal intersection */
      return false;
    if( h.has_on( ray.source()))
      /* no possible internal intersection */
	return false;
    Object o = intersection( h, ray);
    if( !CGAL::assign( p, o))
      return false;
    CGAL_NEF_TRACEN( "-> intersection point: " << p );
    CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p));
    return does_contain_internally( f, p, false);
  }

#ifdef CGAL_NEF3_FACET_WITH_BOX
  bool does_intersect_internally( const Ray_3& ray,
				  Partial_facet pf,
				  Point_3& p) const { 
    CGAL_NEF_TRACEN("-> Intersection facet - ray");
    Plane_3 h( pf.f->plane());
    CGAL_NEF_TRACEN("-> facet's plane: " << h);
    CGAL_NEF_TRACEN("-> a point on the plane: " << h.point());
    CGAL_NEF_TRACEN("-> ray: " << ray);
    if( ray.is_degenerate())
      /* no possible internal intersection */
      return false;
    if( h.has_on( ray.source()))
      /* no possible internal intersection */
	return false;
    Object o = intersection( h, ray);
    if( !CGAL::assign( p, o))
      return false;
    CGAL_NEF_TRACEN( "-> intersection point: " << p );
    //    CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p));
    return does_contain_internally( pf, p, false);
  }
#endif

  bool does_intersect_internally( const Segment_3& seg,
				  Halffacet_const_handle f,
				  Point_3& p) const { 
    CGAL_NEF_TRACEN("-> Intersection facet - segment");
    Plane_3 h( f->plane());
    CGAL_NEF_TRACEN("-> facet's plane: " << h);
    CGAL_NEF_TRACEN("-> a point on the plane: " << h.point());
    CGAL_NEF_TRACEN("-> segment: " << seg);
    if( seg.is_degenerate())
      /* no possible internal intersection */
      return false;
    if( h.has_on( seg.source()) || h.has_on(seg.target()))
      /* no possible internal intersection */
      return false;
    return does_intersect(seg, f, p);
  }

  bool does_intersect(const Segment_3& seg,
		      Halffacet_const_handle f,
		      Point_3& p) const {
    Plane_3 h( f->plane());
    Object o = intersection( h, seg);
    if( !CGAL::assign( p, o))
      return false;
    CGAL_NEF_TRACEN( "-> intersection point: " << p );
    CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p));
    return( does_contain_internally( f, p, false));
  }

#ifdef CGAL_NEF3_FACET_WITH_BOX
  bool does_intersect_internally( const Segment_3& seg,
				  Partial_facet pf,
				  Point_3& p) const { 
    CGAL_NEF_TRACEN("-> Intersection partial facet - segment");
    Plane_3 h( pf.f->plane());
    CGAL_NEF_TRACEN("-> facet's plane: " << h);
    CGAL_NEF_TRACEN("-> a point on the plane: " << h.point());
    CGAL_NEF_TRACEN("-> segment: " << seg);
    if( seg.is_degenerate())
      /* no possible internal intersection */
      return false;
    if( h.has_on( seg.source()) || h.has_on(seg.target()))
      /* no possible internal intersection */
      return false;
    Object o = intersection( h, seg);
    if( !CGAL::assign( p, o))
      return false;
    CGAL_NEF_TRACEN( "-> intersection point: " << p );
    //    CGAL_NEF_TRACEN( "-> point in facet interior? "<<does_contain_internally( f, p));
    return( does_contain_internally( pf, p, false));
  }
#endif

  Bounded_side locate_point_in_halffacet( const Point_3& p, 
					  Halffacet_const_handle f) const {
    typedef Project_shalfedge_point
      < SHalfedge, const Point_3> Project;
    typedef Circulator_project
      < SHalfedge_around_facet_const_circulator, Project, 
      const Point_3&, const Point_3*> Circulator;
    typedef Container_from_circulator<Circulator> Container;

    Plane_3 h(f->plane());
    CGAL_assertion(h.has_on(p));
    Halffacet_cycle_const_iterator fc = f->facet_cycles_begin();
    Bounded_side outer_bound_pos(CGAL::ON_BOUNDARY);
    if (fc.is_shalfedge() ) {
      SHalfedge_const_handle se(fc);
      SHalfedge_around_facet_const_circulator hfc(se);
      Circulator c(hfc);
      Container ct(c);
      CGAL_assertion( !is_empty_range(ct.begin(), ct.end()));
      outer_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h);
    } 
    else 
      CGAL_assertion_msg(0, "is facet first cycle a SHalfloop?");
    if( outer_bound_pos != CGAL::ON_BOUNDED_SIDE )
      return outer_bound_pos;
    /* The point p is not in the relative interior of the outer face cycle
       so it is not necesary to know the possition of p with respect to the 
       inner face cycles */
    Halffacet_cycle_const_iterator fe = f->facet_cycles_end();
    ++fc;
    if( fc == fe )
      return outer_bound_pos;
    Bounded_side inner_bound_pos(CGAL::ON_BOUNDARY);
    CGAL_For_all(fc, fe) {
      if (fc.is_shalfloop() ) {
	SHalfloop_const_handle l(fc);
        if(l->incident_sface()->center_vertex()->point() == p )
	  inner_bound_pos = CGAL::ON_BOUNDARY;
	else
	  inner_bound_pos = CGAL::ON_UNBOUNDED_SIDE;
      } 
      else if (fc.is_shalfedge() ) {
	SHalfedge_const_handle se(fc);
	SHalfedge_around_facet_const_circulator hfc(se);
	Circulator c(hfc);
	Container ct(c);
	CGAL_assertion( !is_empty_range(ct.begin(), ct.end()));
        inner_bound_pos = bounded_side_3( ct.begin(), ct.end(), 
					  p, h.opposite());
      } 
      else 
	CGAL_assertion_msg(0, "Damn wrong handle.");
      if( inner_bound_pos != CGAL::ON_UNBOUNDED_SIDE )
	return opposite(inner_bound_pos);
      /* At this point the point p belongs to relative interior of the facet's
	 outer cycle, and its possition is completely known when it belongs
	 to the clousure of any inner cycle */
    }
    return CGAL::ON_BOUNDED_SIDE;
  }

#ifdef CGAL_NEF3_FACET_WITH_BOX
  Bounded_side locate_point_in_halffacet( const Point_3& p, 
					 Partial_facet pf) const {

    if(p.x() < pf.f->b.min_coord(0) || p.x() > pf.f->b.max_coord(0) ||
       p.y() < pf.f->b.min_coord(1) || p.y() > pf.f->b.max_coord(1) ||
       p.z() < pf.f->b.min_coord(2) || p.z() > pf.f->b.max_coord(2))
      return CGAL::ON_UNBOUNDED_SIDE;
    
    typedef Project_shalfedge_point
      < SHalfedge, Point_3> Project;
    typedef Circulator_project
      < SHalfedge_around_facet_const_circulator, Project, 
      const Point_3&, const Point_3*> Circulator;
    typedef Container_from_circulator<Circulator> Container;

    typedef typename Partial_facet::Outer_cycle_iterator  Outer_cycle_iterator;
    typedef typename Partial_facet::Inner_cycle_iterator  Inner_cycle_iterator;
    typedef typename Partial_facet::Isolated_vertex_iterator Isolated_vertex_iterator;

    Plane_3 h(pf.f->plane());
    CGAL_assertion(h.has_on(p));
    
    Bounded_side outer_bound_pos(CGAL::ON_BOUNDED_SIDE);

    Outer_cycle_iterator oc = pf.outer_cycles_begin();
    while(oc != pf.outer_cycles_end() && 
	  outer_bound_pos == CGAL::ON_BOUNDED_SIDE) {
      if(oc->first == oc->second) {
	SHalfedge_around_facet_const_circulator hfc(oc->first);
	Circulator c(hfc);
	Container ct(c);
	CGAL_assertion( !is_empty_range(ct.begin(), ct.end()));
	outer_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h);	
      } else {
	outer_bound_pos = bounded_side_3(Circulator(SHalfedge_around_facet_const_circulator(oc->first)), 
					 Circulator(SHalfedge_around_facet_const_circulator(oc->second)), p, h);
      }
      ++oc;
    }
    if(outer_bound_pos != CGAL::ON_BOUNDED_SIDE )
      return outer_bound_pos;    

    Bounded_side inner_bound_pos(CGAL::ON_UNBOUNDED_SIDE);

    Inner_cycle_iterator ic = pf.inner_cycles_begin();
    while(ic != pf.inner_cycles_end() && 
	  inner_bound_pos == CGAL::ON_UNBOUNDED_SIDE) {
      if(ic->first == ic->second) {
	SHalfedge_around_facet_const_circulator hfc(ic->first);
	Circulator c(hfc);
	Container ct(c);
	CGAL_assertion( !is_empty_range(ct.begin(), ct.end()));
	inner_bound_pos = bounded_side_3(ct.begin(), ct.end(), p, h);	
      } else {
	inner_bound_pos = bounded_side_3(Circulator(SHalfedge_around_facet_const_circulator(ic->first)), 
					 Circulator(SHalfedge_around_facet_const_circulator(ic->second)), p, h);
      }
      ++ic;
    }
    if(inner_bound_pos != CGAL::ON_UNBOUNDED_SIDE )
      return opposite(inner_bound_pos);
    
    Isolated_vertex_iterator iv = pf.isolated_vertices_begin();
    while(iv != pf.isolated_vertices_end()) {
      if(*iv == p)
	return CGAL::ON_BOUNDARY;
      ++iv;
    }
   
    return CGAL::ON_BOUNDED_SIDE;
  }
#endif
}; // SNC_intersection

CGAL_END_NAMESPACE

#endif //CGAL_SNC_INTERSECTION_H