forked from paulmach/orb
-
Notifications
You must be signed in to change notification settings - Fork 0
/
polygon.go
78 lines (61 loc) · 1.67 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
package tilecover
import (
"sort"
"github.com/paulmach/orb"
"github.com/paulmach/orb/maptile"
)
// Ring creates a tile cover for the ring.
func Ring(r orb.Ring, z maptile.Zoom) maptile.Set {
if len(r) == 0 {
return make(maptile.Set)
}
return Polygon(orb.Polygon{r}, z)
}
// Polygon creates a tile cover for the polygon.
func Polygon(p orb.Polygon, z maptile.Zoom) maptile.Set {
set := make(maptile.Set)
polygon(set, p, z)
return set
}
// MultiPolygon creates a tile cover for the multi-polygon.
func MultiPolygon(mp orb.MultiPolygon, z maptile.Zoom) maptile.Set {
set := make(maptile.Set)
for _, p := range mp {
polygon(set, p, z)
}
return set
}
func polygon(set maptile.Set, p orb.Polygon, zoom maptile.Zoom) {
intersections := make([][2]uint32, 0)
for _, r := range p {
ring := line(set, orb.LineString(r), zoom, make([][2]uint32, 0))
pi := len(ring) - 2
for i := range ring {
pi = (pi + 1) % len(ring)
ni := (i + 1) % len(ring)
y := ring[i][1]
// add interesction if it's not local extremum or duplicate
if (y > ring[pi][1] || y > ring[ni][1]) && // not local minimum
(y < ring[pi][1] || y < ring[ni][1]) && // not local maximum
y != ring[ni][1] {
intersections = append(intersections, ring[i])
}
}
}
// sort by y, then x
sort.Slice(intersections, func(i, j int) bool {
it := intersections[i]
jt := intersections[j]
if it[1] != jt[1] {
return it[1] < jt[1]
}
return it[0] < jt[0]
})
for i := 0; i < len(intersections); i += 2 {
// fill tiles between pairs of intersections
y := intersections[i][1]
for x := intersections[i][0] + 1; x < intersections[i+1][0]; x++ {
set[maptile.New(x, y, zoom)] = true
}
}
}