Mercurial > gemma
annotate pkg/mesh/triangulation.go @ 5394:f1a42eea08d3 extented-report
Backed out changeset fe3f651bb03d ... wrong branch.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Sun, 04 Jul 2021 11:36:39 +0200 |
parents | 3f0382e9f302 |
children | 5f47eeea988d |
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 |
4827
f4abfd0ee8ad
Renamed octree package to mesh as there is no octree any more.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3733
diff
changeset
|
20 package mesh |
2483
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 ( |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
23 "log" |
2483
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
24 "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
|
25 |
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 "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
|
27 ) |
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 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
|
30 Points []Vertex |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
31 ConvexHull []Vertex |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
32 Triangles []int32 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
33 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
|
34 } |
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 // 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
|
37 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
|
38 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
|
39 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
|
40 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
|
41 } |
620038ade708
Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
42 |
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
|
43 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
|
44 |
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 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
|
46 |
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 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
|
48 |
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 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
|
50 |
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 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
|
52 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
|
53 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
|
54 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
|
55 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
|
56 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
|
57 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
|
58 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
|
59 } |
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 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
|
61 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
|
62 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
|
63 } |
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 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
|
66 } |
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 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
|
69 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
|
70 } |
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 |
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
|
72 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
|
73 |
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
|
74 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
|
75 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
|
76 } |
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 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
78 tooLong *= tooLong |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
79 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
80 var candidates []int32 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
81 |
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
|
82 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
|
83 |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
84 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
|
85 idx := i * 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
86 var max float64 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
87 vs := t.Triangles[idx : idx+3] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
88 for j, vj := range vs { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
89 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
|
90 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
|
91 max = l |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
92 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
93 } |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
94 if max > tooLong { |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
95 candidates = append(candidates, int32(i)) |
3609
e1021fd60190
Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3604
diff
changeset
|
96 } |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
97 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
98 |
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
|
99 removed := map[int32]struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
100 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
101 isBorder := func(n int32) bool { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
102 n *= 3 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
103 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
|
104 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
|
105 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
|
106 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
|
107 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
|
108 } |
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 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
|
110 return true |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
111 } |
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 return false |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
114 } |
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 var newCandidates []int32 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
117 |
3623
1973fa69b2bb
More SVG debug output.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3621
diff
changeset
|
118 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
|
119 for len(candidates) > 0 { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
120 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
121 oldRemoved := len(removed) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
122 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
123 for _, i := range candidates { |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
124 |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
125 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
|
126 removed[i] = struct{}{} |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
127 } else { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
128 newCandidates = append(newCandidates, i) |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
129 } |
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 if oldRemoved == len(removed) { |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
133 break |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
134 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
135 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
136 candidates = newCandidates |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
137 newCandidates = newCandidates[:0] |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
138 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
139 |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
140 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
|
141 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
|
142 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
|
143 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
144 type edge struct { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
145 a, b int32 |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
146 prev, next *edge |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
147 } |
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 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
|
150 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
|
151 if curr == e { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
152 return true |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
153 } |
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 return false |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
156 } |
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 open := map[int32]*edge{} |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
159 var rings []*edge |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
160 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
161 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
|
162 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
|
163 continue |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
164 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
165 n := i * 3 |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
166 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
|
167 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
|
168 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
|
169 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
|
170 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
|
171 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
|
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 } |
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 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
|
175 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
|
176 |
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
|
177 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
|
178 |
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
|
179 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
|
180 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
|
181 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
|
182 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
|
183 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
184 } 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
|
185 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
|
186 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
187 } |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
188 |
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 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
|
190 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
|
191 } |
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 } 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
|
193 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
|
194 } |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
195 |
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 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
|
197 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
|
198 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
|
199 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
|
200 curr.prev = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
201 } 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
|
202 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
|
203 curr.next = old |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
204 } |
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
|
205 |
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 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
|
207 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
|
208 } |
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 } 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
|
210 open[b] = curr |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
211 } |
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 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
215 if len(open) > 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
216 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
|
217 } |
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 if len(rings) == 0 { |
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
220 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
|
221 return nil, removed |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
222 } |
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
223 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
224 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
|
225 |
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 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
|
227 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
|
228 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
|
229 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
230 |
3634
db7136854a51
Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3633
diff
changeset
|
231 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
|
232 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
|
233 } |
3621
2893ee8ce06f
concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
3609
diff
changeset
|
234 |
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
|
235 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
|
236 |
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
|
237 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
|
238 |
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 return polygon, removed |
3604
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
240 } |
6248a4bc10c7
Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2484
diff
changeset
|
241 |
2484
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
242 func (t *Triangulation) TriangleSlices() [][]int32 { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
243 sl := make([][]int32, len(t.Triangles)/3) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
244 var j int |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
245 for i := range sl { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
246 sl[i] = t.Triangles[j : j+3] |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
247 j += 3 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
248 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
249 return sl |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
250 } |
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 func (t *Triangulation) Tin() *Tin { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
253 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
254 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
255 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64} |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
256 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
257 vertices := t.Points |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
258 |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
259 for _, v := range vertices { |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
260 min.Minimize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
261 max.Maximize(v) |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
262 } |
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 return &Tin{ |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
265 Vertices: vertices, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
266 Triangles: t.TriangleSlices(), |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
267 Min: min, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
268 Max: max, |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
269 } |
4fa92d468164
Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2483
diff
changeset
|
270 } |