forked from omniscale/imposm3
/
multipolygon.go
238 lines (210 loc) · 5.58 KB
/
multipolygon.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
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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
package geom
import (
"errors"
"sort"
osm "github.com/omniscale/go-osm"
"github.com/omniscale/imposm3/geom/geos"
)
type PreparedRelation struct {
rings []*ring
rel *osm.Relation
srid int
}
// PrepareRelation is the first step in building a (multi-)polygon of a Relation.
// It builds rings from all ways and returns an error if there are unclosed rings.
func PrepareRelation(rel *osm.Relation, srid int, maxRingGap float64) (PreparedRelation, error) {
rings, err := buildRings(rel, maxRingGap)
if err != nil {
return PreparedRelation{}, err
}
return PreparedRelation{rings, rel, srid}, nil
}
// Build creates the (multi)polygon Geometry of the Relation.
func (prep *PreparedRelation) Build() (Geometry, error) {
g := geos.NewGeos()
g.SetHandleSrid(prep.srid)
defer g.Finish()
geom, err := buildRelGeometry(g, prep.rel, prep.rings)
if err != nil {
return Geometry{}, err
}
wkb := g.AsEwkbHex(geom)
if wkb == nil {
return Geometry{}, errors.New("unable to create WKB for relation")
}
return Geometry{Geom: geom, Wkb: wkb}, nil
}
func destroyRings(g *geos.Geos, rings []*ring) {
for _, r := range rings {
if r.geom != nil {
g.Destroy(r.geom)
r.geom = nil
}
}
}
func buildRings(rel *osm.Relation, maxRingGap float64) ([]*ring, error) {
var rings []*ring
var incompleteRings []*ring
var completeRings []*ring
var mergedRings []*ring
var err error
g := geos.NewGeos()
defer g.Finish()
defer func() {
if err != nil {
destroyRings(g, mergedRings)
destroyRings(g, completeRings)
}
}()
// create rings for all WayMember members
for _, member := range rel.Members {
if member.Way == nil {
continue
}
rings = append(rings, newRing(member.Way))
}
// create geometries for closed rings, collect incomplete rings
for _, r := range rings {
if r.isClosed() {
r.geom, err = Polygon(g, r.nodes)
if err != nil {
return nil, err
}
completeRings = append(completeRings, r)
} else {
incompleteRings = append(incompleteRings, r)
}
}
// merge incomplete rings
mergedRings = mergeRings(incompleteRings)
// create geometries for merged rings
for _, ring := range mergedRings {
if !ring.isClosed() && !ring.tryClose(maxRingGap) {
continue
}
ring.geom, err = Polygon(g, ring.nodes)
if err != nil {
return nil, err
}
completeRings = append(completeRings, ring)
}
if len(completeRings) == 0 {
err = ErrorNoRing // for defer
return nil, err
}
// sort by area (large to small)
for _, r := range completeRings {
r.area = r.geom.Area()
}
sort.Sort(sortableRingsDesc(completeRings))
return completeRings, nil
}
type sortableRingsDesc []*ring
func (r sortableRingsDesc) Len() int { return len(r) }
func (r sortableRingsDesc) Less(i, j int) bool { return r[i].area > r[j].area }
func (r sortableRingsDesc) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
// buildRelGeometry builds the geometry of rel by creating a multipolygon of all rings.
// rings need to be sorted by area (large to small).
func buildRelGeometry(g *geos.Geos, rel *osm.Relation, rings []*ring) (*geos.Geom, error) {
totalRings := len(rings)
shells := map[*ring]bool{rings[0]: true}
for i := 0; i < totalRings; i++ {
testGeom := g.Prepare(rings[i].geom)
if testGeom == nil {
return nil, errors.New("Error while preparing geometry")
}
for j := i + 1; j < totalRings; j++ {
if g.PreparedContains(testGeom, rings[j].geom) {
if rings[j].containedBy != -1 {
// j is inside a larger ring, remove that relationship
// e.g. j is hole inside a hole (i)
delete(rings[rings[j].containedBy].holes, rings[j])
delete(shells, rings[j])
}
// remember parent
rings[j].containedBy = i
// add ring as hole or shell
if ringIsHole(rings, j) {
rings[i].holes[rings[j]] = true
rings[i].outer = false
} else {
shells[rings[j]] = true
rings[i].outer = true
}
}
}
if rings[i].containedBy == -1 {
// add as shell if it is not a hole
shells[rings[i]] = true
rings[i].outer = true
}
g.PreparedDestroy(testGeom)
}
var polygons []*geos.Geom
for shell := range shells {
var interiors []*geos.Geom
for hole := range shell.holes {
ring := g.Clone(g.ExteriorRing(hole.geom))
g.Destroy(hole.geom)
if ring == nil {
return nil, errors.New("unable to get exterior ring")
}
interiors = append(interiors, ring)
}
exterior := g.Clone(g.ExteriorRing(shell.geom))
g.Destroy(shell.geom)
if exterior == nil {
return nil, errors.New("unable to get exterior ring")
}
polygon := g.Polygon(exterior, interiors)
if polygon == nil {
return nil, errors.New("unable to build polygon")
}
polygons = append(polygons, polygon)
}
var result *geos.Geom
if len(polygons) == 1 {
result = polygons[0]
} else {
result = g.MultiPolygon(polygons)
if result == nil {
return nil, errors.New("unable to build mulipolygon")
}
}
var err error
result, err = g.MakeValid(result)
if err != nil {
return nil, err
}
g.DestroyLater(result)
outer := make(map[int64]struct{})
for i := range rings {
if rings[i].outer {
for _, w := range rings[i].ways {
outer[w.ID] = struct{}{}
}
}
}
for i := range rel.Members {
mid := rel.Members[i].ID
if _, ok := outer[mid]; ok {
rel.Members[i].Role = "outer"
} else {
rel.Members[i].Role = "inner"
}
}
return result, nil
}
// ringIsHole returns true if rings[idx] is a hole, False if it is a
// shell (also if hole in a hole, etc)
func ringIsHole(rings []*ring, idx int) bool {
containedCounter := 0
for {
idx = rings[idx].containedBy
if idx == -1 {
break
}
containedCounter++
}
return containedCounter%2 == 1
}