Mercurial > gemma
annotate pkg/octree/triangulation.go @ 3678:8f58851927c0
client: make layer factory only return new layer config for individual maps
instead of each time it is invoked. The purpose of the factory was to support multiple maps with individual layers.
But returning a new config each time it is invoked leads to bugs that rely on the layer's state. Now this factory
reuses the same objects it created before, per map.
author | Markus Kottlaender <markus@intevation.de> |
---|---|
date | Mon, 17 Jun 2019 17:31:35 +0200 |
parents | 2a4216c81e7b |
children | ec86a7155377 |
rev | line source |
---|---|
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
1 // Copyright (C) 2018 Michael Fogleman |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
2 // |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
3 // Permission is hereby granted, free of charge, to any person obtaining |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
4 // a copy of this software and associated documentation files (the "Software"), |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
5 // to deal in the Software without restriction, including without limitation |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
6 // the rights to use, copy, modify, merge, publish, distribute, sublicense, |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
7 // and/or sell copies of the Software, and to permit persons to whom the |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
8 // Software is furnished to do so, subject to the following conditions: |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
9 // |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
10 // The above copyright notice and this permission notice shall be included |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
11 // in all copies or substantial portions of the Software. |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
12 // |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
14 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
16 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
19 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
20 package octree |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
21 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
22 import ( |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
23 "fmt" |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
24 "log" |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
25 "math" |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
26 ) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
27 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
28 type Triangulation struct { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
29 Points []Vertex |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
30 ConvexHull []Vertex |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
31 Triangles []int32 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
32 Halfedges []int32 |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
33 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
34 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
35 // Triangulate returns a Delaunay triangulation of the provided points. |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
36 func Triangulate(points []Vertex) (*Triangulation, error) { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
37 t := newTriangulator(points) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
38 err := t.triangulate() |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
39 return &Triangulation{points, t.convexHull(), t.triangles, t.halfedges}, err |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
40 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
41 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
42 func (t *Triangulation) ConcaveHull(tooLong float64) (LineStringZ, map[int32]struct{}) { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
43 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
44 tooLong *= tooLong |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
45 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
46 var candidates []int32 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
47 |
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
48 for i, num := 0, len(t.Triangles)/3; i < num; i++ { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
49 idx := i * 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
50 var max float64 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
51 vs := t.Triangles[idx : idx+3] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
52 for j, vj := range vs { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
53 k := (j + 1) % 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
54 if l := t.Points[vj].SquaredDistance2D(t.Points[vs[k]]); l > max { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
55 max = l |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
56 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
57 } |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
58 if max > tooLong { |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
59 candidates = append(candidates, int32(i)) |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
60 } |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
61 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
62 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
63 removed := map[int32]struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
64 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
65 isBorder := func(n int32) bool { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
66 n *= 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
67 for i := int32(0); i < 3; i++ { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
68 e := n + i |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
69 o := t.Halfedges[e] |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
70 if o < 0 { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
71 return true |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
72 } |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
73 if _, found := removed[o/3]; found { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
74 return true |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
75 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
76 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
77 return false |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
78 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
79 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
80 var newCandidates []int32 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
81 |
3623
1973fa69b2bb
More SVG debug output.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3621
diff
changeset
|
82 log.Printf("info: candidates: %d\n", len(candidates)) |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
83 for len(candidates) > 0 { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
84 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
85 oldRemoved := len(removed) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
86 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
87 for _, i := range candidates { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
88 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
89 if isBorder(i) { |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
90 removed[i] = struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
91 } else { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
92 newCandidates = append(newCandidates, i) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
93 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
94 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
95 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
96 if oldRemoved == len(removed) { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
97 break |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
98 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
99 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
100 candidates = newCandidates |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
101 newCandidates = newCandidates[:0] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
102 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
103 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
104 log.Printf("info: candidates left: %d\n", len(candidates)) |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
105 log.Printf("info: triangles: %d\n", len(t.Triangles)/3) |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
106 log.Printf("info: triangles to remove: %d\n", len(removed)) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
107 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
108 type edge struct { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
109 a, b int32 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
110 prev, next *edge |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
111 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
112 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
113 isClosed := func(e *edge) bool { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
114 for curr := e.next; curr != nil; curr = curr.next { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
115 if curr == e { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
116 return true |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
117 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
118 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
119 return false |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
120 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
121 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
122 open := map[int32]*edge{} |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
123 var rings []*edge |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
124 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
125 for i, num := int32(0), int32(len(t.Triangles)/3); i < num; i++ { |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
126 if _, found := removed[i]; found { |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
127 continue |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
128 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
129 n := i * 3 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
130 for j := int32(0); j < 3; j++ { |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
131 e := n + j |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
132 f := t.Halfedges[e] |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
133 if f >= 0 { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
134 if _, found := removed[f/3]; !found { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
135 continue |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
136 } |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
137 } |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
138 a := t.Triangles[e] |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
139 b := t.Triangles[n+(j+1)%3] |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
140 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
141 curr := &edge{a: a, b: b} |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
142 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
143 if old := open[a]; old != nil { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
144 delete(open, a) |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
145 if old.a == a { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
146 old.prev = curr |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
147 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
148 } else { |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
149 old.next = curr |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
150 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
151 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
152 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
153 if isClosed(old) { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
154 rings = append(rings, old) |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
155 } |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
156 } else { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
157 open[a] = curr |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
158 } |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
159 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
160 if old := open[b]; old != nil { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
161 delete(open, b) |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
162 if old.b == b { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
163 old.next = curr |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
164 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
165 } else { |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
166 old.prev = curr |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
167 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
168 } |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
169 |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
170 if isClosed(old) { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
171 rings = append(rings, old) |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
172 } |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
173 } else { |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
174 open[b] = curr |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
175 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
176 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
177 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
178 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
179 if len(open) > 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
180 log.Printf("warn: open vertices left: %d\n", len(open)) |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
181 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
182 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
183 if len(rings) == 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
184 log.Println("warn: no ring found") |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
185 return nil, removed |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
186 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
187 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
188 curr := rings[0] |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
189 |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
190 polygon := LineStringZ{ |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
191 t.Points[curr.a], |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
192 t.Points[curr.b], |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
193 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
194 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
195 for curr = curr.next; curr != rings[0]; curr = curr.next { |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
196 polygon = append(polygon, t.Points[curr.b]) |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
197 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
198 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
199 polygon = append(polygon, t.Points[rings[0].a]) |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
200 |
3639
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
201 log.Printf("length of boundary: %d\n", len(polygon)) |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
202 |
2a4216c81e7b
Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3634
diff
changeset
|
203 return polygon, removed |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
204 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
205 |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
206 func (t *Triangulation) TriangleSlices() [][]int32 { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
207 sl := make([][]int32, len(t.Triangles)/3) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
208 var j int |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
209 for i := range sl { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
210 sl[i] = t.Triangles[j : j+3] |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
211 j += 3 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
212 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
213 return sl |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
214 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
215 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
216 func (t *Triangulation) Tin() *Tin { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
217 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
218 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
219 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
220 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
221 vertices := t.Points |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
222 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
223 for _, v := range vertices { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
224 min.Minimize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
225 max.Maximize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
226 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
227 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
228 return &Tin{ |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
229 Vertices: vertices, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
230 Triangles: t.TriangleSlices(), |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
231 Min: min, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
232 Max: max, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
233 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
234 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
235 |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
236 func (t *Triangulation) area() float64 { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
237 var result float64 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
238 points := t.Points |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
239 ts := t.Triangles |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
240 for i := 0; i < len(ts); i += 3 { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
241 p0 := points[ts[i+0]] |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
242 p1 := points[ts[i+1]] |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
243 p2 := points[ts[i+2]] |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
244 result += area(p0, p1, p2) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
245 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
246 return result / 2 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
247 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
248 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
249 // Validate performs several sanity checks on the Triangulation to check for |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
250 // potential errors. Returns nil if no issues were found. You normally |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
251 // shouldn't need to call this function but it can be useful for debugging. |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
252 func (t *Triangulation) Validate() error { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
253 // verify halfedges |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
254 for i1, i2 := range t.Halfedges { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
255 if i1 != -1 && t.Halfedges[i1] != i2 { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
256 return fmt.Errorf("invalid halfedge connection") |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
257 } |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
258 if i2 != -1 && t.Halfedges[i2] != int32(i1) { |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
259 return fmt.Errorf("invalid halfedge connection") |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
260 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
261 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
262 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
263 // verify convex hull area vs sum of triangle areas |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
264 hull1 := t.ConvexHull |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
265 hull2 := ConvexHull(t.Points) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
266 area1 := polygonArea(hull1) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
267 area2 := polygonArea(hull2) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
268 area3 := t.area() |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
269 if math.Abs(area1-area2) > 1e-9 || math.Abs(area1-area3) > 1e-9 { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
270 return fmt.Errorf("hull areas disagree: %f, %f, %f", area1, area2, area3) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
271 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
272 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
273 // verify convex hull perimeter |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
274 perimeter1 := polygonPerimeter(hull1) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
275 perimeter2 := polygonPerimeter(hull2) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
276 if math.Abs(perimeter1-perimeter2) > 1e-9 { |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
277 return fmt.Errorf("hull perimeters disagree: %f, %f", perimeter1, perimeter2) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
278 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
279 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
280 return nil |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
281 } |