arr_walk_along_line_pl_functions.h

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

        closest_he = curr;
        is_on_edge = true;
        return (true);
      }
      else
      {
        if (! curr->is_fictitious() &&
            is_vertical (curr->curve()) &&
            (curr->source()->is_at_infinity() ||
             ! equal (curr->source()->point(), p)) &&
            (curr->target()->is_at_infinity() ||
             ! equal (curr->target()->point(), p)))
        {
          closest_he = curr;
          is_on_edge = true;
          return (true);
        }
      }
    }

    // If the point is above the current edge (or below it, if we shoot down),
    // move to the next edge.
    if (res != point_above_under)
    {
      ++curr;
      source_res = target_res;
      continue;
    }

    // Note that we do not have count intersections (actually these are
    // overlaps) of the vertical ray we shoot with vertical segments along
    // the boundary.
    if (curr->is_fictitious() || 
        ! is_vertical (curr->curve()))
    {
      // The current curve is not vertical. Check the query point is in the
      // semi-open x-range (source, target] of this curve and lies below it.
      if (source_res != EQUAL)
      {
        if (closest_he == invalid_he ||
            (! closest_in_ccb && closest_he->twin() == curr))
        {
          // If we have no closests halfedge, we have just found one.
          // Alternatively, if the closest halfedge is not in our CCB, but it
          // the twin of our current halfedge, we can take our halfedge to be
          // the closest one.
          closest_he = curr;
          closest_in_ccb = true;
          closest_to_target = (target_res == EQUAL);
        }
        else if (! (closest_he->twin() == curr))
        {
          // The current curve is not the twin of the closest curve.
          // Compare with the vertically closest curve so far and detemine the
          // curve closest to p. We first check the case that the two curves
          // have a common endpoint (note that the two curves do not intersect
          // in their interiors). Observe that if such a common vertex exists,
          // it is certainly not a vertex at infinity, therefore it is
          // associated with a valid point.
          if (! closest_he->is_fictitious() && ! curr->is_fictitious() &&
              ((closest_he->source() == curr->source() &&
                closest_he->direction() == curr->direction()) ||
               (closest_he->source() == curr->target() &&
                closest_he->direction() != curr->direction())))
          {
            if (closest_he->direction() == SMALLER)
            {
              // Both curves extend to the right from a common point.
              y_res = compare_y_at_x_right (closest_he->curve(),
                                            curr->curve(), 
                                            closest_he->source()->point());
            }
            else
            {
              // Both curves extend to the left from a common point.
              y_res = compare_y_at_x_left (closest_he->curve(),
                                           curr->curve(), 
                                           closest_he->source()->point());
            }
          }
          else if (! closest_he->is_fictitious() && ! curr->is_fictitious() &&
                   ((closest_he->target() == curr->source() &&
                     closest_he->direction() != curr->direction()) ||
                    (closest_he->target() == curr->target() &&
                     closest_he->direction() == curr->direction())))
          {
            if (closest_he->direction() == SMALLER)
            {
              // Both curves extend to the left from a common point.
              y_res = compare_y_at_x_left (closest_he->curve(),
                                           curr->curve(), 
                                           closest_he->target()->point());
            }
            else
            {
              // Both curves extend to the right from a common point.
              y_res = compare_y_at_x_right (closest_he->curve(),
                                            curr->curve(), 
                                            closest_he->target()->point());
            }
          }
          else
          {
            // In case the two curves do not have a common endpoint, but
            // overlap in their x-range (both contain p), just compare their
            // positions. Note that in this case one of the edges may be
            // fictitious, so we preform the comparsion symbolically in this
            // case.
            if (closest_he->is_fictitious())
              y_res = curve_above_under;
            else if (curr->is_fictitious())
              y_res = point_above_under;
            else
              y_res = compare_y_position (closest_he->curve(),
                                          curr->curve());
          }

          // If the current curve is closer to p than the closest curve found
          // so far, assign its halfedge as the closest one.
          if (y_res == curve_above_under)
          {
            closest_he = curr;
            closest_in_ccb = true;
            closest_to_target = (target_res == EQUAL);
          }
        }

        // In the degenerate case where p lies below the target vertex of
        // the current halfedge, we have to be a bit careful:
        if (target_res == EQUAL)
        {
          // Locate the next halfedge along the boundary that does not
          // contain a vertical segment.
          Halfedge_const_handle  next_non_vert = curr;

          do
          {
            next_non_vert = next_non_vert->next();

            CGAL_assertion (next_non_vert != curr);

          } while ((! next_non_vert->is_fictitious() &&
                    is_vertical (next_non_vert->curve())) ||
                   (next_non_vert->is_fictitious() &&
                    next_non_vert->source()->boundary_in_x() != 
                    next_non_vert->target()->boundary_in_x()));

          // In case the source of the current curve and the target of
          // the next non-vertical curve lie on opposite sides of the
          // ray we shoot from p (case (a)), we have to count an
          // intersection. Otherwise, we have a "tangency" with the ray
          // (case (b)) and it is not necessary to count it.
          //
          //            +--------+              +                 .
          //            |   next                 \ next           .
          //            |                         \               .
          //            +                          +              .
          //           /                          /               .
          //     curr /                     curr /                .
          //         /                          /                 .
          //        +  (.)p                    +  (.)p            .
          //
          //          (a)                        (b)
          //
          target_res = arr_access.compare_x (p, next_non_vert->target());

          CGAL_assertion (source_res != EQUAL && target_res != EQUAL);

          if (source_res != target_res)
            n_ray_intersections++;
        }
        else
        {
          // In this case p lies under the interior of the current x-montone
          // curve, so the vertical ray we shoot intersects it exactly once.
          n_ray_intersections++;
        }
      }
    }
    else
    {
      // Assign an edge associated with a vertical curve as the closest edge
      // only if the vertical curve has an endpoint closer to p than the
      // closest edge so far.
      if (closest_he == invalid_he ||
          (! closest_in_ccb && closest_he->twin() == curr) ||
          (! curr->source()->is_at_infinity() &&
           arr_access.compare_y_at_x (curr->source()->point(),
                                      closest_he) == point_above_under) ||
          (! curr->target()->is_at_infinity() &&
           arr_access.compare_y_at_x (curr->target()->point(),
                                      closest_he) == point_above_under))
      {
        closest_he = curr;
        closest_in_ccb = true;
        closest_to_target = (curr->direction() == curve_above_under);
      }
    }

    // Proceed to the next halfedge along the component boundary.
    ++curr;
    source_res = target_res;

  } while (curr != first);

  // The query point lies inside the connected components if and only if the
  // ray we shoot from it intersects the boundary an odd number of times.
  return ((n_ray_intersections % 2) != 0);
}

//-----------------------------------------------------------------------------
// Find the first halfedge around a given target vertex, when going clockwise
// from "6 o'clock" around this vertex (when shooting up) or starting from
// "12 o'clock (when shooting down).
//
template <class Arrangement>
typename Arr_walk_along_line_point_location<Arrangement>::Halfedge_const_handle
Arr_walk_along_line_point_location<Arrangement>::
_first_around_vertex (Vertex_const_handle v,
                      bool shoot_up) const
{
  // Travrse the incident halfedges of the current vertex and locate the
  // lowest one to its left and the topmost to its right.
  typename Traits_adaptor_2::Compare_y_at_x_right_2 compare_y_at_x_right =
                                      traits->compare_y_at_x_right_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_left_2  compare_y_at_x_left =
                                      traits->compare_y_at_x_left_2_object();

  Halfedge_const_handle   invalid_handle;
  Halfedge_const_handle   lowest_left;
  Halfedge_const_handle   top_right;

  typename Arrangement::Halfedge_around_vertex_const_circulator first = 
    v->incident_halfedges();
  typename Arrangement::Halfedge_around_vertex_const_circulator curr = first;

  do 
  {
    // Check whether the current halfedge is defined to the left or to the
    // right of the given vertex.
    if (curr->direction() == SMALLER)
    {
      // The curve associated with the current halfedge is defined to the left
      // of v.
      if (lowest_left == invalid_handle ||
          (! curr->is_fictitious() &&
           (lowest_left->is_fictitious() ||
            compare_y_at_x_left (curr->curve(),
                                 lowest_left->curve(), 
                                 v->point()) == SMALLER)))
      {
        lowest_left = curr;
      }
    }
    else
    {
      // The curve associated with the current halfedge is defined to the right
      // of v.
      if (top_right == invalid_handle ||
          (! curr->is_fictitious() &&
           (top_right->is_fictitious() ||
            compare_y_at_x_right (curr->curve(),
                                  top_right->curve(), 
                                  v->point()) == LARGER)))
      {
        top_right = curr;
      }
    }

    curr++;
  } while (curr != first);

  if (shoot_up)
  {
    // As we start from "6 o'clock" in a clockwsie direction, the first
    // halfedge we encounter is the lowest to the left. However, if there
    // is no edge to the left, we first encounter the topmost halfedge to the
    // right.
    if (lowest_left != invalid_handle)
      return (lowest_left);
    else
      return (top_right);
  }
  else
  {
    // As we start from "12 o'clock" in a clockwsie direction, the first
    // halfedge we encounter is the topmost to the right. However, if there
    // is no edge to the right, we first encounter the lowest halfedge to the
    // left.
    if (top_right != invalid_handle)
      return (top_right);
    else
      return (lowest_left);
  }
}

CGAL_END_NAMESPACE

#endif