-
Notifications
You must be signed in to change notification settings - Fork 3.7k
/
geodist.go
348 lines (320 loc) · 12.7 KB
/
geodist.go
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
// Copyright 2020 The Cockroach Authors.
//
// Use of this software is governed by the Business Source License
// included in the file licenses/BSL.txt.
//
// As of the Change Date specified in that file, in accordance with
// the Business Source License, use of this software will be governed
// by the Apache License, Version 2.0, included in the file
// licenses/APL.txt.
// Package geodist finds distances between two geospatial shapes.
package geodist
import "github.com/cockroachdb/errors"
// Point is an interface that represents a geospatial Point.
type Point interface {
IsShape()
IsPoint()
}
// Edge is a struct that represents a connection between two points.
type Edge struct {
V0, V1 Point
}
// LineString is an interface that represents a geospatial LineString.
type LineString interface {
Edge(i int) Edge
NumEdges() int
Vertex(i int) Point
NumVertexes() int
IsShape()
IsLineString()
}
// LinearRing is an interface that represents a geospatial LinearRing.
type LinearRing interface {
Edge(i int) Edge
NumEdges() int
Vertex(i int) Point
NumVertexes() int
IsShape()
IsLinearRing()
}
// shapeWithEdges represents any shape that contains edges.
type shapeWithEdges interface {
Edge(i int) Edge
NumEdges() int
}
// Polygon is an interface that represents a geospatial Polygon.
type Polygon interface {
LinearRing(i int) LinearRing
NumLinearRings() int
IsShape()
IsPolygon()
}
// Shape is an interface that represents any Geospatial shape.
type Shape interface {
IsShape()
}
var _ Shape = (Point)(nil)
var _ Shape = (LineString)(nil)
var _ Shape = (LinearRing)(nil)
var _ Shape = (Polygon)(nil)
// DistanceUpdater is a provided hook that has a series of functions that allows
// the caller to maintain the distance value desired.
type DistanceUpdater interface {
// Update updates the distance based on two provided points,
// returning if the function should return early.
Update(a Point, b Point) bool
// OnIntersects is called when two shapes intersects.
OnIntersects() bool
// Distance returns the distance to return so far.
Distance() float64
// IsMaxDistance returns whether the updater is looking for maximum distance.
IsMaxDistance() bool
}
// EdgeCrosser is a provided hook that calculates whether edges intersect.
type EdgeCrosser interface {
// ChainCrossing assumes there is an edge to compare against, and the previous
// point `p0` is the start of the next edge. It will then check whether (p0, p)
// intersects with the edge. When complete, point p will become p0.
// Desired usage examples:
// crosser := NewEdgeCrosser(edge.V0, edge.V1, startingP0)
// intersects := crosser.ChainCrossing(p1)
// intersects |= crosser.ChainCrossing(p2) ....
ChainCrossing(p Point) bool
}
// DistanceCalculator contains calculations which allow ShapeDistance to calculate
// the distance between two shapes.
type DistanceCalculator interface {
// DistanceUpdater returns the DistanceUpdater for the current set of calculations.
DistanceUpdater() DistanceUpdater
// NewEdgeCrosser returns a new EdgeCrosser with the given edge initialized to be
// the edge to compare against, and the start point to be the start of the first
// edge to compare against.
NewEdgeCrosser(edge Edge, startPoint Point) EdgeCrosser
// PointInLinearRing returns whether the point is inside the given linearRing.
PointInLinearRing(point Point, linearRing LinearRing) bool
// ClosestPointToEdge returns the closest point to the infinite line denoted by
// the edge, and a bool on whether this point lies on the edge segment.
ClosestPointToEdge(edge Edge, point Point) (Point, bool)
}
// ShapeDistance returns the distance between two given shapes.
// Distance is defined by the DistanceUpdater provided by the interface.
// It returns whether the function above should return early.
func ShapeDistance(c DistanceCalculator, a Shape, b Shape) (bool, error) {
switch a := a.(type) {
case Point:
switch b := b.(type) {
case Point:
return c.DistanceUpdater().Update(a, b), nil
case LineString:
return onPointToLineString(c, a, b), nil
case Polygon:
return onPointToPolygon(c, a, b), nil
default:
return false, errors.Newf("unknown shape: %T", b)
}
case LineString:
switch b := b.(type) {
case Point:
return onPointToLineString(c, b, a), nil
case LineString:
return onShapeEdgesToShapeEdges(c, a, b), nil
case Polygon:
return onLineStringToPolygon(c, a, b), nil
default:
return false, errors.Newf("unknown shape: %T", b)
}
case Polygon:
switch b := b.(type) {
case Point:
return onPointToPolygon(c, b, a), nil
case LineString:
return onLineStringToPolygon(c, b, a), nil
case Polygon:
return onPolygonToPolygon(c, a, b), nil
default:
return false, errors.Newf("unknown shape: %T", b)
}
}
return false, errors.Newf("unknown shape: %T", a)
}
// onPointToEdgesExceptFirstEdgeStart updates the distance using the edges between a point and a shape.
// It will only check the ends of the edges, and assumes the check against .Edge(0).V0 is not required.
func onPointToEdgesExceptFirstEdgeStart(c DistanceCalculator, a Point, b shapeWithEdges) bool {
for edgeIdx := 0; edgeIdx < b.NumEdges(); edgeIdx++ {
edge := b.Edge(edgeIdx)
// Check against all V1 of every edge.
if c.DistanceUpdater().Update(a, edge.V1) {
return true
}
if !c.DistanceUpdater().IsMaxDistance() {
// Also project the point to the infinite line of the edge, and compare if the closestPoint
// lies on the edge.
if closestPoint, ok := c.ClosestPointToEdge(edge, a); ok {
if c.DistanceUpdater().Update(a, closestPoint) {
return true
}
}
}
}
return false
}
// onPointToLineString updates the distance between a point and a polyline.
// Returns true if the calling function should early exit.
func onPointToLineString(c DistanceCalculator, a Point, b LineString) bool {
// Compare the first point, to avoid checking each V0 in the chain afterwards.
if c.DistanceUpdater().Update(a, b.Vertex(0)) {
return true
}
return onPointToEdgesExceptFirstEdgeStart(c, a, b)
}
// onPointToPolygon updates the distance between a point and a polygon.
// Returns true if the calling function should early exit.
func onPointToPolygon(c DistanceCalculator, a Point, b Polygon) bool {
// If the exterior ring does not contain the point, we just need to calculate the distance to
// the exterior ring.
// Also, if we are just calculating max distance, we only want the distance to the exterior.
if c.DistanceUpdater().IsMaxDistance() || !c.PointInLinearRing(a, b.LinearRing(0)) {
return onPointToEdgesExceptFirstEdgeStart(c, a, b.LinearRing(0))
}
// At this point it may be inside a hole.
// If it is in a hole, return the distance to the hole.
for ringIdx := 1; ringIdx < b.NumLinearRings(); ringIdx++ {
ring := b.LinearRing(ringIdx)
if c.PointInLinearRing(a, ring) {
return onPointToEdgesExceptFirstEdgeStart(c, a, ring)
}
}
// Otherwise, we are inside the polygon.
return c.DistanceUpdater().OnIntersects()
}
// onShapeEdgesToShapeEdges updates the distance between two shapes by
// only looking at the edges.
// Returns true if the calling function should early exit.
func onShapeEdgesToShapeEdges(c DistanceCalculator, a shapeWithEdges, b shapeWithEdges) bool {
for aEdgeIdx := 0; aEdgeIdx < a.NumEdges(); aEdgeIdx++ {
aEdge := a.Edge(aEdgeIdx)
crosser := c.NewEdgeCrosser(aEdge, b.Edge(0).V0)
for bEdgeIdx := 0; bEdgeIdx < b.NumEdges(); bEdgeIdx++ {
bEdge := b.Edge(bEdgeIdx)
if !c.DistanceUpdater().IsMaxDistance() {
// If the edges cross, the distance is 0.
if crosser.ChainCrossing(bEdge.V1) {
return c.DistanceUpdater().OnIntersects()
}
}
// Compare each vertex against the edge of the other.
for _, toCheck := range []struct {
vertex Point
edge Edge
}{
{aEdge.V0, bEdge},
{aEdge.V1, bEdge},
{bEdge.V0, aEdge},
{bEdge.V1, aEdge},
} {
// Check the vertex against the ends of the edges.
if c.DistanceUpdater().Update(toCheck.vertex, toCheck.edge.V0) ||
c.DistanceUpdater().Update(toCheck.vertex, toCheck.edge.V1) {
return true
}
if !c.DistanceUpdater().IsMaxDistance() {
// Also check the projection of the vertex onto the edge.
if closestPoint, ok := c.ClosestPointToEdge(toCheck.edge, toCheck.vertex); ok {
if c.DistanceUpdater().Update(toCheck.vertex, closestPoint) {
return true
}
}
}
}
}
}
return false
}
// onLineStringToPolygon updates the distance between a polyline and a polygon.
// Returns true if the calling function should early exit.
func onLineStringToPolygon(c DistanceCalculator, a LineString, b Polygon) bool {
// If we know at least one point is outside the exterior ring, then there are two cases:
// * the line is always outside the exterior ring. We only need to compare the line
// against the exterior ring.
// * the line intersects with the exterior ring.
// In both these cases, we can defer to the edge to edge comparison between the line
// and the exterior ring.
// We use the first point of the linestring for this check.
// If we are looking for max distance, we only need to check against the outer ring anyway.
if c.DistanceUpdater().IsMaxDistance() || !c.PointInLinearRing(a.Vertex(0), b.LinearRing(0)) {
return onShapeEdgesToShapeEdges(c, a, b.LinearRing(0))
}
// Now we are guaranteed that there is at least one point inside the exterior ring.
//
// For a polygon with no holes, the fact that there is a point inside the exterior
// ring would imply that the distance is zero.
//
// However, when there are holes, it is possible that the distance is non-zero if
// polyline A is completely contained inside a hole. We iterate over the holes and
// compute the distance between the hole and polyline A.
// * If polyline A is within the given distance, we can immediately return.
// * If polyline A does not intersect the hole but there is at least one point inside
// the hole, must be inside that hole and so the distance of this polyline to this hole
// is the distance of this polyline to this polygon.
for ringIdx := 1; ringIdx < b.NumLinearRings(); ringIdx++ {
hole := b.LinearRing(ringIdx)
if onShapeEdgesToShapeEdges(c, a, hole) {
return true
}
for pointIdx := 0; pointIdx < a.NumVertexes(); pointIdx++ {
if c.PointInLinearRing(a.Vertex(pointIdx), hole) {
return false
}
}
}
// This means we are inside the exterior ring, and no points are inside a hole.
// This means the point is inside the polygon.
return c.DistanceUpdater().OnIntersects()
}
// onPolygonToPolygon updates the distance between two polygons.
// Returns true if the calling function should early exit.
func onPolygonToPolygon(c DistanceCalculator, a Polygon, b Polygon) bool {
aFirstPoint := a.LinearRing(0).Vertex(0)
bFirstPoint := b.LinearRing(0).Vertex(0)
// If there is at least one point on the the exterior ring of B that is outside the exterior ring
// of A, then we have one of these two cases:
// * The exterior rings of A and B intersect. The distance can always be found by comparing
// the exterior rings.
// * The exterior rings of A and B never meet. This distance can always be found
// by only comparing the exterior rings.
// If we find the point is inside the exterior ring, A could contain B, so this reasoning
// does not apply.
//
// The same reasoning applies if there is at least one point on the exterior ring of A
// that is outside the exterior ring of B.
//
// As such, we only need to compare the exterior rings if we detect this.
//
// If we are only looking at the max distance, we only want to compare exteriors.
if c.DistanceUpdater().IsMaxDistance() ||
(!c.PointInLinearRing(bFirstPoint, a.LinearRing(0)) && !c.PointInLinearRing(aFirstPoint, b.LinearRing(0))) {
return onShapeEdgesToShapeEdges(c, a.LinearRing(0), b.LinearRing(0))
}
// If any point of polygon A is inside a hole of polygon B, then either:
// * A is inside the hole and the closest point can be found by comparing A's outer
// linearRing and the hole in B, or
// * A intersects this hole and the distance is zero, which can also be found by comparing
// A's outer linearRing and the hole in B.
// In this case, we only need to compare the holes of B to contain a single point A.
for ringIdx := 1; ringIdx < b.NumLinearRings(); ringIdx++ {
bHole := b.LinearRing(ringIdx)
if c.PointInLinearRing(aFirstPoint, bHole) {
return onShapeEdgesToShapeEdges(c, a.LinearRing(0), bHole)
}
}
// Do the same check for the polygons the other way around.
for ringIdx := 1; ringIdx < a.NumLinearRings(); ringIdx++ {
aHole := a.LinearRing(ringIdx)
if c.PointInLinearRing(bFirstPoint, aHole) {
return onShapeEdgesToShapeEdges(c, b.LinearRing(0), aHole)
}
}
// Now we know either a point of the exterior ring A is definitely inside polygon B
// or vice versa. This is an intersection.
return c.DistanceUpdater().OnIntersects()
}