-
Notifications
You must be signed in to change notification settings - Fork 84
/
polygon.go
188 lines (171 loc) · 4.17 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
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
package floatgeom
import (
"github.com/oakmound/oak/v4/alg"
)
// A Polygon2 is a series of points in 2D space.
type Polygon2 struct {
// Bounding is a cached bounding box calculated from the input points
// It is exported for convenience, but should be modified with care
Bounding Rect2
// The component points of the polygon. If modified, Bounding should
// be updated with NewBoundingRect2.
Points []Point2
rectangular bool
}
// NewPolygon2 is a helper method to construct a valid polygon. Polygons
// cannot contain less than 3 points.
func NewPolygon2(p1, p2, p3 Point2, pn ...Point2) Polygon2 {
pts := append([]Point2{p1, p2, p3}, pn...)
bounding := NewBoundingRect2(pts...)
return Polygon2{
Bounding: bounding,
Points: pts,
rectangular: isRectangular(pts...),
}
}
// Contains returns whether or not the current Polygon contains the passed in Point.
// If it is known that the polygon is convex, ConvexContains should be preferred for
// performance.
func (pg Polygon2) Contains(x, y float64) (contains bool) {
if !pg.Bounding.Contains(Point2{x, y}) {
return
}
j := len(pg.Points) - 1
for i := 0; i < len(pg.Points); i++ {
tp1 := pg.Points[i]
tp2 := pg.Points[j]
if (tp1.Y() > y) != (tp2.Y() > y) { // Three comparisons
if x < (tp2.X()-tp1.X())*(y-tp1.Y())/(tp2.Y()-tp1.Y())+tp1.X() { // One Comparison, Four add/sub, Two mult/div
contains = !contains
}
}
j = i
}
return
}
// ConvexContains returns whether the given point is contained by the input polygon.
// It assumes the polygon is convex.
func (pg Polygon2) ConvexContains(x, y float64) bool {
p := Point2{x, y}
if !pg.Bounding.Contains(p) {
return false
}
prev := 0
for i := 0; i < len(pg.Points); i++ {
tp1 := pg.Points[i]
tp2 := pg.Points[(i+1)%len(pg.Points)]
tp3 := tp2.Sub(tp1)
tp4 := p.Sub(tp1)
cur := getSide(tp3, tp4)
if cur == 0 {
return false
} else if prev == 0 {
} else if prev != cur {
return false
}
prev = cur
}
return true
}
// TODO: rename this to its real math name, export it
func getSide(a, b Point2) int {
x := a.X()*b.Y() - a.Y()*b.X()
if x == 0 {
return 0
} else if x < 1 {
return -1
} else {
return 1
}
}
// OverlappingRectCollides returns whether a Rect2 intersects or is contained by this Polygon.
// This method differs from RectCollides because it assumes that we already know r overlaps with pg.Bounding.
// It is only valid for convex polygons.
func (pg Polygon2) OverlappingRectCollides(r Rect2) bool {
if pg.rectangular {
return true
}
diags := [][2]Point2{
{
{r.Min.X(), r.Max.Y()},
{r.Max.X(), r.Min.Y()},
}, {
r.Min,
r.Max,
},
}
last := pg.Points[len(pg.Points)-1]
for i := 0; i < len(pg.Points); i++ {
next := pg.Points[i]
if r.Contains(next) {
return true
}
// Checking line segment from last to next
for _, diag := range diags {
if orient(diag[0], diag[1], last) != orient(diag[0], diag[1], next) &&
orient(next, last, diag[0]) != orient(next, last, diag[1]) {
return true
}
}
last = next
}
return false
}
// RectCollides returns whether a Rect2 intersects or is contained by this Polygon.
// It is only valid for convex polygons.
func (pg Polygon2) RectCollides(r Rect2) bool {
x := float64(r.Min.X())
y := float64(r.Min.Y())
x2 := float64(r.Max.X())
y2 := float64(r.Max.Y())
dx := pg.Bounding.Min.X()
dy := pg.Bounding.Min.Y()
dx2 := pg.Bounding.Max.X()
dy2 := pg.Bounding.Max.Y()
overlapX := false
if x > dx {
if x < dx2 {
overlapX = true
}
} else {
if dx < x2 {
overlapX = true
}
}
if !overlapX {
return false
}
if y > dy {
if y < dy2 {
return pg.OverlappingRectCollides(r)
}
} else {
if dy < y2 {
return pg.OverlappingRectCollides(r)
}
}
return false
}
func isRectangular(pts ...Point2) bool {
last := pts[len(pts)-1]
for _, pt := range pts {
// The last point needs to share an x or y value with this point
if !alg.F64eq(pt.X(), last.X()) && !alg.F64eq(pt.Y(), last.Y()) {
return false
}
last = pt
}
return true
}
func orient(p1, p2, p3 Point2) int8 {
val := (p2.Y()-p1.Y())*(p3.X()-p2.X()) -
(p2.X()-p1.X())*(p3.Y()-p2.Y())
switch {
case val < 0:
return 2
case val > 0:
return 1
default:
return 0
}
}