arrangement_zone_2_functions.h

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

    done = true;
  }
  else
  {
    // Split cv at the intersection point.
    traits->split_2_object() (cv,
                              intersect_p,
                              sub_cv1, sub_cv2);

    // Set cv to be the remaining portion.
    has_left_pt = true;
    left_pt = intersect_p;
    cv = sub_cv2;
  }

  const X_monotone_curve_2  *p_orig_curve = NULL;

  if (! found_iso_vert)
  {
    // Check whether intersect_p coincides with one of the end-vertices of the
    // halfedge that cv intersects.
    if (! intersect_he->source()->is_at_infinity() &&
        traits->equal_2_object() (intersect_p,
                                  intersect_he->source()->point()))
    {
      // We know that the right endpoint of sub_cv1 lies on the source vertex:
      right_v = intersect_he->source();
      right_he = invalid_he;
    }
    else if (! intersect_he->target()->is_at_infinity() &&
             traits->equal_2_object() (intersect_p,
                                       intersect_he->target()->point()))
    {
      // We know that the right endpoint of sub_cv1 lies on the target vertex:
      right_v = intersect_he->target();
      right_he = invalid_he;
    }
    else
    {
      // The right endpoint of sub_cv1 lies on the interior of intersect_he:
      // Obtain the halfedge with the correct direction (which should be the
      // predecessor of sub_cv1 if we split the edge around this vertex).
      right_v = invalid_v;

      right_he = _direct_intersecting_edge_to_left (sub_cv1, intersect_he);
    }

    // Store the curve currently associated with the intersecting halfedge.
    p_orig_curve = &(intersect_he->curve());
  }
  else
  {
    // The right endpoint of the subcurve coincides with an isolated vertex:
    right_v = intersect_v;
    right_he = invalid_he;
  }

  // Notify the visitor that the left endpoint of the first subcurve is
  // located within the current face and both its endpoint are located
  // on its boundary.
  Visitor_result  visitor_res = visitor->found_subcurve (sub_cv1,
                                                         face,
                                                         left_v, left_he,
                                                         right_v, right_he);

  // Check if we are done (either we have no remaining curve or if the
  // visitor has indicated we should end the process).
  if (done || visitor_res.second)
    return (true);

  // Move to the remaining portion of the curve, whose left endpoint is the
  // same as the right endpoint of sub_cv1. Note that we check if the visitor
  // has inserted the subcurve (in which case it should return a handle to
  // the resulting halfedge).
  Halfedge_handle  inserted_he = visitor_res.first;

  if (inserted_he != invalid_he)
  {
    if (right_v == invalid_v)
    {
      // If the right endpoint of the subcurve we have just detected was
      // not associated with an existing vertex, the inserted halfedge is
      // now targeted toward a newly created vertex that splits intersect_he
      // into two halfedges: (a) the next halfedge after inserted_he and (b)
      // the previous halfedge before inserted_he's twin.
      // The two halfedges (a) and (b) are now associated with the two
      // subcurves that result from splitting intersect_he->curve() at the
      // intersection point we have just detected, one extends to the left
      // and one to the right of this split point.
      const X_monotone_curve_2  *p_left_subcurve = NULL;
      const X_monotone_curve_2  *p_right_subcurve = NULL;

      if (inserted_he->next()->direction() == SMALLER)
      {
        // The next halfedge extends to the right of the split point:
        p_left_subcurve = &(inserted_he->twin()->prev()->curve());
        p_right_subcurve = &(inserted_he->next()->curve());
      }
      else
      {
        // The next halfedge extends to the left of the split point:
        p_right_subcurve = &(inserted_he->twin()->prev()->curve());
        p_left_subcurve = &(inserted_he->next()->curve());
      }

      // Associate the intersection list of the original curve with the
      // right subcurve, while we can associate an empty list with the
      // left subcurve, as we are now done with it.
      Intersect_map_iterator    iter = inter_map.find (p_orig_curve);
      Intersect_list            empty_inter_list;

      inter_map[p_right_subcurve] = iter->second;
      inter_map[p_left_subcurve] = empty_inter_list;

      // If necessary, erase the original curve from the intersection map.
      if (p_orig_curve != p_right_subcurve && p_orig_curve !=p_left_subcurve)
        inter_map.erase (p_orig_curve);
    }

    if (found_overlap && right_v == invalid_v)
    {
      // In case we have split the overlapping intersect_he, it now refers
      // to the wrong halfedge. the overlapping edge is either the successor
      // of the inserted halfedge or the predecessor of its twin, depending
      // on which one of these halfedges lies to the right of the split point.
      if (inserted_he->next()->direction() == SMALLER)
      {
        // The successor is directed to the right:
        intersect_he = inserted_he->next();
      }
      else
      {
        // The predecessor is directed to the left:
        CGAL_assertion (inserted_he->twin()->prev()->direction() == LARGER);

        intersect_he = inserted_he->twin()->prev();
      }
    }

    // The visitor has created an edge that corresponds to sub_cv1 and instered
    // it into the arrangement. In this case, left_pt should be associated
    // with the target vertex of the new halfedge.
    CGAL_assertion (traits->equal_2_object() (left_pt,
                                              inserted_he->target()->point()));

    left_v = inserted_he->target();

    // If right_he is known, it is possible to set left_he according to the
    // geometric information we have.
    if (right_he != invalid_he)
    {
      if ((ip_mult % 2) == 1)
      {
        // cv crosses right_he (which is now split into two), so the remaining
        // portion must be inserted after the next halfedge going clockwise
        // around left_v:
        //
        //              \   .                            .
        //               \ . remaining portion of cv     .
        //                x                              .
        //   inserted_he / \                             .
        //              /   \                            .
        left_he = inserted_he->next()->twin();
      }
      else if (ip_mult != 0)
      {
        // We have a tangency point. If right_he is directed from left to
        // right, we take the inserted halfedge to be left_he, otherwise
        // right_he itself becomes left_he:
        if (right_he->direction() == SMALLER)
          left_he = inserted_he;
        else
          left_he = right_he;
      }
      else
      {
        // Mutliplicity is unkown:
        left_he = invalid_he;
      }
    }
    else
    {
      // In case left_v used to be an isolated vertex, we know that the
      // inserted halfedge is its only incident halfedge and we can use it.
      // Otherwise, we do not know the identity of left_he.
      if (found_iso_vert)
        left_he = inserted_he;
      else
        left_he = invalid_he;
    }
  }
  else
  {
    // The visitor has not created a new edge. We proceed using the previously
    // computed arrangement features.
    left_v = right_v;

    if (right_he != invalid_he)
    {
      // In case cv crosses the interior of the right_he halfedge (the
      // multiplicity of the intersection is odd), we know that the ramaining
      // portion of the curve lies in the face incident to the twin halfedge.
      // If the multiplicity is known and is even, we stay with the same
      // halfedge.
      if ((ip_mult % 2) == 1)
        left_he = right_he->twin();
      else if (ip_mult != 0)
        left_he = right_he;
      else
        left_he = invalid_he;
    }
    else
    {
      left_he = invalid_he;
    }
  }

  // We are not done with the zone-computation process yet:
  return (false);
}

//-----------------------------------------------------------------------------
// Compute the zone of an overlapping subcurve overlap_cv of cv and the
// curve currently associated with intersect_he.
//
template<class Arrangement, class ZoneVisitor>
bool Arrangement_zone_2<Arrangement,ZoneVisitor>::_zone_in_overlap ()
{
  // Check if the right end of overlap_cv is bounded. If so, compute its
  // right endpoint.
  const Boundary_type  cv_inf_x = 
    traits->boundary_in_x_2_object() (overlap_cv, MAX_END);
  const Boundary_type  cv_inf_y =
    traits->boundary_in_y_2_object() (overlap_cv, MAX_END);
  const bool           cv_has_right_pt = (cv_inf_x == NO_BOUNDARY && 
                                          cv_inf_y == NO_BOUNDARY);
  Point_2              cv_right_pt;

  if (cv_has_right_pt)
    cv_right_pt = traits->construct_max_vertex_2_object() (overlap_cv);

  // Get right end-vertex of the overlapping halfedge intersect_he. Also make
  // sure that the overlapping halfedge is always directed to the right.
  Vertex_handle   he_right_v;

  if (intersect_he->direction() == SMALLER)
  {
    he_right_v = intersect_he->target();
  }
  else
  {
    he_right_v = intersect_he->source();
    intersect_he = intersect_he->twin();
  }

  // Compare the two right endpoints. Note that overlap_cv cannot extend to
  // the right longer than the halfedge it overlaps. Thus, if the curve is
  // not bounded, the right vertex of intersect_he must lie at infinity as
  // well.
  if (! cv_has_right_pt)
  {
    CGAL_assertion (he_right_v->boundary_in_x() == cv_inf_x &&
                    he_right_v->boundary_in_y() == cv_inf_y);

    right_v = he_right_v;
  }
  else
  {
    Comparison_result      res = arr_access.compare_xy (cv_right_pt,
                                                        he_right_v);

    CGAL_assertion (res != LARGER);
    
    if (res == EQUAL)
    {
      // The overlap is with the entire halfedge. In this case we set the
      // right end-vertex of the overlapping zone.
      right_v = he_right_v;
    }
    else
    {
      // In this case intersect_he overlaps just a portion of prev_he.
      // The right end-vertex of the overlapping zone is not known.
      right_v = invalid_v;
    }
  }

  // Store the curve currently associated with the overlapping halfedge.
  const X_monotone_curve_2  *p_orig_curve = &(intersect_he->curve());

  // Notify the visitor on the overlapping zone.
  Visitor_result  visitor_res = visitor->found_overlap (overlap_cv,
                                                        intersect_he,
                                                        left_v, right_v);

  // If the visitor has indicated we should halt the process, or it the right
  // endpoint of the overlapping curve is the right endpoint of cv then we are
  // done (or both extend to infinity).
  if (visitor_res.second ||
      (cv_has_right_pt && has_right_pt &&
       traits->equal_2_object() (cv_right_pt, right_pt)) ||
      (! cv_has_right_pt && ! has_right_pt))
  {
    return (true);
  }

  // Erase the original curve from the intersection map, so we will have to
  // recompute intersections with it in the future.
  inter_map.erase (p_orig_curve);

  // Mark that we have dealt with the overlap.
  found_overlap = false;

  // Split cv at right endpoint of the overlapping curve.
  traits->split_2_object() (cv,
                            cv_right_pt,
                            sub_cv1, sub_cv2);

  // Set cv to be the remaining portion.
  has_left_pt = true;
  left_pt = cv_right_pt;
  cv = sub_cv2;

  // Move to the remaining portion of the curve, whose left endpoint is the
  // same as the right endpoint of the overlapping curve. Note that we check
  // if the visitor has inserted the subcurve (in which case it should return
  // a handle to the resulting halfedge).
  Halfedge_handle  updated_he = visitor_res.first;

  if (updated_he != invalid_he)
  {
    // In this case, left_pt should be associated with the target vertex of
    // the updated halfedge.
    CGAL_assertion (traits->equal_2_object() (left_pt,
                                              updated_he->target()->point()));
 
    left_v = updated_he->target();
  }
  else
  {
    left_v = right_v;
  }

  left_he = invalid_he;

  // We are not done with the zone-computation process yet:
  return (false);
}

CGAL_END_NAMESPACE

#endif