Mercurial > gemma

annotate pkg/mesh/triangulation.go @ 4889:ab6eb160cd29

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Sounding result cache: Start background cache cleanup lazily only when the cache is really used.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 09 Feb 2020 20:24:54 +0100
parents 3f0382e9f302
children 5f47eeea988d
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 }