arrangement_2_insert.h

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

    obj1 = arr_access.locate_unbounded_end (c, MIN_END);
    
    // The unbounded end should lie on a fictitious edge.
    CGAL_precondition_msg
        (object_cast<Vertex_const_handle> (&obj1) == NULL,
         "The curve must not overlap an existing edge.");
  
    fict_hh1 = object_cast<Halfedge_const_handle> (&obj1);
    CGAL_assertion (fict_hh1 != NULL);
  }

  // Check whether the right end of c lies at infinity, or whether it is a
  // normal endpoint, and locate it in the arrangement accordingly.
  const Boundary_type  inf_x2 = traits->boundary_in_x_2_object() (c, MAX_END);
  const Boundary_type  inf_y2 = traits->boundary_in_y_2_object() (c, MAX_END);
  CGAL::Object         obj2;
  const Halfedge_const_handle *fict_hh2 = NULL;
  const Vertex_const_handle   *vh2 = NULL;

  if (inf_x2 == NO_BOUNDARY && inf_y2 == NO_BOUNDARY)
  {
    // We have a normal right endpoint.
    obj2 = pl.locate (arr.get_traits()->construct_max_vertex_2_object() (c));

    // The endpoint must not lie on an existing edge, but may coincide with
    // and existing vertex vh2.
    CGAL_precondition_msg
      (object_cast<Halfedge_const_handle> (&obj2) == NULL,
       "The curve must not intersect an existing edge.");

    vh2 = object_cast<Vertex_const_handle> (&obj2);
  }
  else
  {
    // We have an unbounded right end.
    obj2 = arr_access.locate_unbounded_end (c, MAX_END);

    // The unbounded end should lie on a fictitious edge.
    CGAL_precondition_msg
        (object_cast<Vertex_const_handle> (&obj2) == NULL,
         "The curve must not overlap an existing edge.");
  
    fict_hh2 = object_cast<Halfedge_const_handle> (&obj2);
    CGAL_assertion (fict_hh2 != NULL);
  }

  // Notify the arrangement observers that a global operation is about to 
  // take place.
  arr_access.notify_before_global_change();

  // Check whether the located features containing the curve endpoints
  // are vertices or faces, and use the proper specialized insertion function
  // accordingly.
  typename Arrangement_2::Halfedge_handle             res;

  if (fict_hh1 == NULL && fict_hh2 == NULL)
  {
    // Both endpoints are finite.
    if (vh1 != NULL)
    {
      if (vh2 != NULL)
      {
        // Both endpoints are associated with a existing vertices.
        // In this case insert_at_vertices() already returns a halfedge
        // directed from left to right.
        res = arr.insert_at_vertices (c,
                                      arr.non_const_handle (*vh1),
                                      arr.non_const_handle (*vh2));
      }
      else
      {
        // Only the left endpoint is associated with an existing vertex.
        // In this case insert_from_left_vertex() returns a halfedge directed
        // to the new vertex it creates, so it is already directed from left to
        // right.
        res = arr.insert_from_left_vertex (c,
                                           arr.non_const_handle (*vh1));
      }
    }
    else
    {
      if (vh2 != NULL)
      {
        // Only the right endpoint is associated with an existing vertex.
        // In this case insert_from_left_vertex() returns a halfedge directed
        // to the new vertex it creates, so it is directed from right to left
        // and we take its twin halfedge instead.
        res = arr.insert_from_right_vertex (c,
                                            arr.non_const_handle (*vh2));
        res = res->twin();
      }
      else
      {
        // Both endpoints are not associated with existing vertices, so
        // we must insert the curve in the interior of a face.
        // In this case insert_in_face_interior() already returns a halfedge
        // directed from left to right.
        const typename Arrangement_2::Face_const_handle  *fh1;
        const typename Arrangement_2::Face_const_handle  *fh2;

        fh1 = object_cast<typename Arrangement_2::Face_const_handle> (&obj1);
        fh2 = object_cast<typename Arrangement_2::Face_const_handle> (&obj2);

        CGAL_assertion_msg 
          (fh1 != NULL && fh2 != NULL && *fh1 == *fh2,
           "The curve intersects the interior of existing edges.");

        if (fh1 != NULL && fh2 != NULL && *fh1 == *fh2)
        {
          res = arr.insert_in_face_interior (c,
                                             arr.non_const_handle (*fh1));
        }
      }
    }
  }
  else if (fict_hh1 != NULL && fict_hh2 == NULL)
  {
    // The left end is unbounded and the right endpoint is bounded.
    if (vh2 != NULL)
    {
      res = arr.insert_from_right_vertex (c,
                                          arr.non_const_handle (*vh2));
      res = res->twin();
    }
    else
    {
      res = arr.insert_in_face_interior (c,
                                         arr.non_const_handle (*fict_hh1));
    }
  }
  else if (fict_hh1 == NULL && fict_hh2 != NULL)
  {
    // The left endpoint is bounded and the right end is unbounded.
    if (vh1 != NULL)
    {
      res = arr.insert_from_left_vertex (c,
                                         arr.non_const_handle (*vh1));
    }
    else
    {
      res = arr.insert_in_face_interior (c,
                                         arr.non_const_handle (*fict_hh2));
    }
  }
  else
  {
    // Both curve ends are unbounded. In this case the two fictitious
    // halfedges must belong to the same unbounded face.
    typename Arrangement_2::Face_const_handle  fh1 = (*fict_hh1)->face();
    typename Arrangement_2::Face_const_handle  fh2 = (*fict_hh2)->face();

    CGAL_assertion_msg 
      (fh1 == fh2,
       "The curve intersects the interior of existing edges.");
    
    if (fh1 == fh2)
    {
      res = arr.insert_in_face_interior (c,
                                         arr.non_const_handle (fh1));
    }
  }

  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  // Return the resulting halfedge from the insertion operation.
  return (res);
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that the curve
// interior does not intersect with any existing edge or vertex in the
// arragement (incremental insertion).
// Overloaded version with no point location object - the walk point-location
// strategy is used as default.
//
template <class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
insert_non_intersecting_curve (Arrangement_2<Traits,Dcel>& arr,
                               const typename Traits::X_monotone_curve_2& c)
{
  typedef Arrangement_2<Traits, Dcel>                          Arrangement_2;
  typedef Arr_walk_along_line_point_location<Arrangement_2>    Walk_pl;
  
  // create walk point location object
  Walk_pl    walk_pl(arr);

  return (insert_non_intersecting_curve (arr, c, walk_pl));
}

//-----------------------------------------------------------------------------
// Insert a range of pairwise interior-disjoint x-monotone curves into
// the arrangement, such that the curve interiors do not intersect with
// any existing edge or vertex in the arragement (aggregated insertion).
//
template <class Traits, class Dcel, class InputIterator>
void insert_non_intersecting_curves (Arrangement_2<Traits,Dcel>& arr,
                                     InputIterator begin, InputIterator end)
{
  // Notify the arrangement observers that a global operation is about to 
  // take place.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  arr_access.notify_before_global_change();

  // Perform the aggregated insertion.
  if(arr.is_empty())
  {
    // Perform the aggregated insertion.
    Arr_non_x_construction<Arrangement_2>  non_x_construct (arr);
    non_x_construct.insert_curves(begin, end);
  }
  else
  {
    Arr_non_x_addition<Arrangement_2>      non_x_adder(arr);
    non_x_adder.insert_curves (begin, end);
  }
  
  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  return;
}

//-----------------------------------------------------------------------------
// Remove an edge from the arrangement. In case it is possible to merge
// the edges incident to the end-vertices of the removed edge after its
// deletion, the function performs these merges as well.
//
template <class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Face_handle
remove_edge (Arrangement_2<Traits,Dcel>& arr,
             typename Arrangement_2<Traits,Dcel>::Halfedge_handle e)
{
  // Notify the arrangement observers that a global operation is about to 
  // take place.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  arr_access.notify_before_global_change();

  // Keep track of the end-vertices of the edge we are about to remove.
  typename Arrangement_2::Vertex_handle  v_ends[2];
  bool                                   is_removed[2];

  v_ends[0] = e->source();
  is_removed[0] = (v_ends[0]->is_at_infinity() || v_ends[0]->degree() == 1);
  v_ends[1] = e->target();
  is_removed[1] = (v_ends[1]->is_at_infinity() || v_ends[1]->degree() == 1);

  // Remove the edge from the arrangement.
  typename Arrangement_2::Face_handle    face = arr.remove_edge (e);

  // Examine the end-vertices: If a vertex has now two incident edges, and the
  // curves associated with these edges can be merged, merge the two edges and
  // remove the vertex.
  typedef Arr_traits_adaptor_2<Traits>                   Traits_adaptor_2;

  Traits_adaptor_2                *traits =
                         static_cast<Traits_adaptor_2*>(arr.get_traits());

  typename Arrangement_2::Halfedge_around_vertex_circulator  circ;
  typename Arrangement_2::Halfedge_handle                    e1, e2;
  int                                                        i;

  for (i = 0; i < 2; i++)
  {
    if (! is_removed[i] && v_ends[i]->degree() == 2)
    {
      // Get the two edges incident to the end-vertex.
      circ = v_ends[i]->incident_halfedges();
      e1 = circ;
      ++circ;
      e2 = circ;

      // Check if it is possible to merge the two edges.
      if (traits->are_mergeable_2_object() (e1->curve(), e2->curve()))
      {
        // Merge the two curves.
        typename Traits::X_monotone_curve_2   cv;
        traits->merge_2_object() (e1->curve(), e2->curve(),
                                  cv);

        // Merge the two edges in the arrangement.
        arr.merge_edge (e1, e2, cv);
      }
    }
  }

  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  // Return the face remaining after the removal of the edge.
  return (face);
}

//-----------------------------------------------------------------------------
// Insert a vertex that corresponds to a given point into the arrangement.
// The inserted point may lie on any existing arrangement feature.
//
template <class Traits, class Dcel, class PointLocation>
typename Arrangement_2<Traits,Dcel>::Vertex_handle
insert_point (Arrangement_2<Traits,Dcel>& arr,
              const typename Traits::Point_2& p,
              const PointLocation& pl)
{
  // Obtain an arrangement accessor.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;
  // Act according to the type of arrangement feature that contains the point.
  const typename Arrangement_2::Face_const_handle      *fh;
  const typename Arrangement_2::Halfedge_const_handle  *hh;
  const typename Arrangement_2::Vertex_const_handle    *vh;
  typename Arrangement_2::Vertex_handle                 vh_for_p;

  Arr_accessor<Arrangement_2>                           arr_access (arr);

  // Locate the given point in the arrangement.
  CGAL::Object        obj = pl.locate (p);

  // Notify the arrangement observers that a global operation is about to 
  // take place.
  arr_access.notify_before_global_change();

  if ((fh = object_cast<typename Arrangement_2::Face_const_handle>(&obj)) 
      != NULL) 
  {
    // p lies inside a face: Insert it as an isolated vertex it the interior of
    // this face.
    vh_for_p = arr.insert_in_face_interior (p,
                                            arr.non_const_handle (*fh));
  }
  else if ((hh = 
	    object_cast<typename Arrangement_2::Halfedge_const_handle>(&obj)) 
	   != NULL) 
  {
    // p lies in the interior of an edge: Split this edge to create a new
    // vertex associated with p.
    typename Traits::X_monotone_curve_2                   sub_cv1, sub_cv2;
    typename Arrangement_2::Halfedge_handle  split_he;
   
    arr.get_traits()->split_2_object() ((*hh)->curve(), p,
                                        sub_cv1, sub_cv2);

    split_he = arr.split_edge (arr.non_const_handle (*hh),
                               sub_cv1, sub_cv2);