arrangement_2_functions.h

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

     Halfedge_handle fict_he)
{
  CGAL_precondition_msg
    (! prev->target()->is_at_infinity(),
     "The input vertex must not lie at infinity.");
  CGAL_precondition_msg
    (traits->equal_2_object() (prev->target()->point(),
                               traits->construct_max_vertex_2_object()(cv)),
     "The input halfedge's target should be the right curve endpoint.");
  CGAL_precondition_msg
    (_locate_around_vertex (_vertex(prev->target()),
                            cv, MAX_END) == _halfedge(prev),
     "In the clockwise order of curves around the vertex, "
     " cv must succeed the curve of prev.");

  DHalfedge        *prev2 = _halfedge (prev);

  // Check that cv's left end lies at infinity, and create a vertex v1 that
  // corresponds to this end.
  const Boundary_type  inf_x1 = traits->boundary_in_x_2_object()(cv, MIN_END);
  const Boundary_type  inf_y1 = traits->boundary_in_y_2_object()(cv, MIN_END);
  DHalfedge           *fict_prev1 = _halfedge (fict_he);

  CGAL_precondition_code (
    bool   eq_source; 
    bool   eq_target;
  );
  CGAL_precondition_msg 
    (_is_on_fictitious_edge (cv, MIN_END, inf_x1, inf_y1, fict_prev1,
                             eq_source, eq_target) &&
     !eq_source && !eq_target,
     "The given halfedge must contain the unbounded left end.");

  fict_prev1 = _split_fictitious_edge (fict_prev1,
                                       inf_x1, inf_y1);

  // Insert the curve and create an edge connecting the the two vertices.
  // Note that we may create a new unbounded face.
  bool        new_face_created = false;
  DHalfedge  *new_he = _insert_at_vertices (cv,
                                            prev2, 
                                            fict_prev1,
                                            LARGER,
                                            new_face_created,
                                            true);
  
  if (new_face_created)
  {
    CGAL_assertion (! new_he->is_on_hole());
    _relocate_in_new_face (new_he);
  }

  // Return a handle to the halfedge directed toward the new vertex v2.
  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that both its
// endpoints corresponds to a given arrangement vertex.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_at_vertices (const X_monotone_curve_2& cv,
                                                Vertex_handle v1,
                                                Vertex_handle v2)
{
  CGAL_precondition_msg
    (! v1->is_at_infinity() && ! v2->is_at_infinity(),
     "The input vertices must not lie at infinity.");

  Curve_end    ind1;
  Curve_end    ind2;

  if (traits->equal_2_object() (v1->point(),
                                traits->construct_min_vertex_2_object()(cv)))
  {
    CGAL_precondition_msg 
      (traits->equal_2_object()(v2->point(),
                                traits->construct_max_vertex_2_object()(cv)),
       "The input vertices should match the curve endpoints.");

    ind1 = MIN_END;
    ind2 = MAX_END;
  }
  else
  {
    CGAL_precondition_msg
      (traits->equal_2_object()(v2->point(),
                                traits->construct_min_vertex_2_object()(cv)) &&
       traits->equal_2_object()(v1->point(),
                                traits->construct_max_vertex_2_object()(cv)),
       "The input vertices should match the curve endpoints.");

    ind1 = MAX_END;
    ind2 = MIN_END;
  }

  // Check whether one of the vertices is isolated.
  if (v1->is_isolated())
  {
    // Get the face containing the isolated vertex v1.
    DVertex    *p_v1 = _vertex (v1);
    DIso_vert  *iv1 = p_v1->isolated_vertex();
    DFace      *f1 = iv1->face();

    // Remove the isolated vertex v1, as it will not be isolated any more.
    f1->erase_isolated_vertex (iv1->iterator());
    dcel.delete_isolated_vertex (iv1);

    if (v2->is_isolated())
    {
      // Both end-vertices are isolated. Make sure they are contained inside
      // the same face.
      DVertex    *p_v2 = _vertex (v2);
      DIso_vert  *iv2 = p_v2->isolated_vertex();

      CGAL_assertion_code (
        DFace      *f2 = iv2->face();
      );

      CGAL_assertion_msg
        (f1 == f2,
         "The inserted curve should not intersect the existing arrangement.");

      // Remove the isolated vertex v2, as it will not be isolated any more.
      f1->erase_isolated_vertex (iv2->iterator());
      dcel.delete_isolated_vertex (iv2);

      // Perform the insertion.
      Comparison_result  res = traits->compare_xy_2_object() (v1->point(),
                                                              v2->point());
      CGAL_assertion (res != EQUAL);

      DHalfedge  *new_he = _insert_in_face_interior (cv, f1,
                                                     p_v1, p_v2,
                                                     res);

      return (Halfedge_handle (new_he));
    }

    // Go over the incident halfedges around v2 and find the halfedge after
    // which the new curve should be inserted.
    DHalfedge  *prev2 = _locate_around_vertex (_vertex (v2), cv, ind2);

    CGAL_assertion_msg
      (prev2 != NULL,
       "The inserted curve should not exist in the arrangement.");

    CGAL_assertion_msg
      (f1 == _face(Halfedge_handle (prev2)->face()),
       "The inserted curve should not intersect the existing arrangement.");

    // Perform the insertion. Note that the returned halfedge is directed
    // toward v1 (and not toward v2), so we return its twin.
    Comparison_result  res = traits->compare_xy_2_object() (v2->point(),
                                                            v1->point());
    CGAL_assertion (res != EQUAL);

    DHalfedge  *new_he = _insert_from_vertex (cv,
                                              prev2, p_v1,
                                              res);

    return (Halfedge_handle (new_he->opposite()));
  }
  else if (v2->is_isolated())
  {
    // Get the face containing the isolated vertex v2.
    DVertex    *p_v2 = _vertex (v2);
    DIso_vert  *iv2 = p_v2->isolated_vertex();
    DFace      *f2 = iv2->face();

    // Remove the isolated vertex v2, as it will not be isolated any more.
    f2->erase_isolated_vertex (iv2->iterator());
    dcel.delete_isolated_vertex (iv2);

    // Go over the incident halfedges around v1 and find the halfedge after
    // which the new curve should be inserted.
    DHalfedge  *prev1 = _locate_around_vertex (_vertex (v1), cv, ind1);

    CGAL_assertion_msg
      (prev1 != NULL,
       "The inserted curve should not exist in the arrangement.");

    CGAL_assertion_msg
      (f2 == _face (Halfedge_handle (prev1)->face()),
       "The inserted curve should not intersect the existing arrangement.");

    // Perform the insertion.
    Comparison_result  res = traits->compare_xy_2_object() (v1->point(),
                                                            v2->point());
    CGAL_assertion (res != EQUAL);

    DHalfedge  *new_he = _insert_from_vertex (cv,
                                              prev1, p_v2,
                                              res);

    return (Halfedge_handle (new_he));
  }

  // Go over the incident halfedges around v1 and v2 and find the two
  // halfedges after which the new curve should be inserted, respectively.
  DHalfedge  *prev1 = _locate_around_vertex (_vertex (v1), cv, ind1);
  DHalfedge  *prev2 = _locate_around_vertex (_vertex (v2), cv, ind2);

  CGAL_assertion_msg
    (prev1 != NULL && prev2 != NULL,
     "The inserted curve should not exist in the arrangement.");

  // Perform the insertion.
  return (insert_at_vertices (cv,
                              Halfedge_handle(prev1),
                              Halfedge_handle(prev2)));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that both its
// endpoints correspond to given arrangement vertices, given the exact
// place for the curve in one of the circular lists around a vertex.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_at_vertices (const X_monotone_curve_2& cv,
                                                Halfedge_handle prev1,
                                                Vertex_handle v2)
{
  CGAL_precondition_msg
    (! prev1->target()->is_at_infinity() && ! v2->is_at_infinity(),
     "The input vertices must not lie at infinity.");

  Curve_end    ind2;

  if (traits->equal_2_object() (prev1->target()->point(),
                                traits->construct_min_vertex_2_object()(cv)))
  {
    CGAL_precondition_msg 
      (traits->equal_2_object()(v2->point(),
                                traits->construct_max_vertex_2_object()(cv)),
       "The input vertices should match the curve endpoints.");

    ind2 = MAX_END;
  }
  else
  {
    CGAL_precondition_msg
      (traits->equal_2_object()(v2->point(),
                                traits->construct_min_vertex_2_object()(cv)) &&
       traits->equal_2_object()(prev1->target()->point(),
                                traits->construct_max_vertex_2_object()(cv)),
       "The input vertices should match the curve endpoints.");

    ind2 = MIN_END;
  }

  // Check whether v2 is an isolated vertex.
  if (v2->is_isolated())
  {
    // Get the face containing the isolated vertex v2.
    DVertex    *p_v2 = _vertex (v2);
    DIso_vert  *iv2 = p_v2->isolated_vertex();
    DFace      *f2 = iv2->face();

    CGAL_assertion_msg
      (f2 == _face (prev1->face()),
       "The inserted curve should not intersect the existing arrangement.");

    // Remove the isolated vertex v2, as it will not be isolated any more.
    f2->erase_isolated_vertex (iv2->iterator());
    dcel.delete_isolated_vertex (iv2);

    // Perform the insertion.
    Comparison_result  res = traits->compare_xy_2_object() 
                                             (prev1->target()->point(),
                                              v2->point());
    CGAL_assertion (res != EQUAL);

    DHalfedge  *new_he = _insert_from_vertex (cv,
                                              _halfedge (prev1), p_v2,
                                              res);

    return (Halfedge_handle (new_he));
  }

  // Go over the incident halfedges around v2 and find the halfedge after
  // which the new curve should be inserted.
  DHalfedge  *prev2 = _locate_around_vertex (_vertex (v2), cv, ind2);

  CGAL_assertion_msg
    (prev2 != NULL,
     "The inserted curve should not exist in the arrangement.");

  // Perform the insertion.
  return (insert_at_vertices (cv,
                              prev1,
                              Halfedge_handle(prev2)));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that both its
// endpoints correspond to given arrangement vertices, given the exact
// place for the curve in both circular lists around these two vertices.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_at_vertices (const X_monotone_curve_2& cv,
                                                Halfedge_handle prev1,
                                                Halfedge_handle prev2)
{
  CGAL_precondition_msg
    (! prev1->target()->is_at_infinity() &&
     ! prev2->target()->is_at_infinity(),
     "The input vertices must not lie at infinity.");

  CGAL_precondition_msg
    ((traits->equal_2_object()(prev1->target()->point(),
                               traits->construct_min_vertex_2_object()(cv)) &&
      traits->equal_2_object()(prev2->target()->point(),
                               traits->construct_max_vertex_2_object()(cv))) ||
     (traits->equal_2_object()(prev2->target()->point(),
                               traits->construct_min_vertex_2_object()(cv)) &&
      traits->equal_2_object()(prev1->target()->point(),
                               traits->construct_max_vertex_2_object()(cv))),
     "The input halfedges' target points should match the curve endpoints.");

  // Check if e1 and e2 are on the same connected component.
  DHalfedge  *p_prev1 = _halfedge (prev1);
  DHalfedge  *p_prev2 = _halfedge (prev2);
  DHole      *hole1 = (p_prev1->is_on_hole()) ? p_prev1->hole() : NULL;
  DHole      *hole2 = (p_prev2->is_on_hole()) ? p_prev2->hole() : NULL;
  bool        prev1_before_prev2 = true;

  if (hole1 == hole2 && hole1 != NULL)
  {
    // If prev1 and prev2 are on different components, the insertion of the
    // new curve does not generate a new face, so the way we send these
    // halfedge pointers to the auxiliary function _insert_at_vertices() does
    // not matter.
    // However, in our case, where the two halfedges are reachable from one
    // another and are located on the same hole, a new face will be created
    // and form a hole inside their current incident face. In this case we
    // have to arrange prev1 and prev2 so that the new face (hole) will be
    // incident to the correct halfedge, directed from prev1's target to
    // prev2's target.
    // To do this, we check whether prev1 lies inside the new face we are
    // about to create (or alternatively, whether prev2 does not lie inside
    // this new face).
    const unsigned int  dist1 = _halfedge_distance (p_prev1, p_prev2);
    const unsigned int  dist2 = _halfedge_distance (p_prev2, p_prev1);

    prev1_before_prev2 = (dist1 > dist2) ?
      (_is_inside_new_face (p_prev1, p_prev2, cv)) :
      (! _is_inside_new_face (p_prev2, p_prev1, cv));
  }

  // Compare the points associated with the end-vertices of the edge we are
  // about to create.
  Comparison_result    res;

  if (prev1_before_prev2)
    res = traits->compare_xy_2_object() (p_prev1->vertex()->point(),
                                         p_prev2->vertex()->point());
  else
    res = traits->compare_xy_2_object() (p_prev2->vertex()->point(),
                                         p_prev1->vertex()->point());

  // Perform the insertion.
  bool        new_face_created = false;
  DHalfedge  *new_he = (prev1_before_prev2) ?
    _insert_at_vertices (cv, p_prev1, p_prev2, res, new_face_created, false) :
    _insert_at_vertices (cv, p_prev2, p_prev1, res, new_face_created, false);

  if (new_face_created)
  {
    // In case a new face has been created (pointed by the new halfedge we
    // obtained), we have to examine the holes and isolated vertices in the
    // existing face (pointed by the twin halfedge) and move the relevant