arr_naive_point_location_functions.h

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

        if (y_res == curve_above_under)
          closest_edge = eit;
      }
    }

    if (in_x_range && res == EQUAL &&
        ! eit->is_fictitious() && is_vertical(eit->curve()))
    {
      // Check if the query point is one of the end-vertices of the vertical
      // edge.
      Comparison_result  res1 = arr_access.compare_xy (p, eit->source());
      Comparison_result  res2 = arr_access.compare_xy (p, eit->target());

      if (! ((res1 == EQUAL && res2 == curve_above_under) ||
             (res1 == curve_above_under && res2 == EQUAL)))
      {
        // The vertical ray overlaps an existing vertical edge containing p.
        // In this case simply return this edge.
        closest_edge = eit;
        return (CGAL::make_object (closest_edge));
      }
    }

    // Move to the next edge.
    ++eit;
  }

  // If we found a fictitious edge, return it now.
  CGAL_assertion (found);

  if (closest_edge->is_fictitious())
    return (CGAL::make_object (closest_edge));

  // If one of the closest edge's end vertices has the same x-coordinate
  // as the query point, return this vertex.
  if (! is_vertical (closest_edge->curve()))
  {
    if (! closest_edge->source()->is_at_infinity() &&
        traits->compare_x_2_object() (closest_edge->source()->point(),
                                      p) == EQUAL)
    {
      return (CGAL::make_object (closest_edge->source()));
    }
    else if (! closest_edge->target()->is_at_infinity() &&
             traits->compare_x_2_object() (closest_edge->target()->point(),
                                           p) == EQUAL)
    {
      return (CGAL::make_object (closest_edge->target()));
    }
  }
  else
  {
    CGAL_assertion_code(
      Comparison_result  res1 = arr_access.compare_xy (p,
                                                       closest_edge->source());
      Comparison_result  res2 = arr_access.compare_xy (p,
                                                       closest_edge->target());
      );

    CGAL_assertion (res1 == res2);
    CGAL_assertion (res1 = point_above_under);

    if (closest_edge->direction() == point_above_under)
      return (CGAL::make_object (closest_edge->source()));
    else
      return (CGAL::make_object (closest_edge->target()));
  }

  // Otherwise, return the closest edge.
  return (CGAL::make_object (closest_edge));
}

//-----------------------------------------------------------------------------
// Locate the arrangement feature which a vertical ray emanating from the
// given point hits, considering isolated vertices.
//
template <class Arrangement>
Object Arr_naive_point_location<Arrangement>::_vertical_ray_shoot
    (const Point_2& p,
     bool shoot_up) const
{
  // Locate the arrangement feature which a vertical ray emanating from the
  // given point hits, when not considering the isolated vertices.
  // This feature may not exist, or be either a vertex of a halfedge.
  Object                 obj = _base_vertical_ray_shoot (p, shoot_up);
  bool                   found_vertex;
  Vertex_const_handle    closest_v;
  Halfedge_const_handle  closest_he;

  const Vertex_const_handle *p_vh = object_cast<Vertex_const_handle> (&obj);
  
  if (p_vh != NULL)
  {
    found_vertex = true;
    closest_v = *p_vh;
  }
  else
  {
    found_vertex = false;
    closest_he = object_cast<Halfedge_const_handle> (obj);
  }

  // Set the result for comparison according to the ray direction.
  const Comparison_result point_above_under = (shoot_up ? SMALLER : LARGER);

  // Go over all isolated vertices in the arrangement.
  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();

  typename Arrangement::Vertex_const_iterator  vit;
  Vertex_const_handle                          vh;

  for (vit = p_arr->vertices_begin(); vit != p_arr->vertices_end(); ++vit)
  {
    vh = vit;
    if (! vh->is_isolated())
      continue;

    // 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, vh->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, vh->point()) != point_above_under)
      continue;

    // Check if the isolated vertex is closer to p than the current closest
    // object.
    if ((found_vertex &&
         compare_xy (vh->point(), closest_v->point()) == point_above_under) ||
        (! found_vertex &&
         (closest_he->is_fictitious() ||
          compare_y_at_x (vh->point(), closest_he->curve()) == 
                                                         point_above_under)))
    {
      found_vertex = true;
      closest_v = vh;
    }
  }

  // Set back the result according to its type.
  if (found_vertex)
    return (CGAL::make_object (closest_v));
  else if (! closest_he->is_fictitious())
    return (CGAL::make_object (closest_he));
  
  // If we found a fictitious edge, we have to return a handle to its
  // incident unbounded face.
  if ((shoot_up && closest_he->direction() == SMALLER) ||
      (!shoot_up && closest_he->direction() == LARGER))
    closest_he = closest_he->twin();

  return (CGAL::make_object (closest_he->face()));
}

//-----------------------------------------------------------------------------
// Find the first halfedge with a given source vertex, when going clockwise
// from "6 o'clock" around this vertex.
//
template <class Arrangement>
typename Arr_naive_point_location<Arrangement>::Halfedge_const_handle
Arr_naive_point_location<Arrangement>::_first_around_vertex
    (Vertex_const_handle v) 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();

  const 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() &&
           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() &&
           compare_y_at_x_right (curr->curve(),
                                 top_right->curve(), 
                                 v->point()) == LARGER))
      {
        top_right = curr;
      }
    }

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

  // The first halfedge we encounter is the lowest to the left, but if there
  // is no edge to the left, we first encounter the topmost halfedge to the 
  // right. Note that as the halfedge we located has v as its target, we now
  // have to return its twin.
  if (lowest_left != invalid_handle)
    return (lowest_left->twin());
  else
    return (top_right->twin());
}

CGAL_END_NAMESPACE

#endif