arrangement_2_functions.h

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

    // holes and isolated vertices into the new face.
    _relocate_in_new_face (new_he);
  }

  // Return a handle to the new halfedge directed from prev1's target to
  // prev2's target. Note that this may be the twin halfedge of the one
  // returned by _insert_at_vertices();
  if (! prev1_before_prev2)
    new_he = new_he->opposite();

  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Replace the point associated with the given vertex.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Vertex_handle
Arrangement_2<Traits,Dcel>::modify_vertex (Vertex_handle vh,
                                           const Point_2& p)
{
  CGAL_precondition_msg
    (! vh->is_at_infinity(),
     "The modified vertex must not lie at infinity.");
  CGAL_precondition_msg (traits->equal_2_object() (vh->point(), p),
                         "The new point is different from the current one.");

  // Modify the vertex.
  _modify_vertex (_vertex (vh), p);

  // Return a handle to the modified vertex.
  return (vh);
}

//-----------------------------------------------------------------------------
// Remove an isolated vertex from the interior of a given face.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Face_handle
Arrangement_2<Traits,Dcel>::remove_isolated_vertex (Vertex_handle v)
{
  CGAL_precondition (v->is_isolated());

  // Get the face containing v.
  DVertex      *p_v = _vertex (v);
  DIso_vert    *iv = p_v->isolated_vertex();
  DFace        *p_f = iv->face();
  Face_handle   f = Face_handle (p_f);
  
  // Notify the observers that we are abount to remove a vertex.
  _notify_before_remove_vertex (v);

  // Remove the isolated vertex from the face that contains it.
  p_f->erase_isolated_vertex (iv->iterator());
  dcel.delete_isolated_vertex (iv);

  // Delete the vertex.
  _delete_point (p_v->point());
  dcel.delete_vertex (p_v);

  // Notify the observers that the vertex has been removed.
  _notify_after_remove_vertex ();

  // Return a handle for the face that used to contain the deleted vertex.
  return (f);
}

//-----------------------------------------------------------------------------
// Replace the x-monotone curve associated with the given edge.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::modify_edge (Halfedge_handle e,
                                         const X_monotone_curve_2& cv)
{
  CGAL_precondition_msg (! e->is_fictitious(),
                         "The edge must be a valid one.");
  CGAL_precondition_msg (traits->equal_2_object() (e->curve(), cv),
                         "The new curve is different from the current one.");

  // Modify the edge.
  _modify_edge (_halfedge (e), cv);

  // Return a handle to the modified halfedge.
  return (e);
}

//-----------------------------------------------------------------------------
// Split a given edge into two, and associate the given x-monotone
// curves with the split edges.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::split_edge (Halfedge_handle e,
                                        const X_monotone_curve_2& cv1,
                                        const X_monotone_curve_2& cv2)
{
  CGAL_precondition_msg (! e->is_fictitious(),
                         "The edge must be a valid one.");

  // Get the split halfedge and its twin, its source and target.
  DHalfedge       *he1 = _halfedge (e);
  DHalfedge       *he2 = he1->opposite();
  DVertex         *source = he2->vertex();
  CGAL_precondition_code (
    DVertex         *target = he1->vertex();
  );

  // Determine the point where we split the halfedge. We also determine which
  // curve should be associated with he1 (and he2), which is the curve who
  // has an endpoint that equals e's source, and which should be associated
  // with the new pair of halfedges we are about to split (the one who has
  // an endpoint which equals e's target).
  Point_2                    split_pt;
  const X_monotone_curve_2  *p_cv1 = NULL;
  const X_monotone_curve_2  *p_cv2 = NULL;

  if (traits->boundary_in_x_2_object()(cv1, MAX_END) == NO_BOUNDARY &&
      traits->boundary_in_y_2_object()(cv1, MAX_END) == NO_BOUNDARY)
  {
    const Point_2&  cv1_right = traits->construct_max_vertex_2_object() (cv1);

    if (traits->boundary_in_x_2_object()(cv2, MIN_END) == NO_BOUNDARY &&
        traits->boundary_in_y_2_object()(cv2, MIN_END) == NO_BOUNDARY &&
        traits->equal_2_object()(traits->construct_min_vertex_2_object()(cv2),
                                 cv1_right))
    {
      // cv1's right endpoint and cv2's left endpoint are equal, so this should
      // be the split point. Now we check whether cv1 is incident to e's source
      // and cv2 to its target, or vice versa.
      split_pt = cv1_right;

      if (_are_equal (source, cv1, MIN_END))
      {
        CGAL_precondition_msg
          (_are_equal (target, cv2, MAX_END),
           "The subcurve endpoints must match e's end vertices.");

        p_cv1 = &cv1;
        p_cv2 = &cv2;
      }
      else
      {
        CGAL_precondition_msg
          (_are_equal (source, cv2, MAX_END) &&
           _are_equal (target, cv1, MIN_END),
           "The subcurve endpoints must match e's end vertices.");

        p_cv1 = &cv2;
        p_cv2 = &cv1;      
      }
    }
  }

  if (p_cv1 == NULL && p_cv2 == NULL &&
      traits->boundary_in_x_2_object()(cv1, MIN_END) == NO_BOUNDARY &&
      traits->boundary_in_y_2_object()(cv1, MIN_END) == NO_BOUNDARY)
  {
    const Point_2&  cv1_left = traits->construct_min_vertex_2_object() (cv1);

    if (traits->boundary_in_x_2_object()(cv2, MAX_END) == NO_BOUNDARY &&
        traits->boundary_in_y_2_object()(cv2, MAX_END) == NO_BOUNDARY &&
        traits->equal_2_object()(traits->construct_max_vertex_2_object()(cv2),
                                 cv1_left))
    {
      // cv1's left endpoint and cv2's right endpoint are equal, so this should
      // be the split point. Now we check whether cv1 is incident to e's source
      // and cv2 to its target, or vice versa.
      split_pt = cv1_left;

      if (_are_equal (source, cv2, MIN_END))
      {
        CGAL_precondition_msg
          (_are_equal (target, cv1, MAX_END),
           "The subcurve endpoints must match e's end vertices.");

        p_cv1 = &cv2;
        p_cv2 = &cv1;
      }
      else
      {
        CGAL_precondition_msg
          (_are_equal (source, cv1, MAX_END) && 
           _are_equal (target, cv2, MIN_END),
           "The subcurve endpoints must match e's end vertices.");

        p_cv1 = &cv1;
        p_cv2 = &cv2;      
      }
    }
  }

  CGAL_precondition_msg (p_cv1 != NULL && p_cv2 != NULL,
                         "The two subcurves must have a common endpoint.");

  // Perform the split.
  return (Halfedge_handle (_split_edge (he1, split_pt, *p_cv1, *p_cv2)));
}

//-----------------------------------------------------------------------------
// Merge two edges to form a single edge, and associate the given x-monotone
// curve with the merged edge.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::merge_edge (Halfedge_handle e1,
                                        Halfedge_handle e2,
                                        const X_monotone_curve_2& cv)
{
  CGAL_precondition_msg (! e1->is_fictitious() && ! e2->is_fictitious(),
                         "The edges must be a valid.");

  // Assign pointers to the existing halfedges, such that we have:
  //
  //            he1      he3
  //         -------> ------->
  //       (.)      (.)v     (.)
  //         <------- <-------
  //            he2      he4
  //
  DHalfedge   *_e1 = _halfedge (e1);
  DHalfedge   *_e2 = _halfedge (e2);
  DHalfedge   *he1 = NULL;
  DHalfedge   *he2 = NULL;
  DHalfedge   *he3 = NULL;
  DHalfedge   *he4 = NULL;

  if (_e1->vertex() == _e2->opposite()->vertex())
  {
    he1 = _e1;
    he2 = he1->opposite();
    he3 = _e2;
    he4 = he3->opposite();
  }
  else if (_e1->opposite()->vertex() == _e2->opposite()->vertex())
  {
    he2 = _e1;
    he1 = he2->opposite();
    he3 = _e2;
    he4 = he3->opposite();
  }
  else if (_e1->vertex() == _e2->vertex())
  {
    he1 = _e1;
    he2 = he1->opposite();
    he4 = _e2;
    he3 = he4->opposite();
  }
  else if (_e1->opposite()->vertex() == _e2->vertex())
  {
    he2 = _e1;
    he1 = he2->opposite();
    he4 = _e2;
    he3 = he4->opposite();
  }
  else
  {
    CGAL_precondition_msg (false,
                           "The input edges do not share a common vertex.");
    return Halfedge_handle();
  }

  // The vertex we are about to delete is now he1's target vertex.
  // Make sure that he1 and he4 are the only halfedges directed to v.
  DVertex    *v = he1->vertex();

  CGAL_precondition_msg
    (! v->has_null_point(),
     "The vertex removed by the merge must not lie at infinity.");
  CGAL_precondition_msg
    (he1->next()->opposite() == he4 &&
     he4->next()->opposite() == he1,
     "The degree of the deleted vertex is greater than 2.");

  // Make sure the curve ends match the end vertices of the merged edge.
  CGAL_precondition_msg
    ((_are_equal (he2->vertex(), cv, MIN_END) && 
      _are_equal (he3->vertex(), cv, MAX_END)) ||
     (_are_equal (he3->vertex(), cv, MIN_END) && 
      _are_equal (he2->vertex(), cv, MAX_END)),
     "The endpoints of the merged curve must match the end vertices.");

  // Keep pointers to the components that contain two halfedges he3 and he2,
  // pointing at the end vertices of the merged halfedge.
  DHole       *hole1 = (he3->is_on_hole()) ? he3->hole() : NULL;
  DFace       *f1 = (hole1 == NULL) ? he3->face() : hole1->face();
  DHole       *hole2 = (he4->is_on_hole()) ? he4->hole() : NULL;
  DFace       *f2 = (hole2 == NULL) ? he4->face() : hole2->face();

  // Notify the observers that we are about to merge an edge.
  _notify_before_merge_edge (e1, e2, cv);

  // As he1 and he2 will evetually represent the merged edge, while he3 and he4
  // will be deleted, check if the deleted halfedges are represantatives of a
  // face boundary or a hole inside these faces. If so, replace he3 by he1 and
  // he4 by he2. Note that as we just change the hole representatives, we do
  // not have to notify the observers about the change.
  if (hole1 == NULL && f1->halfedge() == he3)
  {
    f1->set_halfedge (he1);
  }
  else if (hole1 != NULL)
  {
    if (*(hole1->iterator()) == he3)
    {
      f1->erase_hole (hole1->iterator());
      hole1->set_iterator (f1->add_hole (he1));
    }
  }

  if (hole2 == NULL && f2->halfedge() == he4)
  {
    f2->set_halfedge (he2);
  }
  else if (hole2 != NULL)
  {
    if (*(hole2->iterator()) == he4)
    {
      f2->erase_hole (hole2->iterator());
      hole2->set_iterator (f2->add_hole (he2));
    }
  }

  if (he3->vertex()->halfedge() == he3)
    // If he3 is the incident halfedge to its target, replace it by he1.
    he3->vertex()->set_halfedge (he1);

  // Disconnect he3 and he4 from the edge list.
  if (he3->next() == he4)
  {
    // he3 and he4 form an "antenna", so he1 and he2 must be connected
    // together.
    he1->set_next(he2);
  }
  else
  {
    he1->set_next (he3->next());
    he4->prev()->set_next (he2);
  }

  // Note that he1 (and its twin) is going to represent the merged edge while
  // he3 (and its twin) is going to be removed. We therefore associate the
  // merged curve with he1 and delete the curve associated with he3.
  he1->curve() = cv;
  _delete_curve (he3->curve());

  // Set the properties of the merged edge.
  he1->set_vertex (he3->vertex());

  // Notify the observers that we are about to delete a vertex.
  _notify_before_remove_vertex (Vertex_handle (v));

  // Delete the point associated with the merged vertex.
  _delete_point (v->point());

  // Delete the merged vertex.
  dcel.delete_vertex (v);

  // Notify the observers that the vertex has been deleted.
  _notify_after_remove_vertex ();

  // Delete the redundant halfedge pair.
  dcel.delete_edge (he3);

  // Create a handle for one of the merged halfedges.
  Halfedge_handle   hh (he1);

  // Notify the observers that the edge has been merge.
  _notify_after_merge_edge (hh);

  // Return a handle for one of the merged halfedges.
  return (hh);
}

//-----------------------------------