forked from golang/geo
/
polygon.go
132 lines (113 loc) · 4.6 KB
/
polygon.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
/*
Copyright 2015 Google Inc. All rights reserved.
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 s2
// Polygon represents a sequence of zero or more loops; recall that the
// interior of a loop is defined to be its left-hand side (see Loop).
//
// When the polygon is initialized, the given loops are automatically converted
// into a canonical form consisting of "shells" and "holes". Shells and holes
// are both oriented CCW, and are nested hierarchically. The loops are
// reordered to correspond to a preorder traversal of the nesting hierarchy.
//
// Polygons may represent any region of the sphere with a polygonal boundary,
// including the entire sphere (known as the "full" polygon). The full polygon
// consists of a single full loop (see Loop), whereas the empty polygon has no
// loops at all.
//
// Use FullPolygon() to construct a full polygon. The zero value of Polygon is
// treated as the empty polygon.
//
// Polygons have the following restrictions:
//
// - Loops may not cross, i.e. the boundary of a loop may not intersect
// both the interior and exterior of any other loop.
//
// - Loops may not share edges, i.e. if a loop contains an edge AB, then
// no other loop may contain AB or BA.
//
// - Loops may share vertices, however no vertex may appear twice in a
// single loop (see Loop).
//
// - No loop may be empty. The full loop may appear only in the full polygon.
type Polygon struct {
loops []*Loop
// index is a spatial index of all the polygon loops.
index ShapeIndex
// hasHoles tracks if this polygon has at least one hole.
hasHoles bool
// numVertices keeps the running total of all of the vertices of the contained loops.
numVertices int
// bound is a conservative bound on all points contained by this loop.
// If l.ContainsPoint(P), then l.bound.ContainsPoint(P).
bound Rect
// Since bound is not exact, it is possible that a loop A contains
// another loop B whose bounds are slightly larger. subregionBound
// has been expanded sufficiently to account for this error, i.e.
// if A.Contains(B), then A.subregionBound.Contains(B.bound).
subregionBound Rect
}
// PolygonFromLoops constructs a polygon from the given hierarchically nested
// loops. The polygon interior consists of the points contained by an odd
// number of loops. (Recall that a loop contains the set of points on its
// left-hand side.)
//
// This method figures out the loop nesting hierarchy and assigns every loop a
// depth. Shells have even depths, and holes have odd depths.
//
// NOTE: this function is NOT YET IMPLEMENTED for more than one loop and will
// panic if given a slice of length > 1.
func PolygonFromLoops(loops []*Loop) *Polygon {
if len(loops) > 1 {
panic("s2.PolygonFromLoops for multiple loops is not yet implemented")
}
return &Polygon{
loops: loops,
numVertices: len(loops[0].Vertices()), // TODO(roberts): Once multi-loop is supported, fix this.
bound: EmptyRect(),
subregionBound: EmptyRect(),
}
}
// FullPolygon returns a special "full" polygon.
func FullPolygon() *Polygon {
return &Polygon{
loops: []*Loop{
FullLoop(),
},
numVertices: len(FullLoop().Vertices()),
bound: FullRect(),
subregionBound: FullRect(),
}
}
// IsEmpty reports whether this is the special "empty" polygon (consisting of no loops).
func (p *Polygon) IsEmpty() bool {
return len(p.loops) == 0
}
// IsFull reports whether this is the special "full" polygon (consisting of a
// single loop that encompasses the entire sphere).
func (p *Polygon) IsFull() bool {
return len(p.loops) == 1 && p.loops[0].IsFull()
}
// Loops returns the loops in this polygon.
func (p *Polygon) Loops() []*Loop {
return p.loops
}
// CapBound returns a bounding spherical cap.
func (p *Polygon) CapBound() Cap { return p.bound.CapBound() }
// RectBound returns a bounding latitude-longitude rectangle.
func (p *Polygon) RectBound() Rect { return p.bound }
// ContainsCell reports whether the polygon contains the given cell.
// TODO
//func (p *Polygon) ContainsCell(c Cell) bool { ... }
// IntersectsCell reports whether the polygon intersects the given cell.
// TODO
//func (p *Polygon) IntersectsCell(c Cell) bool { ... }