arr_walk_along_line_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_walk_along_line_pl_functions.h $
// $Id: Arr_walk_along_line_pl_functions.h 39244 2007-06-27 09:44:50Z ophirset $
// 
//
// Author(s)     : Ron Wein   <[e-mail]>
//                 (based on old version by Oren Nechushtan
//                                      and Iddo Hanniel)
#ifndef CGAL_ARR_WALK_ALONG_LINE_POINT_LOCATION_FUNCTIONS_H
#define CGAL_ARR_WALK_ALONG_LINE_POINT_LOCATION_FUNCTIONS_H

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

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Locate the arrangement feature containing the given point.
//
template <class Arrangement>
Object Arr_walk_along_line_point_location<Arrangement>::locate
    (const Point_2& p) const
{
  // Start from the fictitious face, and an invalid halfedge representing
  // the closest edge to p from above it so far.
  Arrangement&                        arr = const_cast<Arrangement&>(*p_arr);
  const Arr_accessor<Arrangement>     arr_access (arr);
  typename Traits_adaptor_2::Equal_2  equal = traits->equal_2_object();
  Hole_const_iterator    holes_it;
  Face_const_handle      face = arr_access.fictitious_face();
  Halfedge_const_handle  closest_he;
  bool                   is_in_face;
  bool                   is_on_edge;
  bool                   closest_to_target;
  bool                   found_containing_hole;

  do
  {
    // Go over the holes in the current face.
    found_containing_hole = false;
    for (holes_it = face->holes_begin();
         !found_containing_hole && holes_it != face->holes_end();
         ++holes_it)
    {
      // Check if the point is inside the current hole.
      is_in_face = _is_in_connected_component (p, *holes_it,
                                               true,        // Shoot up.
                                               true,        // Including p.
                                               closest_he,
                                               is_on_edge,
                                               closest_to_target);

      // Check if the query point is located on the returned edge.
      if (is_on_edge)
      {
        // Check if the point is located on one of the edge endpoints.
        if (! closest_he->source()->is_at_infinity() &&
            equal (p, closest_he->source()->point()))
        {
          // The query point is located on the source vertex:
          return (CGAL::make_object (closest_he->source()));
        }
        else if (! closest_he->target()->is_at_infinity() &&
                 equal (p, closest_he->target()->point()))
        {
          // The query point is located on the target vertex:
          return (CGAL::make_object (closest_he->target()));
        }

        // The query point is located in the edge interior:
        return (CGAL::make_object (closest_he));
      }

      // Check if the point is contained in the interior of the current hole.
      if (is_in_face)
      {
        if (closest_to_target)
        {
          // Deal with the following scenario, where the definition of the
          // closest halfedge is not unique (all halfedges around x are
          // closest to p):
          //
          //          +--+--+
          //           \ | /
          //            \|/
          //     +-------x------+
          //     |              |
          //     |      (.)p    |
          //     |              |
          //     +--------------+
          //
          // In this case, we find the first halfegde whose target is x
          // in a clockwise direction from "6 o'clock" around x and take
          // its incident face.
          closest_he = _first_around_vertex (closest_he->target(),
                                             true);      // Shoot up.
        }
        
        // Move inside the faces that constitute the hole, the first one
        // being incident face of the twin of closest halfedge found so far.
        CGAL_assertion (face != closest_he->twin()->face());

        face = closest_he->twin()->face();

        // Perform a vertical walk along the faces of the hole until locating
        // a face that contains the qeury point.
        do
        {
          CGAL_assertion_code (
            Halfedge_const_handle  old_closest_he = closest_he;
          );

          is_in_face = _is_in_connected_component (p, face->outer_ccb(),
                                                   true,    // Shoot up.
                                                   true,    // Including p.
                                                   closest_he,
                                                   is_on_edge,
                                                   closest_to_target);

          // Check if the query point was located on an edge.
          if (is_on_edge)
          {
            // Check if the point is located on one of the edge endpoints.
            if (! closest_he->source()->is_at_infinity() &&
                equal (p, closest_he->source()->point()))
            {
              // The query point is located on the source vertex:
              return (CGAL::make_object (closest_he->source()));
            }
            else if (! closest_he->target()->is_at_infinity() &&
                     equal (p, closest_he->target()->point()))
            {
              // The query point is located on the target vertex:
              return (CGAL::make_object (closest_he->target()));
            }

            // The query point is located in the edge iterior:
            return (CGAL::make_object (closest_he));
          }

          // If the point is not contained in the face, move to the neighboring
          // face from below, using the closest halfedge located so far.
          if (! is_in_face)
          {
            if (closest_to_target)
            {
              // The query point lies below the target vertex of the closest
              // halfedge: In this case we have to locate the first halfedge
              // we encounter when going around this target vertex from
              // "6 o'clock" (see above).
              closest_he = _first_around_vertex (closest_he->target(),
                                                 true);      // Shoot up.
            }

            CGAL_assertion (old_closest_he != closest_he);
            face = closest_he->twin()->face();
          }

        } while (! is_in_face);

        // We have located a face in the hole that contains the query point.
        // This will break the internal loop on holes, and we shall proceed
        // for another iteration of the external loop, trying to locate p in
        // one of the hole of this new face.
        found_containing_hole = true;
      }
    } // End loop on the current face's holes.

  } while (found_containing_hole);

  // 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;

  for (iso_verts_it = face->isolated_vertices_begin();
       iso_verts_it != face->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));
    }
  }

  // The query point is contained in the face interior:
  return (CGAL::make_object (face));
}

//-----------------------------------------------------------------------------
// Locate the arrangement feature which a vertical ray emanating from the
// given point hits.
//
template <class Arrangement>
Object Arr_walk_along_line_point_location<Arrangement>::
_vertical_ray_shoot (const Point_2& p,
                     bool shoot_up) const
{
  // Start from the fictitious face, and an invalid halfedge representing
  // the closest edge to p from above it so far.
  Arrangement&                        arr = const_cast<Arrangement&>(*p_arr);
  const Arr_accessor<Arrangement>     arr_access (arr);
  typename Traits_adaptor_2::Is_vertical_2        is_vertical =
                                            traits->is_vertical_2_object();

  Hole_const_iterator    holes_it;
  Face_const_handle      face = arr_access.fictitious_face();
  Halfedge_const_handle  closest_he;
  bool                   is_in_face;
  bool                   is_on_edge;
  bool                   closest_to_target;
  bool                   found_containing_hole;

  do
  {
    // Go over the holes in the current face.
    found_containing_hole = false;
    for (holes_it = face->holes_begin();
         !found_containing_hole && holes_it != face->holes_end();
         ++holes_it)
    {
      // Check if the point is inside the current hole.
      is_in_face = _is_in_connected_component (p, *holes_it,
                                               shoot_up,
                                               false,     // Not including p.
                                               closest_he,
                                               is_on_edge,
                                               closest_to_target);

      // Check if the query point is located on the returned edge.
      // This can happen only if the edge is vertical.
      if (is_on_edge)
      {
        CGAL_assertion (is_vertical (closest_he->curve()));
        return (CGAL::make_object (closest_he));
      }

      // Check if the point is contained in the interior of the current hole.
      if (is_in_face)
      {
        if (closest_to_target)
        {
          // The query point lies below the target vertex of the closest
          // halfedge: In this case we have to locate the first halfedge
          // we encounter when going around this target vertex from
          // "6 o'clock" (when shooting up) or from "12 o'clock" (when
          // shooting down).
          closest_he = _first_around_vertex (closest_he->target(),
                                             shoot_up);
        }

        // Move inside the faces that constitute the hole, the first one
        // being incident face of the twin of closest halfedge found so far.
        CGAL_assertion (face != closest_he->twin()->face());

        face = closest_he->twin()->face();

        // Perform a vertical walk along the faces of the hole until locating
        // a face that contains the qeury point.
        do
        {
          CGAL_assertion_code (
            Halfedge_const_handle  old_closest_he = closest_he;
          );

          is_in_face = _is_in_connected_component (p, face->outer_ccb(),
                                                   shoot_up,
                                                   false,   // Not including p.
                                                   closest_he,
                                                   is_on_edge,
                                                   closest_to_target);

          // Check if the query point was located on an edge.
          // This can happen only if the edge is vertical.
          if (is_on_edge)
          {
            CGAL_assertion (is_vertical (closest_he->curve()));
            return (CGAL::make_object (closest_he));
          }

          // If the point is not contained in the face, move to the neighboring
          // face from below (or above, if we shoot downward), using the
          // closest halfedge located so far.
          if (! is_in_face)
          {
            if (closest_to_target)