arrangement_2_functions.h

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

    // Both vertices represent valid points.
    new_he = _insert_in_face_interior (cv, p_f, v1, v2,
                                       SMALLER);
  }
  else if (fict_prev1 == NULL && fict_prev2 != NULL)
  {
    // v1 represents a valid point and v2 is at infinity.
    new_he = _insert_from_vertex (cv,
                                  fict_prev2,
                                  v1,
                                  LARGER);
    new_he = new_he->opposite();
  }
  else if (fict_prev1 != NULL && fict_prev2 == NULL)
  {
    // v1 is at infinity and v2 represents a valid point.
    new_he = _insert_from_vertex (cv,
                                  fict_prev1,
                                  v2,
                                  SMALLER);
  }
  else
  {
    // Both vertices are at infinity. Note that we may create a new unbounded
    // face.
    bool        new_face_created = false;

    new_he = _insert_at_vertices (cv,
                                  fict_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 new halfedge directed from left to right.
  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Insert an unbounded x-monotone curve into the arrangement inside a given
// unbounded face, given a fictitious halfedge(s) that contains the unbounded
// end(s) of the curve.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle 
Arrangement_2<Traits,Dcel>::insert_in_face_interior
    (const X_monotone_curve_2& cv, 
     Halfedge_handle fict_he1, Halfedge_handle fict_he2)
{
  CGAL_precondition_msg (fict_he1->is_fictitious() && 
                         (fict_he2 == Halfedge_handle() ||
                          fict_he2->is_fictitious()),
                         "The given halfedge(s) must be fictitious.");

  // Check which one of cv's ends lie at infinity (both may lie there).
  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);
  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            *new_he;

  if (inf_x1 != NO_BOUNDARY || inf_y1 != NO_BOUNDARY)
  {
    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's left end.
    DHalfedge    *fict_prev1 = _halfedge (fict_he1);

    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.");

    CGAL_precondition_msg
      ((inf_x2 == NO_BOUNDARY && inf_y2 == NO_BOUNDARY &&
        fict_he2 == Halfedge_handle()) ||
       (_is_on_fictitious_edge (cv, MAX_END, inf_x2, inf_y2,
                                _halfedge (fict_he2),
                                eq_source, eq_target) &&
        ! eq_source && ! eq_target),
       "The given halfedge must contain the unbounded right end.");

    fict_prev1 = _split_fictitious_edge (fict_prev1,
                                         inf_x1, inf_y1);

    if (inf_x2 != NO_BOUNDARY || inf_y2 != NO_BOUNDARY)
    {
      // Split the fictitious edge and create a vertex at infinity that
      // represents cv's right end.
      DHalfedge    *fict_prev2;
      
      if (fict_he2 != Halfedge_handle())
      {
        if (fict_he2 != fict_he1)
          fict_prev2 = _halfedge (fict_he2);
        else if (fict_prev1->direction() == SMALLER)
          fict_prev2 = fict_prev1->next();
        else
          fict_prev2 = fict_prev1;
      }
      else
      {
        if (fict_prev1->direction() == SMALLER)
          fict_prev2 = fict_prev1->next();
        else
          fict_prev2 = fict_prev1;
      }

      fict_prev2 = _split_fictitious_edge (fict_prev2,
                                           inf_x2, inf_y2);

      // As both end vertices are at infinity, we may create a new unbounded
      // face.
      bool        new_face_created = false;

      new_he = _insert_at_vertices (cv,
                                    fict_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);
      }
    }
    else
    {
      // Create a new vertex that corresponds to cv's right endpoint.
      DVertex       *v2 = 
        _create_vertex (traits->construct_max_vertex_2_object()(cv));

      // Insert the curve.
      new_he = _insert_from_vertex (cv,
                                    fict_prev1,
                                    v2,
                                    SMALLER);
    }
  }
  else
  {
    // In this case only the right end of cv is unbounded.
    CGAL_precondition_msg (inf_x2 != NO_BOUNDARY || inf_y2 != NO_BOUNDARY,
                           "The inserted curve must be unbounded.");

    // Create a new vertex that corresponds to cv's left endpoint.
    DVertex       *v1 = 
      _create_vertex (traits->construct_min_vertex_2_object()(cv));
    
    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's right end.
    DHalfedge    *fict_prev2;
      
    if (fict_he2 != Halfedge_handle())
      fict_prev2 = _halfedge (fict_he2);
    else
      fict_prev2 = _halfedge (fict_he1);

    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.
    new_he = _insert_from_vertex (cv,
                                  fict_prev2,
                                  v1,
                                  LARGER);
    new_he = new_he->opposite();
  }

  // Return a handle to the new halfedge directed from left to right.
  return (Halfedge_handle (new_he));
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that its left 
// 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_left_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_min_vertex_2_object()(cv)),
     "The input vertex should be the left curve endpoint.");

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

  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));
  }

  // Check if the given vertex, corresponding to the left endpoint,
  // 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    *v1 = _vertex (v);
    DIso_vert  *iv = v1->isolated_vertex();
    DFace      *p_f = iv->face();

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

      fict_prev2 = _locate_along_ccb (p_f, 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);
    }

    // Remove the isolated vertex v1, 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_prev2 == NULL)
    {
      new_he = _insert_in_face_interior (cv, p_f, v1, v2,
                                         SMALLER);
    }
    else
    {
      new_he = _insert_from_vertex (cv,
                                    fict_prev2, v1,
                                    LARGER);
      new_he = new_he->opposite();
    }

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

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

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

  // If the vertex that corresponds to cv's right end lies at infinity,
  // create it now.
  if (v2 == NULL)
  {    
    // Locate a halfedge along the outer CCB of the incident face of prev1
    // that contains cv's right end in its range.
    DFace      *uf = prev1->is_on_hole() ? prev1->hole()->face() :
                                           prev1->face();
    CGAL_assertion (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 one its left
// 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_left_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_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.");

  // Check if 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);
  DVertex             *v2 = NULL;
  DHalfedge           *fict_prev2 = NULL;
  DHalfedge           *prev1 = _halfedge (prev);