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 typenameVerticalRayShooting::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 vertexstd::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 edgestd::cout << "hit an edge: " << (*e)->curve() << std::endl;else if (f = boost::get<Face_const_handle>(&obj)) {    // we hit nothingCGAL_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;
}