S2 计算给定点到哪条边最近

Posted on | Post modified | In | Visitors

在 GIS 系统里，我们可能会遇到如下的场景，给定一个坐标点，计算其到哪条边最近。而生活中对应的实例是：根据你的 GPS 位置信号，找到离你最近的一条公路是哪个。

在 google s2 的库中，提供了如下类，用来进行该类型的空间索引：S2ClosestEdgeQuery。

首先我们将已有的 geospatial objects 存到一个 index 中，也就是对这些 objects 建立了一个空间索引，我们暂且称这个索引为 index。

之后我们给定一个查询目标，Target，从 index 里面查找到在 Target 周围，符合我们要求的 spatial objects，这就是 query 以后返回的 results。

下面看一段简单的查询代码，给定 Target 点，找到距离它最近的边是哪些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include "s2/s2closest_edge_query.h"

#include <memory>
#include <set>
#include <vector>

#include <gtest/gtest.h>
#include "s2/third_party/absl/memory/memory.h"
#include "s2/mutable_s2shape_index.h"
#include "s2/s1angle.h"
#include "s2/s2cap.h"
#include "s2/s2cell.h"
#include "s2/s2cell_id.h"
#include "s2/s2edge_distances.h"
#include "s2/s2loop.h"
#include "s2/s2metrics.h"
#include "s2/s2edge_vector_shape.h"
#include "s2/s2point_vector_shape.h"
#include "s2/s2polygon.h"
#include "s2/s2predicates.h"
#include "s2/s2testing.h"
#include "s2/s2text_format.h"

using absl::make_unique;
using s2textformat::MakeIndexOrDie;
using s2textformat::MakePointOrDie;
using s2textformat::MakePolygonOrDie;
using s2textformat::ParsePointsOrDie;
using std::fabs;
using std::make_pair;
using std::min;
using std::ostream;
using std::pair;
using std::unique_ptr;
using std::vector;

using absl::make_unique;
using s2textformat::MakeIndexOrDie;
using s2textformat::MakePointOrDie;
using s2textformat::MakePolygonOrDie;
using s2textformat::ParsePointsOrDie;
using std::fabs;
using std::make_pair;
using std::min;
using std::ostream;
using std::pair;
using std::unique_ptr;
using std::vector;
using std::numeric_limits;
using namespace std;
int main() {
  // Tests a target point in the interior of an indexed polygon.
  // (The index also includes a polyline loop with no interior.)
  // 这里定义了三条线段，(0,0)-(0,5) (5,5)-(5,0)，第三条由三个小段组成：(0,6)-(0,7)-(0,9)-(0,10)
  auto index = MakeIndexOrDie("# 0:0, 0:5 | 5:5, 5:0| 0:6, 0:7, 0:9, 0:10 #");
  S2ClosestEdgeQuery::Options options;
  // KNN 算法，设置 K = 2
  options.set_max_edges(2);
  S2ClosestEdgeQuery query(index.get(), options);
  // 设定查询的目标点
  S2ClosestEdgeQuery::PointTarget target(MakePointOrDie("2:12"));
  // 查找距离该点最近的两条线段
  auto results = query.FindClosestEdges(&target);

  // 最终返回结果，一定是小于等于 2
  cout << "should be 2:" << results.size() << endl;
  // 最近的 edge id 是哪个，也就是上面通过 MakeIndexOrDie 中的第几个 edge。这里应该是是 2，代表第三条线段
  cout << results[0].shape_id << endl;
  // 因为可能一条线段由多个小段组成，所以再定位到是哪个小段，这里是2，表示最后一小段 (0,9)-(0,10)
  cout << results[0].edge_id << endl;
  // 输出最近的距离值
  cout << results[0].distance << endl;
}

可以从下面的示例图中看出来：

当然，s2 的该类不仅仅只能计算点到哪条边最近，抽象一下它能够实现的功能为：

  1. 计算距离给定 Target（可以是 point，edge，或者复杂的 polygon）最近的 spatial objects （这些 object 也可以是 point, edge, polygon）是哪些。
  2. 给定一个范围 r，是否在距离 Target 为 r 的周围，有 spatial object 存在。

具体的例子可以到下面去查阅：
http://s2geometry.io/devguide/s2closestedgequery
https://github.com/google/s2geometry/blob/master/src/s2/s2closest_edge_query_test.cc

0%