arr_naive_point_location_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_naive_point_location_functions.h $
// $Id: Arr_naive_point_location_functions.h 37680 2007-03-29 16:32:15Z efif $
// 
//
// Author(s)     : Ron Wein   <[e-mail]>
//                 (based on old version by Eyal Flato)
#ifndef CGAL_ARR_NAIVE_POINT_LOCATION_FUNCTIONS_H
#define CGAL_ARR_NAIVE_POINT_LOCATION_FUNCTIONS_H

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

#include <CGAL/Arr_accessor.h>

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Locate the arrangement feature containing the given point.
//
template <class Arrangement>
Object Arr_naive_point_location<Arrangement>::locate (const Point_2& p) const
{
  // Go over the arrangement vertices and check whether one of them equals
  // the query point.
  typename Traits_adaptor_2::Equal_2            equal = 
                                            traits->equal_2_object();
  typename Arrangement::Vertex_const_iterator   vit;
  typename Arrangement::Vertex_const_handle     vh;

  for (vit = p_arr->vertices_begin(); vit != p_arr->vertices_end(); ++vit)
  {
    vh = vit;
    if (equal (p, vh->point()))
      return (CGAL::make_object (vh));
  }

  // Go over arrangement halfedges and check whether one of them contains
  // the query point in its interior.
  typename Traits_adaptor_2::Is_in_x_range_2    is_in_x_range = 
                                            traits->is_in_x_range_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2   compare_y_at_x = 
                                            traits->compare_y_at_x_2_object();
  typename Arrangement::Edge_const_iterator     eit;
  typename Arrangement::Halfedge_const_handle   hh;

  for (eit = p_arr->edges_begin(); eit != p_arr->edges_end(); ++eit)
  {
    hh = eit;

    if (is_in_x_range (hh->curve(), p) &&
        compare_y_at_x (p, hh->curve()) == EQUAL)
    {
      return (CGAL::make_object (hh));
    }
  }

  // Shoot a vertical ray from the query point.
  // The ray shooting returns either a vertex of a halfedge.
  Object   obj = _base_vertical_ray_shoot (p, true);

  const typename Arrangement::Vertex_const_handle    *p_vh;
  const typename Arrangement::Halfedge_const_handle  *p_hh;

  p_hh = object_cast<typename Arrangement::Halfedge_const_handle> (&obj);
  if (p_hh != NULL)
  {
    // Make sure that the edge is directed from right to left, so that p
    // (which lies below it) is contained in its incident face. If necessary,
    // we take the twin halfedge.
    if ((*p_hh)->direction() == SMALLER)
      hh = (*p_hh)->twin();
    else
      hh = *p_hh;

    // Return the incident face.
    return (CGAL::make_object (hh->face()));
  }

  // In case the ray-shooting returned a vertex, we have to locate the first
  // halfedge whose source vertex is v, rotating clockwise around the vertex
  // from "6 o'clock", and to return its incident face. 
  p_vh = object_cast<typename Arrangement::Vertex_const_handle> (&obj);
  CGAL_assertion (p_vh != NULL);

  hh = _first_around_vertex (*p_vh);
  return (CGAL::make_object (hh->face()));
}

//-----------------------------------------------------------------------------
// Locate the arrangement feature which a vertical ray emanating from the
// given point hits (not inculding isolated vertices).
//
template <class Arrangement>
Object Arr_naive_point_location<Arrangement>::_base_vertical_ray_shoot
    (const Point_2& p,
     bool shoot_up) const
{
  typedef Arr_accessor<Arrangement_2>                            Arr_accessor;
  typedef typename Arr_accessor::All_edge_const_iterator  
                                                      All_edge_const_iterator;

  // Set the results for comparison according to the ray direction.
  const Comparison_result point_above_under = (shoot_up ? SMALLER : LARGER);
  const Comparison_result curve_above_under = (shoot_up ? LARGER : SMALLER);

  // Go over all halfedges in the arrangement.
  typename Traits_adaptor_2::Is_vertical_2        is_vertical =
                                       traits->is_vertical_2_object();
  typename Traits_adaptor_2::Compare_y_position_2 compare_y_position =
                                       traits->compare_y_position_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_right_2  compare_y_at_x_right =
                                       traits->compare_y_at_x_right_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_left_2   compare_y_at_x_left =
                                       traits->compare_y_at_x_left_2_object();
  typename Traits_adaptor_2::Compare_xy_2            compare_xy =
                                       traits->compare_xy_2_object();

  const Arr_accessor       arr_access (const_cast<Arrangement_2&>(*p_arr));
  All_edge_const_iterator  eit = arr_access.all_edges_begin();
  Comparison_result        res_s;
  Comparison_result        res;
  Comparison_result        y_res;
  bool                     in_x_range;
  typename Arrangement::Halfedge_const_handle  closest_edge;
  bool                                         found = false;

  while (eit != arr_access.all_edges_end())
  {
    // Determine whether p is in the x-range of the curve and above or below it
    // (according to the direction of the shoot).
    res_s = arr_access.compare_x (p, eit->source());

    if (res_s == EQUAL)
      in_x_range = true;
    else if (res_s == eit->direction())
      in_x_range = false;
    else
      in_x_range = (res_s != arr_access.compare_x (p, eit->target()));

    if (in_x_range)
      res = arr_access.compare_y_at_x (p, eit);

    if (in_x_range && res == point_above_under)
    {
      if (!found)
      {
        // If no other x-monotone curve containing p in its x-range has been
        // found yet, take the current one as the vertically closest to p.
        closest_edge = eit;
        found = true;
      }
      else
      {
        // Compare with the vertically closest curve so far and detemine the
        // curve closest to p. We first check the case that the two curves
        // have a common endpoint (note that the two curves do not intersect
        // in their interiors). Observe that if such a common vertex exists,
        // it is certainly not a vertex at infinity, therefore it is
        // associated with a valid point.
        if ((closest_edge->source() == eit->source() &&
             closest_edge->direction() == eit->direction()) ||
            (closest_edge->source() == eit->target() &&
             closest_edge->direction() != eit->direction()))
        {
          CGAL_assertion (! closest_edge->source()->is_at_infinity());

          if (closest_edge->direction() == SMALLER)
          {
            // Both curves extend to the right from a common point.
            y_res = compare_y_at_x_right (closest_edge->curve(),
                                          eit->curve(), 
                                          closest_edge->source()->point());
          }
          else
          {
            // Both curves extend to the left from a common point.
            y_res = compare_y_at_x_left (closest_edge->curve(),
                                         eit->curve(), 
                                         closest_edge->source()->point());
          }
        }
        else if ((closest_edge->target() == eit->source() &&
                  closest_edge->direction() != eit->direction()) ||
                 (closest_edge->target() == eit->target() &&
                  closest_edge->direction() == eit->direction()))
        {
          CGAL_assertion (! closest_edge->target()->is_at_infinity());

          if (closest_edge->direction() == SMALLER)
          {
            // Both curves extend to the left from a common point.
            y_res = compare_y_at_x_left (closest_edge->curve(),
                                         eit->curve(), 
                                         closest_edge->target()->point());
          }
          else
          {
            // Both curves extend to the right from a common point.
            y_res = compare_y_at_x_right (closest_edge->curve(),
                                          eit->curve(), 
                                          closest_edge->target()->point());
          }
        }
        else
        {
          // In case the two curves do not have a common endpoint, but overlap
          // in their x-range (both contain p), just compare their positions.
          // Note that in this case one of the edges may be fictitious, so we
          // preform the comparsion symbolically in this case.
          if (closest_edge->is_fictitious())
            y_res = curve_above_under;
          else if (eit->is_fictitious())
            y_res = point_above_under;
          else
            y_res = compare_y_position (closest_edge->curve(),
                                        eit->curve());
        }