arrangement_zone_2_functions.h

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

    {
      // The current x-monotone curve lies entirely to the right of
      // ip_left, so its intersection with cv (if any) cannot lie to
      // the left of this point. We therefore do not need to compute
      // this intersection.
      ++he_curr;
      continue;
    }
    
    left_equals_curr_endpoint = false;
    if (on_boundary)
    {
      // Check if the left endpoint of the inserted curve (which is located
      // on the boundary of our face) equals one of the endpoints of the
      // current halfedge. If it equals the right endpoint of the current
      // halfedge, we can skip this edge, as there is no true overlap in
      // the x-range. Otherwise, we keep track of the fact that left_v is
      // the left end-vertex of the current halfedge.
      if (he_curr->target() == left_v)
      {
        left_equals_curr_endpoint = true;
        
        if (he_curr->direction() == SMALLER)
        {
          ++he_curr;
          continue;
        }
      }
      else if (he_curr->source() == left_v)
      {
        left_equals_curr_endpoint = true;
        
        if (he_curr->direction() == LARGER)
        {
          ++he_curr;
          continue;
        }
      }
    }
    
    // Check whether the two curves overlap in their x-range (in order
    // to avoid unnecessary intersection computations).
    if (! left_equals_curr_endpoint &&
        ((has_left_pt &&            
          ((he_curr->direction() == SMALLER &&
            arr_access.compare_xy (left_pt, he_curr->target()) != SMALLER) ||
           (he_curr->direction() == LARGER &&
            arr_access.compare_xy (left_pt, he_curr->source()) != SMALLER))) ||
         ! is_in_x_range (cv, he_curr->curve())))
    {
      // In case there is no overlap, the two x-monotone curves obviously
      // do not intersect.
      ++he_curr;
      continue;
    }

    // Compute the next intersection of cv and the current halfedge.
    iobj = _compute_next_intersection (he_curr,
                                       left_equals_curr_endpoint);
    
    if (! iobj.is_empty())
    {
      // We have found an intersection (either a simple point or an
      // overlapping x-monotone curve).
      int_p = object_cast<Intersect_point_2> (&iobj);
      if (int_p != NULL)
      {
        ip = int_p->first;
        
        // Found a simple intersection point. Check if it is the leftmost
        // intersection point so far.
        if (! found_intersect ||
            compare_xy (ip, intersect_p) == SMALLER)
        {
          // Store the leftmost intersection point and the halfedge handle.
          intersect_p = ip;
          ip_mult = int_p->second;
          intersect_he = he_curr;
          found_overlap = false;
        }
      }
      else
      {
        // We have located an overlapping curve. Assign ip as its left
        // endpoint.
        icv = object_cast<X_monotone_curve_2> (&iobj);
        CGAL_assertion (icv != NULL);
        
        ip = min_vertex (*icv);
        
        // Check if this endpoint it is the leftmost intersection point so
        // far.
        if (! found_intersect ||
            compare_xy (ip, intersect_p) == SMALLER)
        {
          // Store the leftmost intersection point and the halfedge handle.
          intersect_p = ip;
          ip_mult = 0;
          overlap_cv = *icv;
          intersect_he = he_curr;
          found_overlap = true;
        }
      }
      
      // Mark that we found an intersection.
      found_intersect = true;
    }
    
    // Move to the next edge along the outer boundary,
    ++he_curr;
    
  } while (he_curr != he_first);     // End loop on the outer CCB.

  // Go over the boundary of the holes inside the face (if there exist any),
  // and try to locate intersections of cv with the edges along the boundary
  // of each hole.
  typename Arrangement_2::Hole_iterator   holes_it;

  for (holes_it = face->holes_begin();
       holes_it != face->holes_end(); ++holes_it)
  {
    // Get circulators for the boundary of the current hole.
    he_first = *holes_it;
    he_curr = he_first;

    do
    {
      // 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)))
      {
        // The current x-monotone curve lies entirely to the right of
        // ip_left, so its intersection with cv (if any) cannot lie to
        // the left of this point. We therefore do not need to compute
        // this intersection.
        ++he_curr;
        continue;
      }

      left_equals_curr_endpoint = false;
      if (on_boundary)
      {
        // Check if the left endpoint of the inserted curve (which is located
        // on the boundary of our face) equals one of the endpoints of the
        // current halfedge. If it equals the right endpoint of the current
        // halfedge, we can skip this edge, as there is no true overlap in
        // the x-range. Otherwise, we keep track of the fact that left_v is
        // the left end-vertex of the current halfedge.
        if (he_curr->target() == left_v)
        {
          left_equals_curr_endpoint = true;

          if (he_curr->direction() == SMALLER)
          {
            ++he_curr;
            continue;
          }
        }
        else if (he_curr->source() == left_v)
        {
          left_equals_curr_endpoint = true;

          if (he_curr->direction() == LARGER)
          {
            ++he_curr;
            continue;
          }
        }
      }

      // Check whether the two curves overlap in their x-range (in order
      // to avoid unnecessary intersection computations).
      if (! left_equals_curr_endpoint &&
          ((has_left_pt &&            
            ((he_curr->direction() == SMALLER &&
              arr_access.compare_xy (left_pt,
                                     he_curr->target()) != SMALLER) ||
             (he_curr->direction() == LARGER &&
              arr_access.compare_xy (left_pt,
                                     he_curr->source()) != SMALLER))) ||
           ! is_in_x_range (cv, he_curr->curve())))
      {
        // In case there is no overlap, the two x-monotone curves obviously
        // do not intersect.
        ++he_curr;
        continue;
      }

      // Compute the next intersection of cv and the current halfedge.
      iobj = _compute_next_intersection (he_curr,
                                         left_equals_curr_endpoint);

      if (! iobj.is_empty())
      {
        // We have found an intersection (either a simple point or an
        // overlapping x-monotone curve).
	int_p = object_cast<Intersect_point_2> (&iobj);
        if (int_p != NULL)
        {
          ip = int_p->first;

          // Found a simple intersection point. Check if it is the leftmost
          // intersection point so far.
          if (! found_intersect ||
              compare_xy (ip, intersect_p) == SMALLER)
          {
            // Store the leftmost intersection point and the halfedge
            // handle.
            intersect_p = ip;
            ip_mult = int_p->second;
            intersect_he = he_curr;
            found_overlap = false;
          }
        }
        else
        {
          // We have located an overlapping curve. Assign ip as its left
          // endpoint.
	  icv = object_cast<X_monotone_curve_2> (&iobj);
	  CGAL_assertion (icv != NULL);

          ip = min_vertex (*icv);

          // Check if this endpoint it is the leftmost intersection point
          // so far.
          if (! found_intersect ||
              compare_xy (ip, intersect_p) == SMALLER)
          {
            // Store the leftmost intersection point and the halfedge
            // handle.
            intersect_p = ip;
            ip_mult = 0;
            overlap_cv = *icv;
            intersect_he = he_curr;
            found_overlap = true;
          }
        }

        // Mark that we found an intersection.
        found_intersect = true;
      }

      // Move to the next edge along the outer boundary,
      ++he_curr;

    } while (he_curr != he_first);

  } // End: traversal of the holes inside the face.

  // Go over the boundary of the isolated vertices inside the face (if there
  // exist any), and check whether an isolated vertex lies on the curve.
  typename Arrangement_2::Isolated_vertex_iterator   iso_verts_it;

  for (iso_verts_it = face->isolated_vertices_begin();
       iso_verts_it != face->isolated_vertices_end(); ++iso_verts_it)
  {
    // If the isolated vertex is not in the x-range of our curve, disregard it.
    if (! is_in_x_range (cv, iso_verts_it->point()))
      continue;

    // If we already have an intersection point, compare it to the current
    // isolated vertex, in order to filter unnecessary computations.
    if (found_intersect &&
        compare_xy (iso_verts_it->point(), intersect_p) == LARGER)
    {
      continue;
    }

    // In case the isolated vertex lies on the curve, update the intersection
    // point accordingly.
    if (compare_y_at_x (iso_verts_it->point(), cv) == EQUAL &&
        (! has_left_pt ||
         compare_xy (iso_verts_it->point(), left_pt) == LARGER))
    {
      intersect_v = iso_verts_it;
      intersect_p = intersect_v->point();
      ip_mult = 0;
      found_intersect = true;
      found_iso_vert = true;
    }

  } // End:: traversal of the isolated vertices inside the face.

  // Remove the next intersection associated with intersect_he, as we have
  // now reported it and do not want to encounter it again.
  if (found_intersect && !found_iso_vert)
    _remove_next_intersection (intersect_he);

  return;
}

//-----------------------------------------------------------------------------
// Compute the zone of an x-monotone curve in a given arrangement face.
// The left endpoint of the curve either lies in the face interior or on
// the boundary of the face.
//
template<class Arrangement, class ZoneVisitor>
bool Arrangement_zone_2<Arrangement,ZoneVisitor>::_zone_in_face
    (Face_handle face,
     bool on_boundary)
{
  CGAL_precondition ((! on_boundary &&
                      ((left_v == invalid_v && left_he == invalid_he) ||
                      left_v->is_isolated())) ||
                     (on_boundary && left_he != invalid_he));

  // Find the first intersection of the curve with the face boundary.
  _leftmost_intersection_with_face_boundary (face, on_boundary);

  if (! found_intersect)
  {
    // Notify the visitor that the entire curve lies within the given face,
    // such that its right endpoint is not incident to any arrangement feature.
    visitor->found_subcurve (cv,
                             face,
                             left_v, left_he,
                             invalid_v, invalid_he);

    // Inidicate that we are done with the zone-computation process.
    return (true);
  }

  // In this case found_intersect is true and intersect_he is the edge that
  // cv next intersects (or overlaps). If found_overlap is also true,
  // then overlap_cv is set and intersect_p is the left endpoint of the
  // overlapping subcurve. Otherwise, intersect_p is a simple intersection
  // point.
  // Alternatively, if found_iso_vert is true, then the next intersection point
  // intersect_p lies on the isolated vertex intersect_v.
  bool                  done = false;

  if (has_right_pt &&
      traits->equal_2_object() (intersect_p, right_pt))
  {
    // If the intersection point is cv's right endpoint, the interior of cv
    // does not intersect any existing halfedge. In this case, we only have
    // to insert cv to the arrangement and we are done.
    sub_cv1 = cv;