pm_point_locator.h

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

  bool ray_shoot_from_outer_facet(Segment& s, object_kind& current, 
				  Vertex_const_handle &v, 
				  Halfedge_const_handle& e,
				  const Tag_false& ) const {
    CGAL_NEF_TRACEN("target on outer facet");
    Point p = this->K.source(s);
    Vertex_const_handle v1 = CT.vertices_begin();
    Halfedge_const_handle e1 = CT.twin(CT.first_out_edge(v1));
    Halfedge_around_face_const_circulator circ(e1), end(circ);
    Point i;
    Segment seg;
    bool found = false;
    CGAL_For_all(circ, end) {
      //	std::cerr << s << std::endl;
      //	std::cerr << point(source(circ)) << "->" << point(target(circ)) << std::endl;
      Object o = intersection(s, Segment(point(source(circ)), 
					 point(target(circ))));

      if(assign(i,o)) {
	CGAL_NEF_TRACEN("intersection in point " << i);
	found = true;
	s = Segment(p,i);
	if(i == point(source(circ))) {
	  current = VERTEX;
	  v = source(circ);
	} else if(i == point(target(circ))) {
	  current = VERTEX;
	  v = target(circ);
	} else {	 
	  current = EDGE_CROSSING;
	  e = circ;
	}
      } else if(assign(seg,o)) {
	found = true;
	CGAL_NEF_TRACEN("overlap of segments");
	current = EDGE_COLLINEAR;
	e = circ;
      }
    }
    return found;
  }

  template <typename Object_predicate>
  Object_handle ray_shoot(const Segment& ss, const Object_predicate& M) const
  /*{\Mop returns an |Object_handle o| which can be converted to a
  |Vertex_const_handle|, |Halfedge_const_handle|, |Face_const_handle|
  |h| as described above.  The object predicate |M| has to have 
  function operators\\
  |bool operator() (const Vertex_/ Halfedge_/Face_const_handle&) const|.\\
  The object returned is intersected by the segment |s| and has minimal
  distance to |s.source()| and |M(h)| holds on the converted object. The
  operation returns the null handle |NULL| if the ray shoot along |s|
  does not hit any object |h| of |P| with |M(h)|.}*/
  { Segment s(ss);
    CGAL_NEF_TRACEN("ray_shoot "<<s);
    CGAL_assertion( !this->K.is_degenerate(s) );
    Point p = this->K.source(s);
    Direction d = this->K.construct_direction(p,s.target()); 
    Vertex_const_handle v;
    Halfedge_const_handle e;
    object_kind current;
    Object_handle h = LOCATE_IN_TRIANGULATION(p);
    if ( assign(v,h) ) {
      CGAL_NEF_TRACEN("located vertex "<<PV(v));
      current = VERTEX;
    } else if ( assign(e,h) ) {
      CGAL_NEF_TRACEN("located edge "<<PE(e));
      int orientation_ = this->K.orientation( segment(e), p);
      if ( orientation_ == 0 ) { // p on segment
        CGAL_NEF_TRACEN("on edge "<<PE(e));
        if ( d == CT.direction(e) ) 
        { current = EDGE_COLLINEAR; }
        else if ( d == CT.direction(CT.twin(e)) ) 
        { e = CT.twin(e); current = EDGE_COLLINEAR; }
        else { // crossing
          current = EDGE_CROSSING;
          if ( !(this->K.orientation(CT.segment(e),s.target())>0) ) // not left_turn
            e = CT.twin(e); 
        }

      } else { // p not on segment, thus in triangle
        if ( orientation_ < 0  ) e = CT.twin(e);
        // now p left of e
        CGAL_NEF_TRACEN("in face at "<<PE(e));
        if ( M(input_face(e)) ) // face mark
          return Object_handle(input_face(e));

        Point p1 = CT.point(CT.source(e)), 
              p2 = CT.point(CT.target(e)), 
              p3 = CT.point(CT.target(next(e)));
        int or1 = this->K.orientation(p,s.target(),p1);
        int or2 = this->K.orientation(p,s.target(),p2);
        int or3 = this->K.orientation(p,s.target(),p3);
        if ( or1 == 0 && !this->K.left_turn(p1,p2,s.target()) )
        { v = CT.source(e); current = VERTEX; }
        else if ( or2 == 0 && !this->K.left_turn(p2,p3,s.target()) )
        { v = CT.target(e); current = VERTEX; }
        else if ( or3 == 0 && !this->K.left_turn(p3,p1,s.target()) )
        { v = CT.target(CT.next(e)); current = VERTEX; }
        else if ( or2 > 0 && or1 < 0 && !this->K.left_turn(p1,p2,s.target()) )
        { e = CT.twin(e); current = EDGE_CROSSING; }
        else if ( or3 > 0 && or2 < 0 && !this->K.left_turn(p2,p3,s.target()) )
        { e = CT.twin(CT.next(e)); current = EDGE_CROSSING; }
        else if ( or1 > 0 && or3 < 0 && !this->K.left_turn(p3,p1,s.target()) )
        { e = CT.twin(CT.previous(e)); current = EDGE_CROSSING; }
        else return Object_handle();

      }
    } else {

      if(check_tag(typename Is_extended_kernel<Geometry>::value_type())) {
	CGAL_assertion_msg(false, "code is only for Bounded_kernel");
      }
      if(!ray_shoot_from_outer_facet(s,current,v,e,typename Is_extended_kernel<Geometry>::value_type()))
	return Object_handle();
    }

    CGAL_NEF_TRACEN("current = " << current);
    if(current == VERTEX)
      CGAL_NEF_TRACEN(point(v));

    while (true) switch ( current ) {
      case VERTEX:
        { CGAL_NEF_TRACEN("vertex "<<CT.point(v));
          Vertex_const_handle v_org = input_vertex(v);
          if ( M(v_org) ) return Object_handle(v_org);
          if ( CT.point(v) == s.target() ) return Object_handle();
          // stop walking at s.target(), or determine next object on s:
          bool collinear;
          Halfedge_const_handle e_out = CT.out_wedge(v,d,collinear);
          if (collinear) // ray shoot via e_out
          { e = e_out; current = EDGE_COLLINEAR; }
          else { // ray shoot in wedge left of e_out
            if ( M(input_face(e_out)) )
              return Object_handle(input_face(e_out));
            e = CT.twin(CT.next(e_out)); current = EDGE_CROSSING;
          }
        }

        break;
      case EDGE_CROSSING:
        { CGAL_NEF_TRACEN("crossing edge "<<segment(e));
          if ( this->K.orientation(CT.segment(e),s.target()) == 0 ) 
            return Object_handle();
          Halfedge_const_handle e_org = input_halfedge(e);
          if ( e_org != Halfedge_const_handle() ) { // not a CT edge
            if ( M(e_org) ) return Object_handle(e_org);
            if ( M(face(e_org)) ) return Object_handle(face(e_org));
          }
          Vertex_const_handle v_cand = CT.target(CT.next(e));
          CGAL_NEF_TRACEN("v_cand "<<PV(v_cand));
          int orientation_ = this->K.orientation(p,s.target(),CT.point(v_cand));
          switch( orientation_ ) {
            case 0: 
              v = v_cand; current = VERTEX; break;
            case +1: 
              e = CT.twin(CT.next(e)); current = EDGE_CROSSING; break;
            case -1: 
              e = CT.twin(CT.previous(e)); current = EDGE_CROSSING; break;
          }
        }

        break;
      case EDGE_COLLINEAR:
        { CGAL_NEF_TRACEN("collinear edge "<<CT.segment(e));
          Halfedge_const_handle e_org = input_halfedge(e);
          if ( e_org == Halfedge_const_handle() ) { // a CT edge
            if ( M(input_face(e)) ) 
              return Object_handle(input_face(e));
          } else { // e_org is not a CT edge
            if ( M(e_org) )
              return Object_handle(e_org);
          }
          if ( this->K.strictly_ordered_along_line(
                 CT.point(CT.source(e)),s.target(),CT.point(CT.target(e))) ) 
            return Object_handle();
          v = CT.target(e); current = VERTEX;
        }

        break;
    } 
    // assert(0); return h; // compiler warning
  }

  bool within_outer_cycle(Vertex_const_handle , 
			  const Point& , const Tag_true& ) const {
    return true;
  }

  bool within_outer_cycle(Vertex_const_handle v, 
			  const Point& q, const Tag_false& ) const {
    typedef Project_halfedge_point<typename Decorator::Halfedge, Point> Project;
    typedef Circulator_project<Halfedge_around_face_const_circulator, 
      Project, const Point&, const Point*> Circulator;
    typedef Container_from_circulator<Circulator> Container;
    
    Halfedge_const_handle e_min = CT.twin(CT.first_out_edge(v));
    Halfedge_around_face_const_circulator circ(e_min);
    Circulator c(circ);
    Container ct(c); 
    if(is_empty_range(ct.begin(), ct.end()) ||
       bounded_side_2(ct.begin(), ct.end(),q) == CGAL::ON_UNBOUNDED_SIDE)
      return false;
    
    return true;
  }

  Object_handle walk_in_triangulation(const Point& p) const;

}; // PM_point_locator<PM_decorator_,Geometry_>


#ifdef CGAL_USING_PPL
static const char* const pointlocationversion ="point location via pers dicts";
#else
static const char* const pointlocationversion ="point location via seg walks";
#endif

template <typename PMD, typename GEO>
PM_point_locator<PMD,GEO>::
PM_point_locator(const Plane_map& P, const Geometry& k) :
  Base(P,k), CT(*(new Plane_map),k)

{ CGAL_NEF_TRACEN("PM_point_locator construction");
  CT.clone_skeleton(P,CT_link_to_original(CT,*this));
  triangulate_CT();
  minimize_weight_CT();
  #ifdef CGAL_USING_PPL
  pPPL = new PMPP_locator(CT,PMPPLT(K));
  #endif

}

template <typename PMD, typename GEO>
PM_point_locator<PMD,GEO>::
~PM_point_locator()
{ CGAL_NEF_TRACEN("clear_static_point_locator");
  Vertex_iterator vit, vend = CT.vertices_end();
  for (vit = CT.vertices_begin(); vit != vend; ++vit) {
    geninfo<VF_pair>::clear(CT.info(vit));
  }
  Halfedge_iterator eit, eend = CT.halfedges_end();
  for (eit = CT.halfedges_begin(); eit != eend; ++eit) {
    geninfo<EF_pair>::clear(CT.info(eit));
  }
  CT.clear();
  delete &(CT.plane_map());
  #ifdef CGAL_USING_PPL
  delete pPPL; pPPL=0; 
  #endif
}

template <typename PMD, typename GEO>
typename PM_point_locator<PMD,GEO>::Object_handle  
PM_point_locator<PMD,GEO>::walk_in_triangulation(const Point& q) const
{ 
  CGAL_NEF_TRACEN("walk in triangulation "<<q);

  Vertex_const_handle v = CT.vertices_begin();

  if(!check_tag(typename Is_extended_kernel<GEO>::value_type()))
    if(!within_outer_cycle(v,q,typename Is_extended_kernel<Geometry>::value_type()))
      return Object_handle();

  Halfedge_const_handle e;
  Point p = CT.point(v);
  if ( p == q ) return Object_handle(v);
  //  Segment s = this->K.construct_segment(p,q);
  Direction dir = this->K.construct_direction(p,q);
  object_kind current = VERTEX;
  while (true) switch ( current ) {
    case VERTEX:
      { 
        CGAL_NEF_TRACEN("vertex "<<CT.point(v));
        if ( CT.point(v) == q ) 
          return Object_handle(v); // stop walking at q
        bool collinear;
        Halfedge_const_handle e_out = CT.out_wedge(v,dir,collinear);
        if (collinear) // ray shoot via e_out
        { e = e_out; current = EDGE_COLLINEAR; }
        else  // ray shoot in wedge left of e_out
        { e = CT.twin(CT.next(e_out)); current = EDGE_CROSSING; }
      }

      break;
    case EDGE_CROSSING:
      { CGAL_NEF_TRACEN("crossing edge "<<CT.segment(e));
        if ( !(this->K.orientation(CT.segment(e),q) > 0) ) // q not left of e
          return Object_handle(e);
        Vertex_const_handle v_cand = CT.target(CT.next(e));
        int orientation_ = this->K.orientation(p,q,CT.point(v_cand));
        switch( orientation_ ) {
          case 0:  // collinear 
            if ( this->K.strictly_ordered_along_line(p,q,CT.point(v_cand)) ) 
              return Object_handle(e);
            v = v_cand; current = VERTEX; break;
          case +1: // left_turn
            e = twin(next(e)); current = EDGE_CROSSING; break;
          case -1: 
            e = twin(previous(e)); current = EDGE_CROSSING; break;
        }
      }

      break;
    case EDGE_COLLINEAR:
      { CGAL_NEF_TRACEN("collinear edge "<<CT.segment(e));
        if ( this->K.strictly_ordered_along_line(
               CT.point(CT.source(e)),q,CT.point(CT.target(e))) ) 
          return Object_handle(e);
        v = CT.target(e); current = VERTEX;
      }

      break;
  }
#if !defined(__BORLANDC__)
  return Object_handle(); // never reached warning acceptable
#endif
}


CGAL_END_NAMESPACE

#endif // CGAL_PM_POINT_LOCATOR_H