arr_landmarks_pl_functions.h

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

// Copyright (c) 2005  Tel-Aviv University (Israel).
// 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/Arrangement_2/include/CGAL/Arr_point_location/Arr_landmarks_pl_functions.h $
// $Id: Arr_landmarks_pl_functions.h 37679 2007-03-29 16:31:55Z efif $
// 
//
// Author(s)     : Idit Haran   <[e-mail]>
#ifndef CGAL_ARR_LANDMARKS_POINT_LOCATION_FUNCTIONS_H
#define CGAL_ARR_LANDMARKS_POINT_LOCATION_FUNCTIONS_H

/*! \file
 * Member-function definitions for the 
 * Arr_landmarks_point_location<Arrangement> class.
 */

//#define CGAL_DEBUG_LM
#ifdef CGAL_DEBUG_LM
  #define CGAL_PRINT_DEBUG(expr)   std::cout << expr << std::endl
  #define CGAL_LM_DEBUG(cmd)   cmd
#else
  #define CGAL_PRINT_DEBUG(expr)
  #define CGAL_LM_DEBUG(cmd) 
#endif

//#define CGAL_PRINT_ERROR(expr)   std::cerr << expr << std::endl
#define CGAL_PRINT_ERROR(expr)   std::cout << expr << std::endl

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Locate the arrangement feature containing the given point.
//
template <class Arrangement_2, class Arr_landmarks_generator>
Object Arr_landmarks_point_location<Arrangement_2,Arr_landmarks_generator>
::locate (const Point_2& p) const
{
  CGAL_PRINT_DEBUG("------ locate point "<< p) ;

  //if this is an empty map - return the unbounded face
  if (p_arr->number_of_vertices() == 0) 
    return (CGAL::make_object (p_arr->unbounded_face()));
  
  Object  lm_location_obj; 
  Point_2 landmark_point = lm_gen->get_closest_landmark (p, 
               lm_location_obj);

  CGAL_PRINT_DEBUG("test ") ;

  //NN_Point_2 nearest_landmark = lm_gen->find_closest_landmark(p);
  //Point_2 landmark_point = nearest_landmarks.get_point();
  //Object  lm_location_obj = nearest_landmarks.get_obj() ;
  CGAL_PRINT_DEBUG("nearest neighbor of point "<< p << " is " << landmark_point);
  
  //walk from the nearest_vertex to the point p, using walk algorithm, 
  //and find the location of p.   
  Object  out_obj; //the output object
  
  //if the landmark s not found in the arangement
  const Vertex_const_handle     *vh;
  const Halfedge_const_handle   *hh;
  const Face_const_handle       *fh;
  m_start_edge = NULL;
  
  if (lm_location_obj.is_empty())
  {
    CGAL_PRINT_ERROR( "lm_location_obj is empty" );
    CGAL_assertion (false);
    return out_obj;
  }
  else if ((vh = object_cast<Vertex_const_handle>(&lm_location_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "lm_location_obj is a vertex: "<< (*vh)->point());
    out_obj = _walk_from_vertex (*vh, p);
  }
  else if ((fh = object_cast<Face_const_handle>(&lm_location_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "lm_location_obj is a face. ");
    out_obj = _walk_from_face (*fh, p, landmark_point);
  }
  else if ((hh = object_cast<Halfedge_const_handle>(&lm_location_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "lm_location_obj is a halfedge: "<< (*hh)->curve());
    out_obj = _walk_from_edge (*hh, p, landmark_point);
  }
  else 
  {
    CGAL_PRINT_ERROR( "unknown object");
    CGAL_assertion (false);
    return out_obj;
  }
  
  CGAL_PRINT_DEBUG( "return from walk" << std::endl);
  
#ifdef CGAL_DEBUG_LM
  if (out_obj.is_empty())
  {
    CGAL_PRINT_ERROR( "object is empty" );
    CGAL_assertion (false);
  }
  else if ((hh = object_cast<Halfedge_const_handle>(&out_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "object is a halfedge: "<< (*hh)->curve());
  }
  else if ((vh = object_cast<Vertex_const_handle>(&out_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "object is a vertex: "<< (*vh)->point());
  }
  else if ((fh = object_cast<Face_const_handle>(&out_obj)) != NULL)
  {
    CGAL_PRINT_DEBUG( "object is a face. ");
  }
#endif
  
  if ((fh = object_cast<Face_const_handle>(&out_obj)) != NULL)
  {
    // If we reached here, we did not locate the query point in any of the
    // holes inside the current face, so we conclude it is contained in this
    // face.
    // However, we first have to check whether the query point coincides with
    // any of the isolated vertices contained inside this face.
    Isolated_vertex_const_iterator   iso_verts_it;
    typename Traits_adaptor_2::Equal_2 equal = traits->equal_2_object();

    for (iso_verts_it = (*fh)->isolated_vertices_begin();
         iso_verts_it != (*fh)->isolated_vertices_end(); ++iso_verts_it)
    {
      if (equal (p, iso_verts_it->point()))
      {
        Vertex_const_handle  vh = iso_verts_it;
        return (CGAL::make_object (vh));
      }
    }    
  }

  return (out_obj);
}

//----------------------------------------------------
// walks from the vertex to the point
// \param nearest_vertex - (input) the closest vertex to point p
// \param p - (input) the point to locate.
//
template <class Arrangement_2, class Arr_landmarks_generator>
Object Arr_landmarks_point_location<Arrangement_2,Arr_landmarks_generator>
::_walk_from_vertex(Vertex_const_handle nearest_vertex,
          const Point_2 & p)   const
{ 
  CGAL_PRINT_DEBUG("inside walk_from_vertex. p= "<< p  << 
        ", nearest_vertex = "<<nearest_vertex->point() );
  
  //inits
  Vertex_const_handle       vh = nearest_vertex;
  
  if (vh->is_isolated())
  {
    Face_const_handle f = vh->face();
    return _walk_from_face(f, p, vh->point());
  }

  //find face
  bool                      new_vertex = false;
  Object                    obj;
  const Face_const_handle  *p_fh;

  do
  {
    //find the edge out_edge which is the best possibly 
    //pointing to the face containing p

    m_flipped_edges.clear();  //clear the curves that were flipped
    
    new_vertex = false;
    obj = _find_face (p, vh, new_vertex);

    if (new_vertex)
    {
      CGAL_PRINT_DEBUG( "NEW vertex 1 " );
      //check if the new vertex is really closer 
      // I removed the check if the vertex is closer since there is no 
      // compare distance 
      //if (traits->compare_distance(p, out_vertex->point(), vh->point())  
      //  != SMALLER) {CGAL_PRINT_DEBUG("Error 2: new vertex"); return; }
      vh = object_cast<Vertex_const_handle> (obj);
    }
    else if (obj.is_empty())
    {
      CGAL_PRINT_ERROR( "object is empty" );
      CGAL_assertion (false);
      return obj;
    }
    else if (object_cast<Halfedge_const_handle>(&obj) != NULL)
    {
      CGAL_PRINT_DEBUG ("_find_face found a halfedge: " << 
		   (object_cast<Halfedge_const_handle>(&obj))->curve());
      return (obj);
    }
    else if (object_cast<Vertex_const_handle>(&obj) != NULL)
    {
      CGAL_PRINT_DEBUG ("_find_face found a vertex: " << 
		   (object_cast<Vertex_const_handle>(&obj))->point());
      return (obj);
    }
    else if ((p_fh = object_cast<Face_const_handle>(&obj)) != NULL)
    {
      CGAL_PRINT_DEBUG ("_find_face found a face.");
      return _walk_from_face (*p_fh, p, vh->point());
    }
    
  } while (new_vertex);  
  
  // We should never reach here:
  CGAL_assertion (false);
  return Object();
}

//----------------------------------------------------
// Return the edge around vh that is before cw to the segment vh->p
// 
//\param p - the input point.
//\param vh - the input vertex
//\param found_vertex_or_edge - output bool, 
//                 if the point was found on a vertex or halfedge
//\param new_vertex - output bool, if a closer vertex to p was found
//
template <class Arrangement_2, class Arr_landmarks_generator>
Object Arr_landmarks_point_location<Arrangement_2,Arr_landmarks_generator>
::_find_face (const Point_2 & p, 
        Vertex_const_handle vh,
        bool & new_vertex) const
{ 
  CGAL_PRINT_DEBUG("inside find_face. p ="<< p <<" , vh = "<<vh->point() ); 
  
  new_vertex = false;
  
  // check if the point equals the vertex. 
  if (traits->equal_2_object()(vh->point(), p))
  {
    return (CGAL::make_object (vh));
  }

  //create a segment vh--p. 
  const Point_2&     v = vh->point();
  X_monotone_curve_2 seg = traits->construct_x_monotone_curve_2_object()(v, p);
  
  //get halfedges around vh
  CGAL_assertion (!vh->is_isolated());
  Halfedge_around_vertex_const_circulator circ = vh->incident_halfedges(); 
  Halfedge_around_vertex_const_circulator circ_done (circ);
  Halfedge_around_vertex_const_circulator prev = circ;
  
  typename Traits_adaptor_2::Compare_xy_2
    compare_xy =  traits->compare_xy_2_object();
  
  typename Traits_adaptor_2::Compare_cw_around_point_2
    compare_cw_around_point = traits->compare_cw_around_point_2_object();
  
  //check if cv_other_point is to the left of v,  to the right, 
  //or if the curve is vertical
  Comparison_result cv_orient = circ->twin()->direction();
  
  //check if p is to the left of v,  to the right, or if the segment is vertical
  Comparison_result seg_orient = compare_xy(v,p);
  
  //save results 
  Comparison_result res1;
  
  CGAL_PRINT_DEBUG("seg_orient ="<< seg_orient ); 
  CGAL_PRINT_DEBUG("cv_orient ="<< cv_orient << " , circ ="<< (*circ).curve());

  /////////////////////////////////// 6.12 - wrapper  
  //TODO: what if both seg and curve are verticals ? @@@@
  //what if one is vertical ?
    
  //curves are to different sides
  if (cv_orient != seg_orient)  
  {
    CGAL_PRINT_DEBUG("seg_orient != cv_orient : "); 
    //find a curve that is on the same side as seg
    do {
      circ++;
      cv_orient = circ->twin()->direction(); 
    } while (seg_orient != cv_orient && circ!=circ_done);
    
    //if exists - go on from next "if" 
    //if not exist - find the curve that is the largest (cw) 
    //in this side, and this is the edge we're looking for
    if (seg_orient != cv_orient) 
    {
      //seg is on one side (right/left) and all curves are on the 
      //other side (left/right)
      //circ == circ_done
      do {
        prev = circ;
        circ++;
        res1 =  compare_cw_around_point 
          (circ->curve(), (circ->direction() == LARGER), 
           prev->curve(), (prev->direction() == LARGER), 
           v);
        CGAL_PRINT_DEBUG ("circ = " << (*circ).curve() << 
                          "  res1= " << res1 ); 
      } while (res1 == LARGER && circ!=circ_done);
      
      CGAL_PRINT_DEBUG ( "new_find_face return face = " << (*prev).curve() );
      return (CGAL::make_object ((*prev).face()));
    }
  }
  
  //both curves are to the same side
  if (seg_orient == cv_orient) 
  {
    CGAL_PRINT_DEBUG("seg_orient == cv_orient : "); 
    res1 = compare_cw_around_point
      (seg, (seg_orient == SMALLER),
       circ->curve(), (circ->direction() == LARGER),
       v);
    
    if (res1 == LARGER) 
    {
      //if the segment is larger than the curve cw, we will go ++ 
      //cw with the circ and find a curve that is larger than seg. 
      //then we will take the curve that was just before that. 
      CGAL_PRINT_DEBUG("res1 == LARGER : "); 
      do {
        prev = circ;
        circ++;
        CGAL_PRINT_DEBUG("circ++ = " << (*circ).curve() ); 
        cv_orient = circ->twin()->direction();
        if (seg_orient == cv_orient) 
        {
          res1 =  compare_cw_around_point