sm_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_S2/include/CGAL/Nef_S2/SM_point_locator.h $
// $Id: SM_point_locator.h 38154 2007-04-16 16:56:26Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>
#ifndef CGAL_SM_POINT_LOCATOR_H
#define CGAL_SM_POINT_LOCATOR_H

#include <vector>
#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_2/geninfo.h>
#include <CGAL/Nef_2/Object_handle.h>
#include <CGAL/Nef_S2/SM_decorator_traits.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 47
#include <CGAL/Nef_2/debug.h>


CGAL_BEGIN_NAMESPACE

/*{\Moptions print_title=yes }*/ 

/*{\Manpage {SM_point_locator}{Decorator}
{Naive point location in plane maps}{PL}}*/
/*{\Mdefinition An instance |\Mvar| of data type |\Mname|
encapsulates naive point location queries within a sphere map |M|.  The
two template parameters are specified via concepts. |SM_decorator_|
must be a model of the concept |SMDecorator| 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
|SMConstDecorator|.}*/

/*{\Mgeneralization Decorator}*/

template <class SM_decorator>
class SM_point_locator : public SM_decorator {
protected:
  typedef SM_decorator                                  Base;
  typedef SM_point_locator<SM_decorator>                Self;
  typedef typename SM_decorator::Sphere_map             Sphere_map;

public:
  /*{\Mtypes 5}*/

  typedef typename SM_decorator::Decorator_traits  Decorator_traits;

  typedef typename Base::Mark      Mark;
  /*{\Mtypemember the attribute of all objects (vertices, edges, loops,
  faces).}*/

  typedef typename SM_decorator::Sphere_kernel Sphere_kernel;
  /*{\Mtypemember the sphere kernel.}*/
  typedef typename Sphere_kernel::Sphere_point Sphere_point;
  /*{\Mtypemember points.}*/
  typedef typename Sphere_kernel::Sphere_segment Sphere_segment;
  /*{\Mtypemember segments.}*/
  typedef typename Sphere_kernel::Sphere_circle Sphere_circle;
  /*{\Mtypemember circles.}*/
  typedef typename Sphere_kernel::Sphere_direction Sphere_direction;
  /*{\Mtypemember directions.}*/

  /*{\Mtext Local types are handles, iterators and circulators of the 
  following kind: |SVertex_const_handle|, |SVertex_const_iterator|, 
  |SHalfedge_const_handle|, |SHalfedge_const_iterator|, 
  |SHalfloop_const_handle|, |SHalfloop_const_iterator|, 
  |SFace_const_handle|, |SFace_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(SVertex_const_handle& h, Object_handle o)|\\ 
  |bool assign(SHalfedge_const_handle& h, Object_handle o)|\\ 
  |bool assign(SFace_const_handle& h, Object_handle o)|\\ where each 
  function returns |true| iff the assignment of |o| to |h| was valid.}*/

  typedef typename Decorator_traits::SVertex_handle       SVertex_handle;   
  typedef typename Decorator_traits::SHalfedge_handle     SHalfedge_handle;   
  typedef typename Decorator_traits::SHalfloop_handle     SHalfloop_handle;   
  typedef typename Decorator_traits::SFace_handle         SFace_handle;     

  typedef typename Decorator_traits::SVertex_iterator     SVertex_iterator;
  typedef typename Decorator_traits::SHalfedge_iterator   SHalfedge_iterator;
  typedef typename Decorator_traits::SHalfloop_iterator   SHalfloop_iterator;
  typedef typename Decorator_traits::SFace_iterator       SFace_iterator;

  typedef typename Decorator_traits::SHalfedge_around_svertex_circulator
                                     SHalfedge_around_svertex_circulator;
  typedef typename Decorator_traits::SHalfedge_around_sface_circulator
                                     SHalfedge_around_sface_circulator;

  Sphere_segment segment(SHalfedge_handle e) const
  { return Sphere_segment(e->source()->point(), e->twin()->source()->point(), e->circle()); }

  Sphere_direction direction(SHalfedge_handle e) const
  { return Sphere_direction(e->circle()); }

  SHalfedge_handle out_wedge(SVertex_handle v, const Sphere_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 "<<PH(v));
    CGAL_assertion(!is_isolated(v));
    collinear=false;
    Sphere_point p = v->point();
    SHalfedge_handle e_res = first_out_edge(v);
    Sphere_direction d_res = direction(e_res);
    SHalfedge_around_svertex_circulator el(e_res),ee(el);
    if(direction(el) == d) {
      collinear = true;
      CGAL_NEF_TRACEN("  determined "<<PH(el) << el->circle());
      return el;
    }
    CGAL_For_all(el,ee) {
      if(direction(cyclic_adj_succ(el)) == d) {
	collinear = true;
	CGAL_NEF_TRACEN("  equal "<<PH(cyclic_adj_succ(el)) << cyclic_adj_succ(el)->circle());
	return cyclic_adj_succ(el);
      }
      else {
	CGAL_NEF_TRACEN("strictly_ordered_ccw " << direction(el) << " ? " << d << " ? " << direction(cyclic_adj_succ(el)));
	//	if ( strictly_ordered_ccw_at(p,d_res, direction(el), d) ) {
	if ( strictly_ordered_ccw_at(p,direction(el), d, direction(cyclic_adj_succ(el))) ) {
	  CGAL_NEF_TRACEN("strictly_ordered_ccw " << direction(el) << " - " << d << " - " << direction(cyclic_adj_succ(el)));
	  e_res = el; d_res = direction(e_res); break;
	}
      }
    }
    CGAL_NEF_TRACEN("  finally determined "<<PH(e_res) << e_res->circle());
    /*
    Sphere_direction d2 = direction(cyclic_adj_succ(e_res));
    d2 = normalized(d2);
    CGAL_NEF_TRACEN(d2 << " =?= " << d);
    if (d2 == d ) {
      e_res = cyclic_adj_succ(e_res);
      collinear=true;
    }
    CGAL_NEF_TRACEN("  wedge = "<<PH(e_res)<<" "<<collinear);
    */
    return e_res;
  }

  /*{\Mcreation 3}*/

  SM_point_locator() : Base() {}

  /*{\Moptions constref=yes}*/
  SM_point_locator(Sphere_map* cp) : Base(cp) {}
  /*{\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|.}*/
  { SVertex_handle v; 
    SHalfedge_handle e; 
    SHalfloop_handle l;
    SFace_handle f;
    if ( CGAL::assign(v,h) ) return v->mark();
    if ( CGAL::assign(e,h) ) return e->mark();
    if ( CGAL::assign(l,h) ) return l->mark();
    CGAL_assertion_msg(CGAL::assign(f,h),
	 "PM_point_locator::mark: Object_handle holds no object.");
    CGAL::assign(f,h);
    return f->mark();
  }

  enum SOLUTION { is_vertex_, is_edge_, is_loop_ };
  // enumeration for internal use

  Object_handle locate(const Sphere_point& p)
  /*{\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 "<<p);
    SVertex_iterator v;
    CGAL_forall_svertices(v,*this) {
      if ( p == v->point() ) {
	CGAL_NEF_TRACEN( "  on point"); 
	return Object_handle(v);
      }
    }

    SHalfedge_iterator e;
    CGAL_forall_sedges(e,*this) {
      if ( segment(e).has_on(p) || 
	   (e->source() == e->twin()->source() && e->circle().has_on(p))) {
	CGAL_NEF_TRACEN( "  on segment " << segment(e));
	return Object_handle(e);
      }
    }

    if ( this->has_shalfloop() && this->shalfloop()->circle().has_on(p)) {
      CGAL_NEF_TRACEN( "  on loop");
      return Object_handle(SHalfloop_handle(this->shalfloop()));
    }

    // now in face:

    if(this->number_of_sfaces() == 1) {
      CGAL_NEF_TRACEN("  on unique face");
      SFace_handle f = this->sfaces_begin();
      return Object_handle(f);
    }

    SVertex_handle v_res;
    SHalfedge_handle e_res;
    SHalfloop_handle l_res(this->shalfloop());
    SOLUTION solution;

    CGAL_NEF_TRACEN("  on face...");
    Sphere_segment s; // we shorten the segment iteratively
    if ( this->has_shalfloop() ) {
      Sphere_circle c(this->shalfloop()->circle(),p); // orthogonal through p
      s = Sphere_segment(p,intersection(c,this->shalfloop()->circle()));
      l_res = this->shalfloop()->circle().has_on_positive_side(p) ? 
	this->shalfloop() : this->shalfloop()->twin();
      solution = is_loop_;
      CGAL_NEF_TRACEN("has loop, initial ray "<<s);
      CGAL_NEF_TRACEN(l_res->circle());
    } else { // has vertices !
      CGAL_assertion( this->number_of_svertices()!=0 );
      SVertex_iterator vi = this->svertices_begin();
      if( p == vi->point().antipode()) {
	++vi;
	CGAL_assertion( vi != this->svertices_end());
      }
      CGAL_NEF_TRACEN("initial segment: "<<p<<","<<vi->point());
      CGAL_assertion( p != vi->point().antipode());
      s = Sphere_segment( p, vi->point());
      v_res = vi;
      solution = is_vertex_;
      CGAL_NEF_TRACEN("has vertices, initial ray "<<s);
    }

    // s now initialized
    
    Sphere_direction dso(s.sphere_circle().opposite());
    Unique_hash_map<SHalfedge_handle,bool> visited(false);
    CGAL_forall_svertices(v,*this) {
      Sphere_point vp = v->point();
      if ( s.has_on(vp) ) {
        CGAL_NEF_TRACEN(" location via vertex at "<<vp);
        s = Sphere_segment(p,vp,s.sphere_circle()); // we shrink the segment
        if ( is_isolated(v) ) {
          CGAL_NEF_TRACEN("is_vertex_");
          v_res = v; solution = is_vertex_;
        } else { // not isolated
          bool dummy;
          e_res = out_wedge(v,dso,dummy);
          SHalfedge_around_svertex_circulator el(e_res),ee(el);
          CGAL_For_all(el,ee) 
            visited[el] = visited[el->twin()] = true;
          /* e_res is now the counterclockwise maximal halfedge out
             of v just before s */
          if ( e_res->circle().has_on_negative_side(p) )
            e_res = e_res->sprev();
            // correction to make e_res visible from p
	  solution = is_edge_;
          CGAL_NEF_TRACEN("  determined "<<PH(e_res));
        }
      }
    }

    CGAL_forall_sedges(e,*this) {
      if ( visited[e] ) continue;
      Sphere_segment se = segment(e);
      Sphere_point p_res;
      if ( do_intersect_internally(se,s,p_res) ) {
          CGAL_NEF_TRACEN(" location via halfedge "<<se);
        s = Sphere_segment(p,p_res,s.sphere_circle()); 
        e_res = ( e->circle().has_on_positive_side(p) ? e : e->twin() );
        visited[e] = visited[e->twin()] = true;
	solution = is_edge_;
        CGAL_NEF_TRACEN("  determined "<<PH(e_res)<<" "<< e_res->incident_sface()->mark());
      }
    }

    switch ( solution ) {
      case is_edge_: 
        return Object_handle(SFace_handle(e_res->incident_sface()));
      case is_loop_:
        return Object_handle(SFace_handle(l_res->incident_sface()));
      case is_vertex_:
        return Object_handle(SFace_handle(v_res->incident_sface()));
      default: CGAL_assertion_msg(0,"missing solution.");
    }
    return Object_handle(); // never reached!
  }

  template <typename Object_predicate>
  Object_handle ray_shoot(const Sphere_point& p, 
			  const Sphere_direction& d,
			  const Object_predicate& M) const
  /*{\Mop returns an |Object_handle o| which can be converted to a
  |SVertex_handle|, |SHalfedge_handle|, |SFace_handle|
  |h| as described above.  The object predicate |M| has to have
  function operators \\ |bool operator() (const
  SVertex_/SHalfedge_/SHalfloop_/SFace_handle&)|.\\ The object
  returned is intersected by |d.circle()|, has minimal distance to
  |p|, 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 |M| with |M(h)|.}*/
  {