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
|
var t = db.geo_s2overlappingpolys
t.drop()
t.ensureIndex( { geo : "2dsphere" } );
var minError = 0.8e-13;
var canonPoly = {type: "Polygon",
coordinates: [
[[-1.0, -1.0], [1.0, -1.0], [1.0, 1.0], [-1.0, 1.0], [-1.0, -1.0]]
]};
t.insert({geo: canonPoly});
// Test 1: If a poly completely encloses the canonPoly, we expect the canonPoly
// to be returned for both $within and $geoIntersect
var outerPoly = {type: "Polygon",
coordinates: [
[[-2.0, -2.0], [2.0, -2.0], [2.0, 2.0], [-2.0, 2.0], [-2.0, -2.0]]
]};
var result = t.find({geo: {$within: {$geometry: outerPoly}}});
assert.eq(result.count(), 1);
result = t.find({geo: {$geoIntersects: {$geometry: outerPoly}}});
assert.eq(result.count(), 1);
// Test 2: If a poly that covers half of the canonPoly, we expect that it should
// geoIntersect, but should not be within.
var partialPoly = {type: "Polygon",
coordinates: [
[[-2.0, -2.0], [2.0, -2.0], [2.0, 0.0], [-2.0, 0.0], [-2.0, -2.0]]
]};
//Should not be within
result = t.find({geo: {$within: {$geometry: partialPoly}}});
assert.eq(result.count(), 0);
//This should however count as a geoIntersect
result = t.find({geo: {$geoIntersects: {$geometry: partialPoly}}});
assert.eq(result.count(), 1);
// Test 3: Polygons that intersect at a point or an edge have undefined
// behaviour in s2 The s2 library we're using appears to have
// the following behaviour.
// Case (a): Polygons that intersect at one point (not a vertex).
// behaviour: geoIntersects.
var sharedPointPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [0.0, -1.0], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: sharedPointPoly}}});
assert.eq(result.count(), 1);
// Case (b): Polygons that intersect at one point (a vertex).
// behaviour: not geoIntersect
var sharedVertexPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [1.0, -1.0], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: sharedVertexPoly}}});
assert.eq(result.count(), 0);
// Case (c): Polygons that intesersect at one point that is very close to a
// vertex should have the same behaviour as Case (b).
var almostSharedVertexPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [1.0 - minError, -1.0], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: almostSharedVertexPoly}}});
assert.eq(result.count(), 0);
// Case (d): Polygons that intesersect at one point that is not quite as close
// to a vertex should behave as though it were not a vertex, and should
// geoIntersect
var notCloseEnoughSharedVertexPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [1.0 - (10 * minError), -1.0], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: notCloseEnoughSharedVertexPoly}}});
assert.eq(result.count(), 1);
// Case (e): Polygons that come very close to having a point intersection
// on a non-vertex coordinate should intersect.
var almostSharedPointPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [0.0, (-1.0 - minError)], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: almostSharedPointPoly}}});
assert.eq(result.count(), 1);
// Case (f): If we increase the error a little, it should no longer act
// as though it's intersecting.
// NOTE: I think this error bound seems odd. Going to 0.000152297 will break this test.
// I've confirmed there is an error bound, but it's a lot larger than we experienced above.
var errorBound = 0.000152298
var notCloseEnoughSharedPointPoly = {type: "Polygon",
coordinates: [
[[0.0, -2.0], [0.0, -1.0 - errorBound], [1.0, -2.0], [0.0, -2.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: notCloseEnoughSharedPointPoly}}});
assert.eq(result.count(), 0);
/* Test 3: Importantly, polygons with shared edges have undefined intersection
* under s2. Therefore these test serve more to make sure nothing changes than
* to confirm an expected behaviour.
*/
// Case 1: A polygon who shares an edge with another polygon, where the searching
// polygon's edge is fully covered by the canon polygon's edge.
// Result: No intersection.
var fullyCoveredEdgePoly = {type: "Polygon",
coordinates: [
[[-2.0, -0.5], [-1.0, -0.5], [-1.0, 0.5], [-2.0, 0.5], [-2.0, -0.5]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: fullyCoveredEdgePoly}}});
assert.eq(result.count(), 0);
// Case 2: A polygon who shares an edge with another polygon, where the searching
// polygon's edge fully covers the canon polygon's edge.
// Result: Intersection.
var coveringEdgePoly = {type: "Polygon",
coordinates: [
[[-2.0, -1.5], [-1.0, -1.5], [-1.0, 1.5], [-2.0, 1.5], [-2.0, -1.5]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: coveringEdgePoly}}});
assert.eq(result.count(), 1);
// Case 2a: same as Case 2, except pulled slightly away from the polygon.
// Result: Intersection.
// NOTE: Scales of errors?
var closebyCoveringEdgePoly = {type: "Polygon",
coordinates: [
[[-2.0, -1.5], [-1.0 - (minError / 1000), -1.5], [-1.0 - (minError / 1000), 1.5], [-2.0, 1.5], [-2.0, -1.5]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: closebyCoveringEdgePoly}}});
assert.eq(result.count(), 1);
// Case 2b: same as Case 4, except pulled slightly away from the polygon, so that it's not intersecting.
// Result: No Intersection.
// NOTE: Scales of errors?
var notCloseEnoughCoveringEdgePoly = {type: "Polygon",
coordinates: [
[[-2.0, -1.5], [-1.0 - (minError / 100), -1.5], [-1.0 - (minError / 100), 1.5], [-2.0, 1.5], [-2.0, -1.5]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: notCloseEnoughCoveringEdgePoly}}});
assert.eq(result.count(), 0);
// Case 3: A polygon who shares an edge with another polygon, where the searching
// polygon's edge partially covers by the canon polygon's edge.
// Result: No intersection.
var partiallyCoveringEdgePoly = {type: "Polygon",
coordinates: [
[[-2.0, -1.5], [-1.0, -1.5], [-1.0, 0.5], [-2.0, 0.5], [-2.0, -1.5]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: partiallyCoveringEdgePoly}}});
assert.eq(result.count(), 0);
//Polygons that intersect at three non-co-linear points should geoIntersect
var sharedPointsPoly = {type: "Polygon",
coordinates: [
[[0.0, -3.0], [0.0, -1.0], [2.0, -2.0], [1.0, 0.0], [2.0, 2.0], [0.0, 1.0], [0.0, 3.0], [3.0, 3.0], [3.0, -3.0], [0.0, -3.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: sharedPointsPoly}}});
assert.eq(result.count(), 1);
//If a polygon contains a hole, and another polygon is within that hole, it should not be within or intersect.
var bigHolePoly = {type: "Polygon",
coordinates: [
[[-3.0, -3.0], [3.0, -3.0], [3.0, 3.0], [-3.0, 3.0], [-3.0, -3.0]],
[[-2.0, -2.0], [2.0, -2.0], [2.0, 2.0], [-2.0, 2.0], [-2.0, -2.0]]
]};
result = t.find({geo: {$within: {$geometry: bigHolePoly}}});
assert.eq(result.count(), 0);
result = t.find({geo: {$geoIntersects: {$geometry: bigHolePoly}}});
assert.eq(result.count(), 0);
// If a polygon has a hole, and another polygon is contained partially by that hole, it should be an intersection
// but not a within.
var internalOverlapPoly = {type: "Polygon",
coordinates: [
[[-3.0, -3.0], [3.0, -3.0], [3.0, 3.0], [-3.0, 3.0], [-3.0, -3.0]],
[[-2.0, 0.0], [2.0, 0.0], [2.0, 2.0], [-2.0, 2.0], [-2.0, 0.0]]
]};
result = t.find({geo: {$geoIntersects: {$geometry: internalOverlapPoly}}});
assert.eq(result.count(), 1);
result = t.find({geo: {$within: {$geometry: internalOverlapPoly}}});
assert.eq(result.count(), 0);
|
