arrangement_2_functions.h

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

  if (inf_x2 == NO_BOUNDARY && inf_y2 == NO_BOUNDARY)
  {
    // The curve has a valid right endpoint: Create a new vertex associated
    // with the curve's right endpoint.
    v2 = _create_vertex (traits->construct_max_vertex_2_object()(cv));
  }
  else
  {    
    // Locate a halfedge along the outer CCB of prev's incident face that
    // contains cv's right end in its range.
    DFace      *uf = prev1->is_on_hole() ? prev1->hole()->face() :
                                           prev1->face();
    CGAL_precondition (uf->is_unbounded());

    fict_prev2 = _locate_along_ccb (uf, cv, MAX_END,
                                    inf_x2, inf_y2);

    CGAL_assertion (fict_prev2 != NULL);

    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's right end.
    fict_prev2 = _split_fictitious_edge (fict_prev2,
                                         inf_x2, inf_y2);
  }

  // Perform the insertion (note that we know that prev1->vertex is smaller
  // than v2).
  DHalfedge  *new_he;

  if (fict_prev2 == NULL)
  {
    new_he = _insert_from_vertex (cv,
                                  prev1, v2,
                                  SMALLER);
  }
  else
  {
    // v2 lies at infinity. Note that we may create a new unbounded face.
    bool        new_face_created = false;

    new_he = _insert_at_vertices (cv,
                                  prev1, 
                                  fict_prev2,
                                  SMALLER,
                                  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 its left
// endpoints corresponds to a given arrangement vertex (given the exact
// place for the curve in the circular list around this vertex), and whose
// right end is unbounded and lies on a given fictitious edge.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle 
Arrangement_2<Traits,Dcel>::insert_from_left_vertex
    (const X_monotone_curve_2& cv,
     Halfedge_handle prev,
     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_min_vertex_2_object()(cv)),
     "The input halfedge's target should be the left curve endpoint.");
  CGAL_precondition_msg
    (_locate_around_vertex (_vertex(prev->target()),
                            cv, MIN_END) == _halfedge(prev),
     "In the clockwise order of curves around the vertex, "
     " cv must succeed the curve of prev.");

  DHalfedge        *prev1 = _halfedge (prev);

  // Check that cv's right end lies at infinity, and create a vertex v2 that
  // corresponds to this end.
  const Boundary_type  inf_x2 = traits->boundary_in_x_2_object()(cv, MAX_END);
  const Boundary_type  inf_y2 = traits->boundary_in_y_2_object()(cv, MAX_END);
  DHalfedge           *fict_prev2 = _halfedge (fict_he);

  CGAL_precondition_code (
    bool   eq_source; 
    bool   eq_target;
  );
  CGAL_precondition_msg 
    (_is_on_fictitious_edge (cv, MAX_END, inf_x2, inf_y2, fict_prev2,
                             eq_source, eq_target) &&
     ! eq_source && ! eq_target,
     "The given halfedge must contain the unbounded right end.");

  fict_prev2 = _split_fictitious_edge (fict_prev2,
                                       inf_x2, inf_y2);

  // 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,
                                            prev1, 
                                            fict_prev2,
                                            SMALLER,
                                            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 its right
// endpoint corresponds to a given arrangement vertex.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_from_right_vertex
    (const X_monotone_curve_2& cv,
     Vertex_handle v)
{
  CGAL_precondition_msg
    (! v->is_at_infinity(),
     "The input vertex must not lie at infinity.");
  CGAL_precondition_msg
    (traits->equal_2_object() (v->point(),
                               traits->construct_max_vertex_2_object()(cv)),
     "The input vertex should be the right curve endpoint.");

  // Check if cv's left end lies at infinity. In case it is a regular
  // point, create a normal vertex that correspond to this point.
  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);
  DVertex             *v1 = NULL;
  DHalfedge           *fict_prev1 = NULL;

  if (inf_x1 == NO_BOUNDARY && inf_y1 == NO_BOUNDARY)
  {
    // The curve has a valid left endpoint: Create a new vertex associated
    // with the curve's left endpoint.
    v1 = _create_vertex (traits->construct_min_vertex_2_object()(cv));
  }

  // Check if the given vertex is isolated.
  if (v->is_isolated())
  {
    // The given vertex is an isolated one: We should in fact insert the curve
    // in the interior of the face containing this vertex.
    DVertex    *v2 = _vertex (v);
    DIso_vert  *iv = v2->isolated_vertex();
    DFace      *p_f = iv->face();

    // If the vertex that corresponds to cv's left end lies at infinity,
    // create it now.
    if (v1 == NULL)
    {    
      // Locate a halfedge of f's outer CCB such that contains cv's left end
      // in its range.
      CGAL_assertion (p_f->is_unbounded());

      fict_prev1 = _locate_along_ccb (p_f, cv, MIN_END,
                                      inf_x1, inf_y1);

      CGAL_assertion (fict_prev1 != NULL);

      // Split the fictitious edge and create a vertex at infinity that
      // represents cv's left end.
      fict_prev1 = _split_fictitious_edge (fict_prev1,
                                           inf_x1, inf_y1);
    }

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

    // Create the edge connecting the two vertices (note that we know that
    // v1 is smaller than v2).
    DHalfedge  *new_he;

    if (fict_prev1 == NULL)
    {
      new_he = _insert_in_face_interior (cv, p_f, v1, v2,
                                         SMALLER);
    }
    else
    {
      new_he = _insert_from_vertex (cv,
                                    fict_prev1, v2,
                                    SMALLER);
    }
    
    // Return a handle to the new halfedge whose target is the new vertex v1.
    return (Halfedge_handle (new_he->opposite()));
  }

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

  CGAL_assertion_msg
    (prev2 != NULL,
     "The inserted curve should not exist in the arrangement.");
  
  // If the vertex that corresponds to cv's left end lies at infinity,
  // create it now.
  if (v1 == NULL)
  {    
    // Locate a halfedge along the outer CCB of the incident face of prev2
    // that contains cv's left end in its range.
    DFace      *uf = prev2->is_on_hole() ? prev2->hole()->face() :
                                           prev2->face();
    CGAL_assertion (uf->is_unbounded());

    fict_prev1 = _locate_along_ccb (uf, cv, MIN_END,
                                    inf_x1, inf_y1);

    CGAL_assertion (fict_prev1 != NULL);

    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's left end.
    fict_prev1 = _split_fictitious_edge (fict_prev1,
                                         inf_x1, inf_y1);
  }

  // Perform the insertion (note that we know that prev2->vertex is larger
  // than v1).
  DHalfedge  *new_he;

  if (fict_prev1 == NULL)
  {
    new_he = _insert_from_vertex (cv,
                                  prev2, v1,
                                  LARGER);
  }
  else
  {
    // v1 lies at infinity. Note that we may create a new unbounded face.
    bool        new_face_created = false;

    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 v1.
  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that its right
// endpoint corresponds to a given arrangement vertex, given the exact place
// for the curve in the circular list around this vertex.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_from_right_vertex
    (const X_monotone_curve_2& cv,
     Halfedge_handle prev)
{
  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.");

  // Check if 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);
  DVertex             *v1 = NULL;
  DHalfedge           *fict_prev1 = NULL;
  DHalfedge           *prev2 = _halfedge (prev);

  if (inf_x1 == NO_BOUNDARY && inf_y1 == NO_BOUNDARY)
  {
    // The curve has a valid left endpoint: Create a new vertex associated
    // with the curve's left endpoint.
    v1 = _create_vertex (traits->construct_min_vertex_2_object()(cv));
  }
  else
  {    
    // Locate a halfedge along the outer CCB of prev's incident face that
    // contains cv's left end in its range.
    DFace      *uf = prev2->is_on_hole() ? prev2->hole()->face() :
                                           prev2->face();
    CGAL_precondition (uf->is_unbounded());

    fict_prev1 = _locate_along_ccb (uf, cv, MIN_END,
                                    inf_x1, inf_y1);

    CGAL_assertion (fict_prev1 != NULL);

    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's left end.
    fict_prev1 = _split_fictitious_edge (fict_prev1,
                                         inf_x1, inf_y1);
  }

  // Perform the insertion (note that we know that prev2->vertex is larger
  // than v1).
  DHalfedge  *new_he;

  if (fict_prev1 == NULL)
  {
    new_he = _insert_from_vertex (cv,
                                  prev2, v1,
                                  LARGER);
  }
  else
  {
    // v1 lies at infinity. Note that we may create a new unbounded face.
    bool        new_face_created = false;

    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 v1.
  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that its right
// endpoint corresponds to a given arrangement vertex (given the exact
// place for the curve in the circular list around this vertex), and whose
// left end is unbounded and lies on a given fictitious edge.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle 
Arrangement_2<Traits,Dcel>::insert_from_right_vertex
    (const X_monotone_curve_2& cv,
     Halfedge_handle prev,