arrangement_zone_2_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/Arrangement_2/Arrangement_zone_2_functions.h $
// $Id: Arrangement_zone_2_functions.h 37682 2007-03-29 16:33:01Z efif $
// 
//
// Author(s)     : Ron Wein          <[e-mail]>
//                 Efi Fogel         <[e-mail]>
//                 (based on old version by Eyal Flato)

#ifndef CGAL_ARRANGEMENT_ZONE_2_FUNCTIONS_H
#define CGAL_ARRANGEMENT_ZONE_2_FUNCTIONS_H

/*! \file
 * Member-function definitions for the Arrangement_zone_2 class.
 */

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Compute the zone of the given curve and issue the apporpriate
// notifications for the visitor.
//
template<class Arrangement, class ZoneVisitor>
void Arrangement_zone_2<Arrangement,ZoneVisitor>::compute_zone ()
{
  // Initialize flags and set all handles to be invalid.
  bool    done = false;

  found_intersect = false;
  found_overlap = false;
  found_iso_vert = false;

  left_v = invalid_v;
  left_he = invalid_he;
  right_v = invalid_v;
  right_he = invalid_he;

  // Locate the arrangement feature containing the left endpoint of the
  // curve (currently obj stores the object containing it).
  const typename Arrangement_2::Vertex_const_handle    *vh;
  const typename Arrangement_2::Halfedge_const_handle  *hh;
  const typename Arrangement_2::Face_const_handle      *fh;

  if ((vh = object_cast<typename Arrangement_2::Vertex_const_handle>(&obj))
      != NULL)
  {
    if (has_left_pt)
    {
      // The left endpoint coincides with an existing vertex:
      left_v = arr.non_const_handle (*vh);
    }
    else
    {
      // Assign the vertex at infinity that represents the left end of cv.
      left_v = arr.non_const_handle (*vh);
      CGAL_assertion (left_v->is_at_infinity());

      // In this case cv overlaps the curve associated with the unbounded
      // curve emanating from vh. Locate the halfedge associated with
      // this curve and assign it as intersect_he.
      typename Arrangement_2::Halfedge_around_vertex_circulator he_first;
      typename Arrangement_2::Halfedge_around_vertex_circulator he_curr;

      he_curr = he_first = left_v->incident_halfedges();
      while (he_curr->is_fictitious())
      {
        ++he_curr;
        CGAL_assertion (he_curr != he_first);   // Guard for infinitive loops.
      }
      intersect_he = he_curr;

      // Compute the overlapping subcurve.
      obj = _compute_next_intersection (intersect_he, false);
        
      overlap_cv = object_cast<X_monotone_curve_2> (obj);
        
      // Remove the overlap from the map.
      _remove_next_intersection (intersect_he);
        
      // Compute the overlap zone.
      done = _zone_in_overlap ();
    }
  }
  else if ((hh =
	    object_cast<typename Arrangement_2::Halfedge_const_handle>(&obj))
	   != NULL)
  {
    if (has_left_pt)
    {
      // Obtain the right halfedge from the halfedge-pair containing left_pt
      // in their interior.
      left_he =
        _direct_intersecting_edge_to_right (cv, left_pt,
                                            arr.non_const_handle (*hh));

      // Handle overlaps.
      if (found_overlap)
      {
        // In this case cv overlaps the curve associated with intersect_he.
        // Compute the overlapping subcurve.
        obj = _compute_next_intersection (intersect_he, false);
        
        overlap_cv = object_cast<X_monotone_curve_2> (obj);
        
        // Remove the overlap from the map.
        _remove_next_intersection (intersect_he);
        
        // Compute the overlap zone.
        done = _zone_in_overlap ();
      }
    }
    else
    {
      // The left end of the curve lies on a fictitious halfedge hh, so the
      // left portion of the curve lies in the interior of hh's incident face.
      typename Arrangement_2::Face_const_handle    fh = (*hh)->face();

      CGAL_assertion (fh->is_unbounded());

      left_he = arr.non_const_handle (*hh);
      done = _zone_in_face (arr.non_const_handle (fh),
                            true);      // left_pt is on the face boundary.

      // In case we have just discovered an overlap, compute the overlapping
      // zone as well.
      if (! done && found_overlap)
      {
        done = _zone_in_overlap ();
      }
    }
  }
  else
  {
    // The left endpoint lies inside a face.
    fh = object_cast<typename Arrangement_2::Face_const_handle>(&obj);

    CGAL_assertion_msg(fh != NULL,
		       "Invalid object returned by the point-location query.");

    CGAL_assertion (has_left_pt);

    // Compute the zone of the curve at the interior of the face.
    done = _zone_in_face (arr.non_const_handle(*fh),
                          false);      // left_pt is not on the face boundary.

    // In case we have just discovered an overlap, compute the overlapping
    // zone as well.
    if (! done && found_overlap)
    {
      done = _zone_in_overlap ();
    }
  }

  // Compute the zone of the curve (or what is remaining of it) in the
  // arrangement, starting from the current position we have computed.
  while (! done)
  {
    // Check if we know the face the curve is going to penetrate now.
    if (left_he == invalid_he)
    {
      if (left_v != invalid_v)
      {
        // We know the vertex that coincides with the left endpoint of cv.
        if (! left_v->is_isolated())
        {
          // Locate the curve around the left_v vertex - that is, find a
          // halfedge left_he such that cv should be placed between left_he
          // and its current successor around the vertex, going in a clockwise
          // order.
          found_overlap = _find_prev_around_vertex (left_v,
                                                    left_he);
        }
        else
        {
          // left_v is an isolated vertex.
          found_iso_vert = true;
        }
      }
      else
      {
        CGAL_assertion (right_he != invalid_he);

        // In this case right_he is the halfedge that the left portion of cv
        // intersected, and we obtain left_he by comparing the remaining
        // portion of cv with the curve associated with this edge.
        left_he = _direct_intersecting_edge_to_right (cv, left_pt,
                                                      right_he);
      }

      if (found_overlap)
      {
        // In this case cv overlaps the curve associated with intersect_he.
        // Compute the overlapping subcurve to the right of curr_v.
        obj = _compute_next_intersection (intersect_he, false);

        overlap_cv = object_cast<X_monotone_curve_2> (obj);

	// Remove the overlap from the map.
	_remove_next_intersection (intersect_he);

	// Compute the overlap zone and continue to the end of the loop.
        done = _zone_in_overlap ();
	continue;
      }
    }

    if (left_v == invalid_v || ! left_v->is_isolated())
    {
      // At this point we can compute the zone of cv starting from the left_he
      // inside its incident face.
      done = _zone_in_face (left_he->face(),
                            true);      // left_pt is on the face boundary.
    }
    else
    {
      // Compute the zone of cv starting from the face that contains the
      // isolated vertex left_v.
      done = _zone_in_face (left_v->face(),
                            false);     // left_pt is not on the face boundary.
    }

    // In case we have just discovered an overlap, compute the overlapping
    // zone as well.
    if (! done && found_overlap)
    {
      done = _zone_in_overlap();
    }
  }

  // Clear the intersections map.
  inter_map.clear();

  return;
}

//-----------------------------------------------------------------------------
// Find a face containing the query curve cv around the given vertex.
// In case an overlap occurs, sets intersect_he to be the overlapping edge.
//
template<class Arrangement, class ZoneVisitor>
bool Arrangement_zone_2<Arrangement,ZoneVisitor>::_find_prev_around_vertex
    (Vertex_handle v,
     Halfedge_handle& he)
{
  // Go over the incident halfedges of v, going in a clockwise order.
  typename Arrangement_2::Halfedge_around_vertex_circulator he_first;
  typename Arrangement_2::Halfedge_around_vertex_circulator he_curr;
  bool                                                      cv_equals_curr;
  typename Arrangement_2::Halfedge_around_vertex_circulator he_next;
  bool                                                      cv_equals_next;
  bool                                                      is_between;

  he_first = v->incident_halfedges();
  he_curr = he_first;
  he_next = he_curr;
  ++he_next;

  if (he_curr == he_next)
  {
    // In case there is just a single incident halfedge around v,
    // we should insert cv right after this halfedge.
    he = he_curr;

    // Note that cv extends to the right of v. In case the single
    // halfedge also extends to the right of v (its source is to
    // the right), check if an overlap occurs.
    if (he->direction() == LARGER &&
        (traits->compare_y_at_x_right_2_object() (he->curve(), cv,
                                                  v->point()) == EQUAL))
    {
      // Mark that an overlap occurs:
      intersect_he = he_curr;
      return (true);
    }

    // We have no overlap:
    return (false);
  }

  // Find the face containing cv around the vertex.
  typename Traits_adaptor_2::Is_between_cw_2  is_between_cw =
                                             traits->is_between_cw_2_object();

  do
  {
    // Check if it is possible to insert cv in between the current curve
    // and the next curve, going in a clockwise direction around v.
    is_between = is_between_cw (cv, true,
                                he_curr->curve(), 
                                (he_curr->direction() == LARGER),  
                                he_next->curve(),
                                (he_next->direction() == LARGER),
                                v->point(),
                                cv_equals_curr, cv_equals_next);

    // Check the case of overlaps:
    if (cv_equals_curr)
    {
      // cv overlaps with the curve of he_curr:
      intersect_he = he_curr;
      return (true);
    }
    else if (cv_equals_next)
    {
      // cv overlaps with the curve of he_next:
      intersect_he = he_next;
      return (true);
    }

    if (is_between)
    {
      // We can conclude that cv should be placed between he_curr and
      // he_next (in a clockwise order), and no overlap occurs.
      he = he_curr;
      return (false);
    }

    // Proceed to the next halfedges around the vertex.
    ++he_curr;
    ++he_next;

  } while (he_curr != he_first);

  // We should never reach here:
  CGAL_assertion (false);
  return (false);
}

//-----------------------------------------------------------------------------
// Direct the halfedge for the location of the given subcurve around a split
// point that occurs in the interior of a given edge, when the subcurve lies
// to the right of the split point.
//
template<class Arrangement, class ZoneVisitor>
typename Arrangement_zone_2<Arrangement,ZoneVisitor>::Halfedge_handle
Arrangement_zone_2<Arrangement,ZoneVisitor>::_direct_intersecting_edge_to_right
    (const X_monotone_curve_2& cv_ins,
     const Point_2& cv_left_pt,
     Halfedge_handle query_he)
{
  // Make sure that the left endpoint of cv_ins lies on query_he.