forked from dgraph-io/dgraph
/
s2.go
123 lines (105 loc) · 3.57 KB
/
s2.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
/*
* Copyright 2016 Dgraph Labs, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package geo
import (
"github.com/golang/geo/s2"
)
// Added functionality missing in s2
// Make s2.Loop implement s2.Region
type loopRegion struct {
*s2.Loop
}
func (l loopRegion) ContainsCell(c s2.Cell) bool {
// Quick check if the cell is in the bounding box
if !l.RectBound().ContainsCell(c) {
return false
}
// Quick check to see if the first vertex is in the loop.
if !l.ContainsPoint(c.Vertex(0)) {
return false
}
// At this stage one vertex is in the loop, now we check that the edges of the cell do not cross
// the loop.
return !l.edgesCross(c)
}
// returns true if the edges of the cell cross the edges of the loop
func (l loopRegion) edgesCross(c s2.Cell) bool {
return l.edgesCrossPoints([]s2.Point{c.Vertex(0), c.Vertex(1), c.Vertex(2), c.Vertex(3)})
}
func (l loopRegion) edgesCrossPoints(pts []s2.Point) bool {
n := len(pts)
for i := 0; i < n; i++ {
crosser := s2.NewChainEdgeCrosser(pts[i], pts[(i+1)%n], pts[0])
for i := 1; i <= l.NumEdges(); i++ { // add vertex 0 twice as it is a closed loop
if crosser.EdgeOrVertexChainCrossing(l.Vertex(i)) {
return true
}
}
}
return false
}
func (l loopRegion) IntersectsCell(c s2.Cell) bool {
// Quick check if the cell intersects the bounding box
if !l.RectBound().IntersectsCell(c) {
return false
}
// Quick check to see if the first vertex is in the loop.
if l.ContainsPoint(c.Vertex(0)) {
return true
}
// At this stage the one vertex is outside the loop. We check if any of the edges of the cell
// cross the loop.
if l.edgesCross(c) {
return true
}
// At this stage we know that there is one point of the cell outside the loop and the boundaries
// do not interesect. The only way for the cell to intersect with the loop is if it contains the
// the loop. We test this by checking if an arbitrary vertex of the loop is inside the cell.
if c.RectBound().Contains(l.RectBound()) {
return c.ContainsPoint(l.Vertex(0))
}
return false
}
func (l loopRegion) intersects(loop *s2.Loop) bool {
// Quick check if the bounding boxes intersect
if !l.RectBound().Intersects(loop.RectBound()) {
return false
}
// Quick check to see if the first vertex is in the loop.
if l.ContainsPoint(loop.Vertex(0)) {
return true
}
// At this stage the one vertex is outside the loop. We check if any of the edges of the cell
// cross the loop.
if l.edgesCrossPoints(loop.Vertices()) {
return true
}
// At this stage we know that there is one point of the loop is outside us and the boundaries do
// not interesect. The only way for the loops to intersect is if it contains us. We test this
// by checking if an arbitrary vertex is inside the loop.
if loop.RectBound().Contains(l.RectBound()) {
return loop.ContainsPoint(l.Vertex(0))
}
return false
}
// Intersects returns true if the two loops intersect.
func Intersects(l1 *s2.Loop, l2 *s2.Loop) bool {
if l2.NumEdges() > l1.NumEdges() {
// Use the larger loop for edge indexing.
return loopRegion{l2}.intersects(l1)
}
return loopRegion{l1}.intersects(l2)
}