arrangement_zone_2_functions.h

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

  CGAL_exactness_assertion (traits->compare_y_at_x_2_object()
                            (cv_left_pt, query_he->curve()) == EQUAL);

  // Check whether the given halfedge is directed to the right.
  const bool               query_he_directed_right = 
                                   (query_he->direction() == SMALLER);

  // Check whether the curve lies above of below the edge immediately to
  // the right of its left endpoint.
  const Comparison_result  pos_res =
    traits->compare_y_at_x_right_2_object() (cv_ins, query_he->curve(),
                                             cv_left_pt);

  if (pos_res == SMALLER)
  {
    // If cv below the curve associated with query_he, the relevant halfedge
    // is the one directed from right to left.
    if (query_he_directed_right)
      return (query_he->twin());
    else
      return (query_he);
  }
  else if (pos_res == LARGER)
  {
    // If cv below the curve associated with hh, the relevant halfedge
    // is the one directed from left to right.
    if (query_he_directed_right)
      return (query_he);
    else
      return (query_he->twin());
  }

  // The two curves are equal to the right of the left endpoint, so we have
  // an overlap.
  found_overlap = true;
  intersect_he = query_he;

  return (query_he);
}

//-----------------------------------------------------------------------------
// Direct the halfedge for the location of the given subcurve around a split
// point that occurs in the interior of a given edge, when the subcurve lies
// to the left of the split point.
//
template<class Arrangement, class ZoneVisitor>
typename Arrangement_zone_2<Arrangement,ZoneVisitor>::Halfedge_handle
Arrangement_zone_2<Arrangement,ZoneVisitor>::_direct_intersecting_edge_to_left
    (const X_monotone_curve_2& cv_ins,
     Halfedge_handle query_he)
{
  // Make sure that the right endpoint of cv_ins lies on query_he.
  CGAL_exactness_assertion (traits->compare_y_at_x_2_object()
                            (traits->construct_max_vertex_2_object() (cv_ins),
                             query_he->curve()) == EQUAL);

  // Check whether the given halfedge is directed to the right.
  const bool               query_he_directed_right =
                                   (query_he->direction() == SMALLER);

  // Check whether the curve lies above of below the edge (we use the curve
  // position predicate, as we know they cruves do not overlap and intersect
  // only at the split point).
  Comparison_result        pos_res =
      traits->compare_y_position_2_object() (cv_ins, query_he->curve());

  if (pos_res == EQUAL)
  {
    // This can happen only when both endpoints of cv_ins lie on query_he,
    // for example (the ^-shaped polyline is associated with query_he and
    // the horizontal segment is cv_ins):
    //
    //      /\        .
    //     /  \       .
    //    +----+      .
    //   /      \     .
    //
    // In this case, we got a wrong result from compare_y_position(), as we
    // abused this predicate (since the two curves are not supposed to
    // intersect), so we now simply have to compare the two curves to the right
    // of cv_ins' left endpoint.
    pos_res = traits->compare_y_at_x_right_2_object()
                  (cv_ins, query_he->curve(),
		   traits->construct_min_vertex_2_object() (cv_ins));
  }

  if (pos_res == SMALLER)
  {
    // If cv_ins lies below the curve associated with query_he, we should
    // take the haldedge directed from right to left, so if query_he is
    // directed to the right, we return it twin.
    if (query_he_directed_right)
      return (query_he->twin());
    else
      return (query_he);
  }
  else
  {
    CGAL_assertion (pos_res != EQUAL);

    // If cv_ins lies above the curve associated with query_he, we should
    // take the haldedge directed from left to right, so if query_he is
    // directed to the left, we return it twin.
    if (! query_he_directed_right)
      return (query_he->twin());
    else
      return (query_he);
  }
}

//-----------------------------------------------------------------------------
// Get the next intersection of cv with the given halfedge.
//
template<class Arrangement, class ZoneVisitor>
CGAL::Object
Arrangement_zone_2<Arrangement,ZoneVisitor>::_compute_next_intersection
    (Halfedge_handle he,
     bool skip_first_point)
{
  // Get a pointer to the curve associated with the halfedge.
  const X_monotone_curve_2  *p_curve = &(he->curve());

  // Try to locate the intersections with this curve in the intersections map.
  Intersect_map_iterator    iter = inter_map.find (p_curve);
  const Intersect_point_2  *ip;
  const X_monotone_curve_2 *icv;
  bool                      valid_intersection;

  if (iter != inter_map.end())
  {
    // The intersections with the curve have already been computed.
    // Retrieve the intersections list from the map.
    Intersect_list&          inter_list = iter->second;

    if (inter_list.empty())
      return CGAL::Object();

    // Locate the first intersection that lies to the right of left_pt
    // (if the left point exists).
    while (! inter_list.empty())
    {
      // Compare that current object with left_pt (if exists).
      ip = object_cast<Intersect_point_2> (&(inter_list.front()));

      if (! has_left_pt)
      {
        // The left end is unbounded, so all intersections are valid, as
        // they lie to its right.
        valid_intersection = true;
      }
      else if (ip != NULL)
      {
        // We have a simple intersection point - make sure it lies to the
        // right of left_pt.
        valid_intersection =
          (traits->compare_xy_2_object() (ip->first, left_pt) == LARGER);
      }
      else
      {
        // We have an overlapping subcurve.
	icv = object_cast<X_monotone_curve_2> (&(inter_list.front()));
	CGAL_assertion (icv != NULL);

        if (traits->boundary_in_x_2_object() (*icv, MIN_END) == NO_BOUNDARY &&
            traits->boundary_in_y_2_object() (*icv, MIN_END) == NO_BOUNDARY)
        {
          // The curve has a valid left point - make sure it lies to the
          // right of left_pt.
          valid_intersection = (traits->compare_xy_2_object()
                                (traits->construct_min_vertex_2_object()(*icv),
                                 left_pt) != SMALLER);
        }
        else
        {
          // In this case the overlap is not valid.
          valid_intersection = false;
        }
      }

      if (valid_intersection)
        // Found an intersection to left_pt's right.
        return (inter_list.front());

      // Discard the current intersection, which lies to left_pt's left.
      inter_list.pop_front();
    }

    // If we reached here, the list of intersections is empty:
    return CGAL::Object();
  }

  // The intersections with the curve have not been computed yet, so we
  // have to compute them now. Note that the first curve we intersect is
  // always the subcurve associated with the given halfegde and the second
  // curve is the one we insert. Even though the order seems unimportant, we
  // exploit this fact in some of the traits classes in order to optimize
  // computations.
  Intersect_list           inter_list;
  bool                     is_first = true;

  traits->intersect_2_object() (he->curve(), cv,
                                std::back_inserter(inter_list));

  // Discard all intersection lying to the left of left_pt (if exists).
  while (! inter_list.empty())
  {
    // Compare that current object with left_pt (if exists).
    ip = object_cast<Intersect_point_2> (&(inter_list.front()));

    if (ip != NULL)
    {
      // We have a simple intersection point - if we don't have to skip it,
      // make sure it lies to the right of left_pt (if left_pt does not
      // exist, all points lie to it right).
      if (is_first && skip_first_point)
        valid_intersection = false;
      else if (! has_left_pt)
        valid_intersection = true;
      else
        valid_intersection =
          (traits->compare_xy_2_object() (ip->first, left_pt) == LARGER);
    }
    else if (! has_left_pt)
    {
      // The left end is unbounded, so all overlapping curves are valid, as
      // they lie to its right.
      valid_intersection = true;
    }
    else
    {
      // We have an overlapping subcurve.
      icv = object_cast<X_monotone_curve_2> (&(inter_list.front()));
      CGAL_assertion (icv != NULL);
      
      if (traits->boundary_in_x_2_object() (*icv, MIN_END) == NO_BOUNDARY &&
          traits->boundary_in_y_2_object() (*icv, MIN_END) == NO_BOUNDARY)
      {
        // The curve has a valid left point - make sure it lies to the
        // right of left_pt.
        valid_intersection = (traits->compare_xy_2_object()
                              (traits->construct_min_vertex_2_object()(*icv),
                               left_pt) != SMALLER);
      }
      else
      {
        // In this case the overlap is not valid.
        valid_intersection = false;
      }
    }
    is_first = false;

    if (valid_intersection)
      // Found an intersection to left_pt's right.
      break;

    // Discard the current intersection, which lies to left_pt's left.
    inter_list.pop_front();
  }

  // Insert the list of valid intersections into the map.
  inter_map[p_curve] = inter_list;

  // Return the first intersection object computed (may be empty).
  if (inter_list.empty())
    return CGAL::Object();
  else
    return (inter_list.front());
}

//-----------------------------------------------------------------------------
// Remove the next intersection of cv with the given halfedge from the map.
//
template<class Arrangement, class ZoneVisitor>
void Arrangement_zone_2<Arrangement,ZoneVisitor>::_remove_next_intersection
    (Halfedge_handle he)
{
  // Get a pointer to the curve associated with the halfedge.
  const X_monotone_curve_2  *p_curve = &(he->curve());

  // Locate the intersections with this curve in the intersections map.
  Intersect_map_iterator     iter = inter_map.find (p_curve);

  CGAL_assertion (iter != inter_map.end());
  CGAL_assertion (! iter->second.empty());

  // Remove the first object in the list of intersections.
  iter->second.pop_front();
  return;
}

//-----------------------------------------------------------------------------
// Compute the (lexicographically) leftmost intersection of the query
// curve with the boundary of a given face in the arrangement.
//
template<class Arrangement, class ZoneVisitor>
void Arrangement_zone_2<Arrangement,ZoneVisitor>::
    _leftmost_intersection_with_face_boundary (Face_handle face,
                                               bool on_boundary)
{
  // Mark that we have not found any intersection (or overlap) yet.
  found_intersect = false;
  found_overlap = false;
  found_iso_vert = false;

  // Go over the outer boundary of the face (if one exists), and try to
  // locate intersections of cv with the edges along the boundary.
  typename Traits_adaptor_2::Compare_xy_2            compare_xy =
                                      traits->compare_xy_2_object();
  typename Traits_adaptor_2::Is_in_x_range_2         is_in_x_range =
                                      traits->is_in_x_range_2_object();
  typename Traits_adaptor_2::Construct_min_vertex_2  min_vertex =
                                      traits->construct_min_vertex_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2        compare_y_at_x =
                                      traits->compare_y_at_x_2_object();

  typename Arrangement_2::Ccb_halfedge_circulator  he_first;
  typename Arrangement_2::Ccb_halfedge_circulator  he_curr;

  CGAL::Object                 iobj;
  const Intersect_point_2     *int_p;
  const X_monotone_curve_2    *icv;
  Point_2                      ip;
  bool                         left_equals_curr_endpoint;

  // Get circulators for the outer boundary of the face.
  he_first = face->outer_ccb();
  he_curr = he_first;
  
  do
  {
    // If this edge is fictitious, skip it.
    if (he_curr->is_fictitious())
    {
      ++he_curr;
      continue;
    }
    
    // If we have already found an intersection with the twin halfedge,
    // we do not have to compute intersections with the current halfedge.
    if (found_intersect && intersect_he == he_curr->twin())
    {
      ++he_curr;
      continue;
    }
    
    // If we already have an intersection point, compare it to the
    // endpoints of the curve associated with the current halfedge,
    //  in order to filter unnecessary intersection computations.
    if (found_intersect &&
        ((he_curr->direction() == SMALLER &&
          arr_access.compare_xy (intersect_p, he_curr->source()) == SMALLER) ||
         (he_curr->direction() == LARGER &&
          arr_access.compare_xy (intersect_p, he_curr->target()) == SMALLER)))