arr_walk_along_line_pl_functions.h

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

            {
              // The query point lies below the target vertex of the closest
              // halfedge: In this case we have to locate the first halfedge
              // we encounter when going around this target vertex from
              // "6 o'clock" (when shooting up) or from "12 o'clock" (when
              // shooting down).
              closest_he = _first_around_vertex (closest_he->target(),
                                                 shoot_up);
            }


            CGAL_assertion (old_closest_he != closest_he);
            face = closest_he->twin()->face();
          }

        } while (! is_in_face);

        // We have located a face in the hole that contains the query point.
        // This will break the internal loop on holes, and we shall proceed
        // for another iteration of the external loop, trying to locate p in
        // one of the holes of this new face.
        found_containing_hole = true;
      }
    } // End loop on the current face's holes.

  } while (found_containing_hole);

  // Check whether one of the isolated vertices in the face containing p lies
  // above (or below) it, closer than the closest halfdge we have located.
  typename Traits_adaptor_2::Compare_x_2          compare_x =
                                             traits->compare_x_2_object();
  typename Traits_adaptor_2::Compare_xy_2         compare_xy =
                                             traits->compare_xy_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2     compare_y_at_x =
                                             traits->compare_y_at_x_2_object();

  const Comparison_result point_above_under = (shoot_up ? SMALLER : LARGER);

  Isolated_vertex_const_iterator     iso_verts_it;
  Vertex_const_handle                closest_iso_v;
  const Vertex_const_handle          invalid_v;
  const Halfedge_const_handle        invalid_he;

  for (iso_verts_it = face->isolated_vertices_begin();
       iso_verts_it != face->isolated_vertices_end(); ++iso_verts_it)
  {
    // The current isolated vertex should have the same x-coordinate as the
    // query point in order to be below or above it.
    if (compare_x (p, iso_verts_it->point()) != EQUAL)
      continue;

    // Make sure the isolated vertex is above the query point (if we shoot up)
    // or below it (if we shoot down).
    if (compare_xy (p, iso_verts_it->point()) != point_above_under)
      continue;

    // Check if the current isolated vertex lies closer to the query point than
    // the closest feature so far.
    if (closest_iso_v == invalid_v)
    {
      // Compare the current isolated vertex with the closest halfedge.
      if (closest_he == invalid_he ||
          closest_he->is_fictitious() ||
          compare_y_at_x (iso_verts_it->point(),
                          closest_he->curve()) == point_above_under)
      {
        closest_iso_v = iso_verts_it;
      }
    }
    else if (compare_xy (iso_verts_it->point(),
                         closest_iso_v->point()) == point_above_under)
    {
      closest_iso_v = iso_verts_it;
    }
  }

  if (closest_iso_v != invalid_v)
  {
    // The first object we encounter when we shoot a vertical ray from p is
    // an isolated vertex:
    return (CGAL::make_object (closest_iso_v));
  }

  // If we reached here, closest_he is the closest edge from above (below)
  // the query point.
  if (closest_he->is_fictitious())
  {
    // If we have a fictitious edge, the ray we shoot is completely contained
    // in an unbounded face. This face is incident to closest_he:
    if ((shoot_up && closest_he->direction() == SMALLER) ||
        (!shoot_up && closest_he->direction() == LARGER))
      closest_he = closest_he->twin();

    Face_const_handle  uf = closest_he->face();

    CGAL_assertion (! uf->is_fictitious());
    return (CGAL::make_object (uf));
  }

  // Check if one of closest_he's end vertices lies directly above (below) the
  // query point, and if so, return this vertex.
  if (! is_vertical (closest_he->curve()))
  {
    if (arr_access.compare_x (p, closest_he->source()) == EQUAL)
      return (CGAL::make_object (closest_he->source()));


    if (arr_access.compare_x (p, closest_he->target()) == EQUAL)
      return (CGAL::make_object (closest_he->target()));
  }
  else
  {
    // The entire vertical segment is above (below) the query point: Return the
    // endpoint closest to it.
    const bool    is_directed_up = (closest_he->direction() == SMALLER);

    if ((shoot_up && is_directed_up) ||
        (! shoot_up && ! is_directed_up))
    {
      return (CGAL::make_object (closest_he->source()));
    }
    else
    {
      return (CGAL::make_object (closest_he->target()));
    }
  }

  // The interior of the edge is closest to the query point:
  return (CGAL::make_object (closest_he));
}

//-----------------------------------------------------------------------------
// Find the closest feature to p (and lying above or below it) along the
// boundary of the given connected component.
//
template <class Arrangement>
bool Arr_walk_along_line_point_location<Arrangement>::
_is_in_connected_component (const Point_2& p,
                            Ccb_halfedge_const_circulator circ,
                            bool shoot_up,
                            bool inclusive,
                            Halfedge_const_handle& closest_he,
                            bool& is_on_edge,
                            bool& closest_to_target) const
{
  // As far as we know, we are not on an edge.
  is_on_edge = false;
  closest_to_target = false;
  
  // Set the results for comparison acording to the ray direction.
  const Comparison_result point_above_under = (shoot_up ? SMALLER : LARGER);
  const Comparison_result curve_above_under = (shoot_up ? LARGER : SMALLER);

  // Keep a counter of the number of halfedges of the connected component's
  // boundary that intersect an upward (or downward, if shoot_up is false)
  // vertical ray emanating from the query point p (except for some degenerate
  // cases that are explained below).
  unsigned int              n_ray_intersections = 0;

  typename Traits_adaptor_2::Equal_2              equal =
                                            traits->equal_2_object();
  typename Traits_adaptor_2::Is_vertical_2        is_vertical =
                                            traits->is_vertical_2_object();
  typename Traits_adaptor_2::Compare_y_position_2 compare_y_position =
                                       traits->compare_y_position_2_object();
  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();

  // Start from the first non-vertical segment in the connected component.
  Arrangement&                      arr = const_cast<Arrangement&>(*p_arr);
  const Arr_accessor<Arrangement>   arr_access (arr);
  const Halfedge_const_handle       invalid_he;
  Ccb_halfedge_const_circulator     first = circ;
  bool                              found_non_vertical = false;

  do
  {
    // In case of a fictitious edge, check whether it is horizontal; otherwise
    // skip it.
    if (first->is_fictitious())
    {
      if (first->source()->boundary_in_y() != NO_BOUNDARY &&
          first->target()->boundary_in_y() != NO_BOUNDARY)
      {
        found_non_vertical = true;
        break;
      }
      else
      {
        ++first;
        continue;
      }
    }

    // Stop if we found a non-vertical curve.
    if (! is_vertical (first->curve()))
    {
      found_non_vertical = true;
      break;
    }

    if (inclusive)
    {
      // Check if the current vertical curve contains the query point.
      if (arr_access.compare_x (p, first->source()) == EQUAL &&
          arr_access.compare_y_at_x (p, first) == EQUAL)
      {
        closest_he = first;
        is_on_edge = true;
        return (true);
      }
    }
    else
    {
      // Check if the current vertical curve contains the query point in its
      // x-range.
      if (arr_access.compare_x (p, first->source()) == EQUAL)
      {
        // Check if the current vertical curve contains the query point in its
        // iterior.
        Comparison_result  res1 = arr_access.compare_xy (p, first->source());
        Comparison_result  res2 = arr_access.compare_xy (p, first->target());
        
        if (res1 != res2)
        {
          if (! ((res1 == EQUAL && res2 == curve_above_under) ||
                 (res1 == curve_above_under && res2 == EQUAL)))
          {
            closest_he = first;
            is_on_edge = true;
            return (true);
          }
        }
        else if (res1 == point_above_under)
        {
          // Check if the vertical segment is the closest to the query point so
          // far.
          if (closest_he == invalid_he ||
              (closest_he != first->twin() &&
               ((! first->source()->is_at_infinity() &&
                 arr_access.compare_y_at_x
                   (first->source()->point(),
                    closest_he) == point_above_under) ||
                (! first->target()->is_at_infinity() &&
                 arr_access.compare_y_at_x
                   (first->target()->point(),
                    closest_he) == point_above_under))))
          {
            closest_he = first;
            closest_to_target = (first->direction() == curve_above_under);
          }
        }
      }
    }

    // Move to the next curve.
    ++first;

  } while (first != circ);

  if (! found_non_vertical)
  {
    // In this case the entire component is comprised of vertical segments,
    // so it has an empty interior and p cannot lie inside it.
    return (false);
  }

  // Go over all curves of the boundary, starting from the non-vertical curve
  // we have located, and count those which are above p.
  Ccb_halfedge_const_circulator  curr = first;
  Comparison_result   source_res, target_res;
  Comparison_result   res;
  Comparison_result   y_res;
  bool                closest_in_ccb = (closest_he != invalid_he &&
                                        closest_he->face() == circ->face());

  source_res = arr_access.compare_x (p, curr->source());
  do
  {
    // Ignore the current edge if p is not in its x-range.
    target_res = arr_access.compare_x (p, curr->target());

    if (source_res == target_res && source_res != EQUAL)
    {
      ++curr;
      source_res = target_res;
      continue;
    }

    // Check whether p lies above or below the current edge.
    res = arr_access.compare_y_at_x (p, curr);

    if (res == EQUAL)
    {
      // The current edge contains the query point. If the seach is inclusive
      // we return the edge. Otherwise, we return it only if it is vertical,
      // and contains p in its interior.
      if (inclusive)
      {