sm_point_locator.h

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

// 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.
//
// $Source: /CVSROOT/CGAL/Packages/Nef_S2/include/CGAL/Nef_S2/SM_point_locator.h,v $
// $Revision: 1.15.2.1 $ $Date: 2004/12/08 20:10:13 $
// $Name:  $
//
// 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(point(source(e)), point(target(e)), circle(e)); }

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

  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 = point(v);
    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) << circle(el));
      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)) << circle(cyclic_adj_succ(el)));
	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) << circle(e_res));
    /*
    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 Base::mark(v);
    if ( CGAL::assign(e,h) ) return Base::mark(e);
    if ( CGAL::assign(l,h) ) return Base::mark(l);
    CGAL_assertion_msg(CGAL::assign(f,h),
	 "PM_point_locator::mark: Object_handle holds no object.");
    CGAL::assign(f,h);
    return Base::mark(f);
  }

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

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

    SHalfedge_iterator e;
    CGAL_forall_sedges(e,*this) {
      if ( segment(e).has_on(p) ) {
	CGAL_NEF_TRACEN( "  on segment " << segment(e));
	return Object_handle(e);
      }
    }

    if ( this->has_shalfloop() && circle(this->shalfloop()).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(circle(this->shalfloop()),p); // orthogonal through p
      s = Sphere_segment(p,intersection(c,circle(this->shalfloop())));
      l_res = circle(this->shalfloop()).has_on_positive_side(p) ? 
	this->shalfloop() : twin(this->shalfloop());
      solution = is_loop_;
      CGAL_NEF_TRACEN("has loop, initial ray "<<s);
      CGAL_NEF_TRACEN(circle(l_res));
    } else { // has vertices !
      CGAL_assertion( this->number_of_svertices()!=0 );
      SVertex_iterator vi = this->svertices_begin();
      if( p == point(vi).antipode()) {
	++vi;
	CGAL_assertion( vi != this->svertices_end());
      }
      CGAL_NEF_TRACEN("initial segment: "<<p<<","<<point(vi));
      CGAL_assertion( p != point(vi).antipode());
      s = Sphere_segment( p, point(vi));
      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 = point(v);
      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[twin(el)] = true;
          /* e_res is now the counterclockwise maximal halfedge out
             of v just before s */