pm_point_locator.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 879 行 · 第 1/3 页

    #ifdef CGAL_USING_PPL
    pPPL = 0;
    #endif
 
  }

  /*{\Moptions constref=yes}*/
  PM_point_locator(const Plane_map& P, const Geometry& k = Geometry());
  /*{\Mcreate constructs a point locator working on |P|.}*/

  ~PM_point_locator();

  /*{\Moperations 2.5 0.5}*/

  const Decorator& triangulation() const { return CT; }
  /*{\Mop access to the constrained triangulation structure that
  is superimposed to |P|.}*/
  /*{\Moptions constref=no}*/

  
  Object_handle locate(const Point& p) const
  /*{\Mop returns a generic handle |h| to an object (vertex, halfedge,
  face) of |P| which contains the point |p| in its relative
  interior.}*/
  { 
    Object_handle h = LOCATE_IN_TRIANGULATION(p); 
    Vertex_const_handle v_triang;
    if ( assign(v_triang,h) ) {
      return input_object(v_triang);
    } 
    Halfedge_const_handle e_triang;
    if ( assign(e_triang,h) ) {
      Halfedge_const_handle e = input_halfedge(e_triang);
      if ( e == Halfedge_const_handle() ) // inserted during triangulation
        return Object_handle(input_face(e_triang)); 
      int orientation_ = this->K.orientation(segment(e),p);
      if ( orientation_ == 0 ) return Object_handle(e);
      if ( orientation_ < 0 )  return Object_handle(face(twin(e)));
      if ( orientation_ > 0 )  return Object_handle(face(e));
    }
    assert(0); return h; // compiler warning
  }

  
  template <typename Object_predicate>
  Object_handle ray_shoot(const Segment& s, 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)|.}*/
  { CGAL_NEF_TRACEN("ray_shoot "<<s);
    CGAL_assertion( !this->K.is_degenerate(s) );
    Point p = this->K.source(s), q = this->K.target(s);
    Direction d = this->K.construct_direction(p,q); 
    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;
    }  

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

      }
    }

    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) == q ) return Object_handle();
          // stop walking at q, 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),q) == 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,q,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)),q,CT.point(CT.target(e))) ) 
            return Object_handle();
          v = CT.target(e); current = VERTEX;
        }

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


  Object_handle walk_in_triangulation(const Point& p) const;


  enum object_kind { VERTEX, EDGE_CROSSING, EDGE_COLLINEAR };
}; // 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();
  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