CGAL::2D Arrangements-3

3.Arrangement查询

Arrangement里面最重要的查询操作是point-location，给定一个点，查找到包含这个点的Arrangement。通常情况下，point-location查询得到的结果是Arrangement的一个face，退化情况下会是一个edge，查一个重合的点。

3.1 point-Location查询

3.3 垂直射线扫描

另一个经常用到Arrangement的查找，是垂直射线扫描查找：给定一个查找点，哪些Arrangement单元会跟从这个点发射的垂直射线相交？一般情况下，可能这个射线交到一边edge，也有可能交到一个vertex，或者这个Arrangement单元不跟这个射线相交。

在前面章节讲到的point-location类，也是一个ArrangementVerticalRayShoot_2概念(concept)的一个model，所以他们全都有成员方法ray_shoot_up(q)和 ray_shoot_down(q)，这其中的Q是一个用来查询的point。

在头文件point_location_utils.h中有下面的辅助方法：

template <typename VerticalRayShooting>
void shoot_vertical_ray(const RayShoot& vrs,
                        const typename
                        VerticalRayShooting::Arrangement_2::Point_2& q)
{
  typedef VerticalRayShooting                           Vertical_ray_shooting;
  // Perform the point-location query.
  typename Vertical_ray_shooting::result_type obj = vrs.ray_shoot_up(q);
  // Print the result.
  typedef typename Vertical_ray_shooting::Arrangement_2 Arrangement_2;
  typedef typename Arrangement_2::Vertex_const_handle   Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle     Face_const_handle;
  const Vertex_const_handle* v;
  const Halfedge_const_handle* e;
  const Face_const_handle* f;
  std::cout << "Shooting up from (" << q << ") : ";
  if (v = boost::get<Vertex_const_handle>(&obj))         // we hit a vertex
    std::cout << "hit " << (((*v)->is_isolated()) ? "an isolated" : "a")
              << " vertex: " << (*v)->point() << std::endl;
  else if (e = boost::get<Halfedge_const_handle>(&obj))  // we hit an edge
    std::cout << "hit an edge: " << (*e)->curve() << std::endl;
  else if (f = boost::get<Face_const_handle>(&obj)) {    // we hit nothing
    CGAL_assertion((*f)->is_unbounded());
    std::cout << "hit nothing.\n";
  }
  else CGAL_error();
}

下面的程序段，使用了上面的函数模式，在一个Arrangement上执行垂直射线扫描查询：

// Answering vertical ray-shooting queries.
#include <CGAL/basic.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arr_trapezoid_ric_point_location.h>
#include "arr_inexact_construction_segments.h"
#include "point_location_utils.h"
typedef CGAL::Arr_walk_along_line_point_location<Arrangement> Walk_pl;
typedef CGAL::Arr_trapezoid_ric_point_location<Arrangement>   Trap_pl;
int main() {
  // Construct the arrangement.
  Arrangement arr;
  construct_segments_arr(arr);
  // Perform some vertical ray-shooting queries using the walk strategy.
  Walk_pl walk_pl(arr);
  shoot_vertical_ray(walk_pl, Point(1, 4));
  shoot_vertical_ray(walk_pl, Point(4, 3));
  shoot_vertical_ray(walk_pl, Point(6, 3));
  // Attach the trapezoid-RIC object to the arrangement and perform queries.
  Trap_pl trap_pl(arr);
  shoot_vertical_ray(trap_pl, Point(3, 2));
  shoot_vertical_ray(trap_pl, Point(5, 2));
  shoot_vertical_ray(trap_pl, Point(1, 0));
  return 0;
}