pm_point_locator.h

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

// Copyright (c) 1997-2000  Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Nef_2/include/CGAL/Nef_2/PM_point_locator.h $
// $Id: PM_point_locator.h 37244 2007-03-19 08:25:43Z afabri $
// 
//
// Author(s)     : Michael Seel <[e-mail]>
#ifndef CGAL_PM_POINT_LOCATOR_H
#define CGAL_PM_POINT_LOCATOR_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_2/Constrained_triang_traits.h>
#include <CGAL/Nef_2/Object_handle.h>
#include <CGAL/Circulator_project.h>
#include <CGAL/Polygon_2_algorithms.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 17
#include <CGAL/Nef_2/debug.h>
#include <CGAL/Nef_2/geninfo.h>

#ifdef CGAL_USE_LEDA
#include <CGAL/LEDA_basic.h> 
# if __LEDA__ > 410 && __LEDA__ < 441
#  define CGAL_USING_PPL
#  include <CGAL/Nef_2/PM_persistent_PL.h>
# endif
#endif

CGAL_BEGIN_NAMESPACE

enum object_kind { VERTEX, EDGE_CROSSING, EDGE_COLLINEAR };

template < class Node, class Object>
struct Project_halfedge_point {
  typedef Node         argument_type;
  typedef Object       result_type;
  Object& operator()( Node& x) const   { 
    return x.vertex()->point();
  }
  const Object& operator()( const Node& x) const   { 
    return x.vertex()->point(); 
  }
};

/*{\Moptions print_title=yes }*/ 
/*{\Msubst 
PM_decorator_#PMD
Geometry_#GEO
}*/
/*{\Manpage {PM_naive_point_locator}{PMD,GEO}
{Naive point location in plane maps}{PL}}*/
/*{\Mdefinition An instance |\Mvar| of data type |\Mname|
encapsulates naive point location queries within a plane map |P|.  The
two template parameters are specified via concepts. |PM_decorator_|
must be a model of the concept |PMDecorator| as described in the
appendix.  |Geometry_| must be a model of the concept
|AffineGeometryTraits_2| as described in the appendix. For a
specification of plane maps see also the concept of
|PMConstDecorator|.}*/

/*{\Mgeneralization PMD}*/

template <typename PM_decorator_, typename Geometry_>
class PM_naive_point_locator : public PM_decorator_ {
protected:
  typedef PM_decorator_ Base;
  typedef PM_naive_point_locator<PM_decorator_,Geometry_> Self;

  const Geometry_& K;
public:
  /*{\Mtypes 5}*/
  typedef PM_decorator_                 Decorator;
  /*{\Mtypemember equals |PM_decorator_|.}*/
  typedef typename Decorator::Plane_map Plane_map;
  /*{\Mtypemember the plane map type decorated by |Decorator|.}*/
  typedef typename Decorator::Mark      Mark;
  /*{\Mtypemember the attribute of all objects (vertices, edges, 
  faces).}*/

  typedef Geometry_                       Geometry;
  /*{\Mtypemember equals |Geometry_|.}*/
  typedef typename Geometry_::Point_2     Point;
  /*{\Mtypemember the point type of the geometry kernel.\\
  \require |Geometry::Point_2| equals |Plane_map::Point|.}*/
  typedef typename Geometry_::Segment_2   Segment;
  /*{\Mtypemember the segment type of the geometry kernel.}*/
  typedef typename Geometry_::Direction_2 Direction;

  /*{\Mtext Local types are handles, iterators and circulators of the 
  following kind: |Vertex_const_handle|, |Vertex_const_iterator|, 
  |Halfedge_const_handle|, |Halfedge_const_iterator|, |Face_const_handle|, 
  |Face_const_iterator|.}*/

  typedef CGAL::Object_handle Object_handle;
  /*{\Mtypemember a generic handle to an object of the underlying plane
  map. The kind of the object |(vertex, halfedge,face)| can be determined and
  the object assigned by the three functions:\\ 
  |bool assign(Vertex_const_handle& h, Object_handle o)|\\ 
  |bool assign(Halfedge_const_handle& h, Object_handle o)|\\ 
  |bool assign(Face_const_handle& h, Object_handle o)|\\ where each 
  function returns |true| iff the assignment of |o| to |h| was valid.}*/

   typedef typename PM_decorator_::Vertex_handle Vertex_handle;   
   typedef typename PM_decorator_::Halfedge_handle Halfedge_handle;   
   typedef typename PM_decorator_::Face_handle Face_handle;     
   typedef typename PM_decorator_::Vertex_const_handle Vertex_const_handle; 
   typedef typename PM_decorator_::Halfedge_const_handle Halfedge_const_handle; 
   typedef typename PM_decorator_::Face_const_handle Face_const_handle; 
   typedef typename PM_decorator_::Vertex_iterator Vertex_iterator;
   typedef typename PM_decorator_::Halfedge_iterator Halfedge_iterator;
   typedef typename PM_decorator_::Face_iterator Face_iterator;
   typedef typename PM_decorator_::Vertex_const_iterator Vertex_const_iterator;
   typedef typename PM_decorator_::Halfedge_const_iterator Halfedge_const_iterator;
   typedef typename PM_decorator_::Face_const_iterator Face_const_iterator;
   typedef typename PM_decorator_::Halfedge_around_vertex_circulator Halfedge_around_vertex_circulator;
   typedef typename PM_decorator_::Halfedge_around_vertex_const_circulator Halfedge_around_vertex_const_circulator;
   typedef typename PM_decorator_::Halfedge_around_face_circulator Halfedge_around_face_circulator;
   typedef typename PM_decorator_::Halfedge_around_face_const_circulator Halfedge_around_face_const_circulator;

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Base::clear;
  using Base::vertices_begin;
  using Base::vertices_end;
  using Base::halfedges_begin;
  using Base::halfedges_end;
  using Base::faces_begin;
  using Base::faces_end;
  using Base::number_of_vertices;
  using Base::number_of_halfedges;
  using Base::number_of_faces;
#endif

  Halfedge_const_handle out_wedge(Vertex_const_handle v, 
    const Direction& d, bool& collinear) const
  /*{\Xop returns a halfedge |e| bounding a wedge in between two
  neighbored edges in the adjacency list of |v| which contains |d|.
  If |d| extends along a edge then |e| is this edge. If |d| extends
  into the interior of such a wedge then |e| is the first edge hit
  when |d| is rotated clockwise. \precond |v| is not isolated.}*/
  { CGAL_NEF_TRACEN("out_wedge "<<PV(v));
    assert(!is_isolated(v));
    collinear=false;
    Point p = point(v);
    Halfedge_const_handle e_res = first_out_edge(v);
    Direction d_res = direction(e_res);
    Halfedge_around_vertex_const_circulator el(e_res),ee(el);
    CGAL_For_all(el,ee) {
      if ( K.strictly_ordered_ccw(d_res, direction(el), d) )
        e_res = el; d_res = direction(e_res);
    }
    CGAL_NEF_TRACEN("  determined "<<PE(e_res)<<" "<<d_res);
    if ( direction(cyclic_adj_succ(e_res)) == d ) {
      e_res = cyclic_adj_succ(e_res);
      collinear=true;
    }
    CGAL_NEF_TRACEN("  wedge = "<<PE(e_res)<<" "<<collinear);
    return e_res;
  }

  Segment segment(Halfedge_const_handle e) const
  { return K.construct_segment(point(source(e)), point(target(e))); }

  Direction direction(Halfedge_const_handle e) const
  { return K.construct_direction(point(source(e)),point(target(e))); }

  /*{\Mcreation 3}*/

  PM_naive_point_locator() : Base() {}

  /*{\Moptions constref=yes}*/
  PM_naive_point_locator(const Plane_map& P, const Geometry& k = Geometry()) : 
    Base(const_cast<Plane_map&>(P)), K(k) {}
  /*{\Mcreate constructs a point locator working on |P|.}*/
  /*{\Moptions constref=no}*/
  /*{\Moperations 2.5 0.5}*/

  const Mark& mark(Object_handle h) const
  /*{\Mop returns the mark associated to the object |h|.}*/
  { Vertex_const_handle v; 
    Halfedge_const_handle e; 
    Face_const_handle f;
    if ( assign(v,h) ) return mark(v);
    if ( assign(e,h) ) return mark(e);
    if ( assign(f,h) ) return mark(f);
    CGAL_assertion_msg(0,
    "PM_point_locator::mark: Object_handle holds no object.");
  #if !defined(__BORLANDC__)
    return mark(v); // never reached
  #endif
  }

  
  Object_handle locate(const Segment& s) const
  /*{\Mop returns a generic handle |h| to an object (vertex, halfedge,
  face) of the underlying plane map |P| which contains the point |p =
  s.source()| in its relative interior. |s.target()| must be a point
  such that |s| intersects the $1$-skeleton of |P|.}*/
  { CGAL_NEF_TRACEN("locate naivly "<<s);
    if (this->number_of_vertices() == 0) 
      CGAL_assertion_msg(0,"PM_naive_point_locator: plane map is empty.");
    Point p = K.source(s);
    Vertex_const_iterator vit;
    for(vit = this->vertices_begin(); vit != this->vertices_end(); ++vit) {
      if ( p == point(vit) ) return Object_handle(vit);
    }
    Halfedge_const_iterator eit;
    for(eit = this->halfedges_begin(); eit != this->halfedges_end(); ++(++eit)) {
      // we only have to check each second halfedge
      if ( K.contains(segment(eit),p) ) 
        return Object_handle(eit);
    }
    Vertex_const_handle v_res;
    Halfedge_const_handle e_res;
    Segment ss = s; // we shorten the segment iteratively
    Direction dso = K.construct_direction(K.target(s),p), d_res;
    CGAL::Unique_hash_map<Halfedge_const_handle,bool> visited(false);
    for(vit = this->vertices_begin(); vit != this->vertices_end(); ++vit) {
      Point p_res, vp = point(vit);
      if ( K.contains(ss,vp) ) {
        CGAL_NEF_TRACEN(" location via vertex at "<<vp);
        ss = K.construct_segment(p,vp); // we shrink the segment
        if ( is_isolated(vit) ) {
          v_res = vit; e_res = Halfedge_const_handle();
        } else { // not isolated
          bool dummy;
          e_res = out_wedge(vit,dso,dummy);
          Halfedge_around_vertex_const_circulator el(e_res),ee(el);
          CGAL_For_all(el,ee) 
            visited[el] = visited[twin(el)] = true;
          /* e_res is now the counterclockwise maximal halfedge out
             of v just before s */
          if ( K.orientation(p,vp,point(target(e_res))) < 0 ) // right turn
            e_res = previous(e_res);
          // correction to make e_res visible from p
          CGAL_NEF_TRACEN("  determined "<<PE(e_res));
        }
      }
    }

    for (eit = this->halfedges_begin(); eit != this->halfedges_end(); ++eit) {
      if ( visited[eit] ) continue;
      Point se = point(source(eit)),
            te = point(target(eit));
      int o1 = K.orientation(ss,se);
      int o2 = K.orientation(ss,te);
      if ( o1 == -o2 && // internal intersection
           K.orientation(se,te,K.source(ss)) != 
           K.orientation(se,te,K.target(ss)) ) { 
          CGAL_NEF_TRACEN(" location via halfedge "<<segment(eit));
        Point p_res = K.intersection(s,segment(eit));
        ss = K.construct_segment(p,p_res); 
        e_res = (o2 > 0 ? eit : twin(eit));
        // o2>0 => te left of s and se right of s => p left of e
        visited[eit] = visited[twin(eit)] = true;
        CGAL_NEF_TRACEN("  determined "<<PE(e_res)<<" "<<mark(e_res));
        CGAL_NEF_TRACEN("             "<<mark(face(e_res)));
      }
    }

    if ( e_res != Halfedge_const_handle() )
      return Object_handle((Face_const_handle)(face(e_res)));
    else
      return Object_handle((Face_const_handle)(face(v_res)));
  }

  
  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&)|.\\
  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("naive ray_shoot "<<s);
    assert( !K.is_degenerate(s) );
    Point p = K.source(s);
    Segment ss(s);
    Direction d = K.construct_direction(K.source(s),K.target(s));
    Object_handle h = locate(s);
    Vertex_const_handle v; 
    Halfedge_const_handle e; 
    Face_const_handle f;
    if ( assign(v,h) && M(v) ||
         assign(e,h) && M(e) ||
         assign(f,h) && M(f) ) return h;
    h = Object_handle(); 
    CGAL_NEF_TRACEN("not contained");
    for (v = this->vertices_begin(); v != this->vertices_end(); ++v) {
      Point pv = point(v);
      if ( !K.contains(ss,pv) ) continue;
      CGAL_NEF_TRACEN("candidate "<<pv);
      if ( M(v) ) {
        h = Object_handle(v);     // store vertex
        ss = K.construct_segment(p,pv); // shorten
        continue;
      }
      // now we know that v is not marked but on s
      bool collinear;
      Halfedge_const_handle e = out_wedge(v,d,collinear);
      if ( collinear ) { 
        if ( M(e) ) {
          h = Object_handle(e);
          ss = K.construct_segment(p,pv);
        }
        continue;
      }
      if ( M(face(e)) ) {
        h = Object_handle(face(e));
        ss = K.construct_segment(p,pv);
      }
    } // all vertices