Mercurial > gemma
annotate pkg/octree/triangulation.go @ 3911:e4e496ae7974
fairway_availability: rendering to offscreen element
author | Thomas Junk <thomas.junk@intevation.de> |
---|---|
date | Thu, 11 Jul 2019 10:58:22 +0200 |
parents | ec86a7155377 |
children |
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" |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
26 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
27 "gonum.org/v1/gonum/stat" |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
28 ) |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
29 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
30 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
|
31 Points []Vertex |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
32 ConvexHull []Vertex |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
33 Triangles []int32 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
34 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
|
35 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
36 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
37 // 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
|
38 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
|
39 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
|
40 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
|
41 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
|
42 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
43 |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
44 func (t *Triangulation) EstimateTooLong() float64 { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
45 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
46 num := len(t.Triangles) / 3 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
47 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
48 lengths := make([]float64, 0, num) |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
49 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
50 points := t.Points |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
51 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
52 tris: |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
53 for i := 0; i < num; i++ { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
54 idx := i * 3 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
55 var max float64 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
56 vs := t.Triangles[idx : idx+3] |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
57 for j, vj := range vs { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
58 if t.Halfedges[idx+j] < 0 { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
59 continue tris |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
60 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
61 k := (j + 1) % 3 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
62 if l := points[vj].Distance2D(points[vs[k]]); l > max { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
63 max = l |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
64 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
65 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
66 lengths = append(lengths, max) |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
67 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
68 |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
69 std := stat.StdDev(lengths, nil) |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
70 return 3.5 * std |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
71 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
72 |
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
|
73 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
|
74 |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
75 if tooLong <= 0 { |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
76 tooLong = t.EstimateTooLong() |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
77 } |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
78 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
79 tooLong *= tooLong |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
80 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
81 var candidates []int32 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
82 |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
83 points := t.Points |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
84 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
85 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
|
86 idx := i * 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
87 var max float64 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
88 vs := t.Triangles[idx : idx+3] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
89 for j, vj := range vs { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
90 k := (j + 1) % 3 |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
91 if l := points[vj].SquaredDistance2D(points[vs[k]]); l > max { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
92 max = l |
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 } |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
95 if max > tooLong { |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
96 candidates = append(candidates, int32(i)) |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
97 } |
3604
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 |
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
|
100 removed := map[int32]struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
101 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
102 isBorder := func(n int32) bool { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
103 n *= 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
104 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
|
105 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
|
106 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
|
107 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
|
108 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
|
109 } |
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
|
110 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
|
111 return true |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
112 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
113 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
114 return false |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
115 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
116 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
117 var newCandidates []int32 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
118 |
3623
1973fa69b2bb
More SVG debug output.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3621
diff
changeset
|
119 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
|
120 for len(candidates) > 0 { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
121 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
122 oldRemoved := len(removed) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
123 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
124 for _, i := range candidates { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
125 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
126 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
|
127 removed[i] = struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
128 } else { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
129 newCandidates = append(newCandidates, i) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
130 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
131 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
132 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
133 if oldRemoved == len(removed) { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
134 break |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
135 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
136 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
137 candidates = newCandidates |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
138 newCandidates = newCandidates[:0] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
139 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
140 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
141 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
|
142 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
|
143 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
|
144 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
145 type edge struct { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
146 a, b int32 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
147 prev, next *edge |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
148 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
149 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
150 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
|
151 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
|
152 if curr == e { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
153 return true |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
154 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
155 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
156 return false |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
157 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
158 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
159 open := map[int32]*edge{} |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
160 var rings []*edge |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
161 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
162 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
|
163 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
|
164 continue |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
165 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
166 n := i * 3 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
167 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
|
168 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
|
169 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
|
170 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
|
171 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
|
172 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
|
173 } |
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 } |
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
|
175 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
|
176 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
|
177 |
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
|
178 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
|
179 |
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
|
180 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
|
181 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
|
182 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
|
183 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
|
184 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
185 } 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
|
186 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
|
187 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
188 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
189 |
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
|
190 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
|
191 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
|
192 } |
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 } 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
|
194 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
|
195 } |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
196 |
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
|
197 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
|
198 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
|
199 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
|
200 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
|
201 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
202 } 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
|
203 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
|
204 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
205 } |
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
|
206 |
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
|
207 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
|
208 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
|
209 } |
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
|
210 } 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
|
211 open[b] = curr |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
212 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
213 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
214 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
215 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
216 if len(open) > 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
217 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
|
218 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
219 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
220 if len(rings) == 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
221 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
|
222 return nil, removed |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
223 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
224 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
225 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
|
226 |
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
|
227 polygon := LineStringZ{ |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
228 points[curr.a], |
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
229 points[curr.b], |
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
|
230 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
231 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
232 for curr = curr.next; curr != rings[0]; curr = curr.next { |
3733
ec86a7155377
Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3639
diff
changeset
|
233 polygon = append(polygon, points[curr.b]) |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
234 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
235 |
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
|
236 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
|
237 |
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
|
238 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
|
239 |
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
|
240 return polygon, removed |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
241 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
242 |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
243 func (t *Triangulation) TriangleSlices() [][]int32 { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
244 sl := make([][]int32, len(t.Triangles)/3) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
245 var j int |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
246 for i := range sl { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
247 sl[i] = t.Triangles[j : j+3] |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
248 j += 3 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
249 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
250 return sl |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
251 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
252 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
253 func (t *Triangulation) Tin() *Tin { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
254 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
255 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
256 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
257 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
258 vertices := t.Points |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
259 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
260 for _, v := range vertices { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
261 min.Minimize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
262 max.Maximize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
263 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
264 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
265 return &Tin{ |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
266 Vertices: vertices, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
267 Triangles: t.TriangleSlices(), |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
268 Min: min, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
269 Max: max, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
270 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
271 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
272 |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
273 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
|
274 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
|
275 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
|
276 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
|
277 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
|
278 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
|
279 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
|
280 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
|
281 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
|
282 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
283 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
|
284 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
285 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
286 // 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
|
287 // 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
|
288 // 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
|
289 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
|
290 // verify halfedges |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
291 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
|
292 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
|
293 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
|
294 } |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
295 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
|
296 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
|
297 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
298 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
299 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
300 // 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
|
301 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
|
302 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
|
303 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
|
304 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
|
305 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
|
306 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
|
307 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
|
308 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
309 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
310 // 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
|
311 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
|
312 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
|
313 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
|
314 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
|
315 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
316 |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
317 return nil |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
318 } |