Mercurial > gemma

annotate pkg/octree/triangulation.go @ 3733:ec86a7155377 concave-hull

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 24 Jun 2019 11:39:09 +0200
parents 2a4216c81e7b
children
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
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 package octree
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 import (
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 "fmt"
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
24 "log"
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 "math"
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
26
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
27 "gonum.org/v1/gonum/stat"
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 )
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 type Triangulation struct {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 Points []Vertex
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 ConvexHull []Vertex
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
33 Triangles []int32
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
34 Halfedges []int32
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 // Triangulate returns a Delaunay triangulation of the provided points.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38 func Triangulate(points []Vertex) (*Triangulation, error) {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 t := newTriangulator(points)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 err := t.triangulate()
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 return &Triangulation{points, t.convexHull(), t.triangles, t.halfedges}, err
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
44 func (t *Triangulation) EstimateTooLong() float64 {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
45
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
46 num := len(t.Triangles) / 3
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
47
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
48 lengths := make([]float64, 0, num)
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
49
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
50 points := t.Points
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
51
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
52 tris:
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
53 for i := 0; i < num; i++ {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
54 idx := i * 3
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
55 var max float64
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
56 vs := t.Triangles[idx : idx+3]
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
57 for j, vj := range vs {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
58 if t.Halfedges[idx+j] < 0 {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
59 continue tris
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
60 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
61 k := (j + 1) % 3
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
62 if l := points[vj].Distance2D(points[vs[k]]); l > max {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
63 max = l
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
64 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
65 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
66 lengths = append(lengths, max)
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
67 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
68
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
69 std := stat.StdDev(lengths, nil)
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
70 return 3.5 * std
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
71 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
72
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
73 func (t *Triangulation) ConcaveHull(tooLong float64) (LineStringZ, map[int32]struct{}) {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
74
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
75 if tooLong <= 0 {
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
76 tooLong = t.EstimateTooLong()
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
77 }
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
78
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
79 tooLong *= tooLong
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
80
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
81 var candidates []int32
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
82
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
83 points := t.Points
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
84
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
85 for i, num := 0, len(t.Triangles)/3; i < num; i++ {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
86 idx := i * 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
87 var max float64
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
88 vs := t.Triangles[idx : idx+3]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
89 for j, vj := range vs {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
90 k := (j + 1) % 3
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
91 if l := points[vj].SquaredDistance2D(points[vs[k]]); l > max {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
92 max = l
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
93 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
94 }
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
95 if max > tooLong {
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
96 candidates = append(candidates, int32(i))
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
97 }
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
98 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
99
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
100 removed := map[int32]struct{}{}
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
101
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
102 isBorder := func(n int32) bool {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
103 n *= 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
104 for i := int32(0); i < 3; i++ {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
105 e := n + i
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
106 o := t.Halfedges[e]
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
107 if o < 0 {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
108 return true
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
109 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
110 if _, found := removed[o/3]; found {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
111 return true
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
112 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
113 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
114 return false
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
115 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
116
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
117 var newCandidates []int32
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
118
3623
1973fa69b2bb More SVG debug output.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3621
diff changeset
119 log.Printf("info: candidates: %d\n", len(candidates))
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
120 for len(candidates) > 0 {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
121
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
122 oldRemoved := len(removed)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
123
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
124 for _, i := range candidates {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
125
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
126 if isBorder(i) {
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
127 removed[i] = struct{}{}
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
128 } else {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
129 newCandidates = append(newCandidates, i)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
130 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
131 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
132
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
133 if oldRemoved == len(removed) {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
134 break
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
135 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
136
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
137 candidates = newCandidates
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
138 newCandidates = newCandidates[:0]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
139 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
140
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
141 log.Printf("info: candidates left: %d\n", len(candidates))
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
142 log.Printf("info: triangles: %d\n", len(t.Triangles)/3)
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
143 log.Printf("info: triangles to remove: %d\n", len(removed))
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
144
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
145 type edge struct {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
146 a, b int32
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
147 prev, next *edge
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
148 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
149
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
150 isClosed := func(e *edge) bool {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
151 for curr := e.next; curr != nil; curr = curr.next {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
152 if curr == e {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
153 return true
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
154 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
155 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
156 return false
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
157 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
158
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
159 open := map[int32]*edge{}
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
160 var rings []*edge
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
161
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
162 for i, num := int32(0), int32(len(t.Triangles)/3); i < num; i++ {
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
163 if _, found := removed[i]; found {
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
164 continue
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
165 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
166 n := i * 3
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
167 for j := int32(0); j < 3; j++ {
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
168 e := n + j
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
169 f := t.Halfedges[e]
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
170 if f >= 0 {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
171 if _, found := removed[f/3]; !found {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
172 continue
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
173 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
174 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
175 a := t.Triangles[e]
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
176 b := t.Triangles[n+(j+1)%3]
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
177
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
178 curr := &edge{a: a, b: b}
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
179
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
180 if old := open[a]; old != nil {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
181 delete(open, a)
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
182 if old.a == a {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
183 old.prev = curr
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
184 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
185 } else {
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
186 old.next = curr
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
187 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
188 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
189
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
190 if isClosed(old) {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
191 rings = append(rings, old)
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
192 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
193 } else {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
194 open[a] = curr
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
195 }
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
196
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
197 if old := open[b]; old != nil {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
198 delete(open, b)
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
199 if old.b == b {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
200 old.next = curr
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
201 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
202 } else {
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
203 old.prev = curr
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
204 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
205 }
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
206
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
207 if isClosed(old) {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
208 rings = append(rings, old)
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
209 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
210 } else {
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
211 open[b] = curr
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
212 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
213 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
214 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
215
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
216 if len(open) > 0 {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
217 log.Printf("warn: open vertices left: %d\n", len(open))
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
218 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
219
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
220 if len(rings) == 0 {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
221 log.Println("warn: no ring found")
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
222 return nil, removed
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
223 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
224
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
225 curr := rings[0]
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
226
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
227 polygon := LineStringZ{
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
228 points[curr.a],
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
229 points[curr.b],
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
230 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
231
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
232 for curr = curr.next; curr != rings[0]; curr = curr.next {
3733
ec86a7155377 Estimated too large triangles as triangles which have an edge which is at least 3.5 times as long as the standard dev of the longest egde per inner triangle.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3639
diff changeset
233 polygon = append(polygon, points[curr.b])
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
234 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
235
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
236 polygon = append(polygon, t.Points[rings[0].a])
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
237
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
238 log.Printf("length of boundary: %d\n", len(polygon))
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
239
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
240 return polygon, removed
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
241 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
242
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
243 func (t *Triangulation) TriangleSlices() [][]int32 {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
244 sl := make([][]int32, len(t.Triangles)/3)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
245 var j int
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
246 for i := range sl {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
247 sl[i] = t.Triangles[j : j+3]
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
248 j += 3
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
249 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
250 return sl
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
251 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
252
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
253 func (t *Triangulation) Tin() *Tin {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
254
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
255 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
256 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
257
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
258 vertices := t.Points
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
259
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
260 for _, v := range vertices {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
261 min.Minimize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
262 max.Maximize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
263 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
264
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
265 return &Tin{
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
266 Vertices: vertices,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
267 Triangles: t.TriangleSlices(),
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
268 Min: min,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
269 Max: max,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
270 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
271 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
272
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273 func (t *Triangulation) area() float64 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
274 var result float64
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
275 points := t.Points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
276 ts := t.Triangles
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
277 for i := 0; i < len(ts); i += 3 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
278 p0 := points[ts[i+0]]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
279 p1 := points[ts[i+1]]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
280 p2 := points[ts[i+2]]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
281 result += area(p0, p1, p2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
282 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
283 return result / 2
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
284 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
285
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
286 // Validate performs several sanity checks on the Triangulation to check for
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
287 // potential errors. Returns nil if no issues were found. You normally
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
288 // shouldn't need to call this function but it can be useful for debugging.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
289 func (t *Triangulation) Validate() error {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
290 // verify halfedges
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
291 for i1, i2 := range t.Halfedges {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
292 if i1 != -1 && t.Halfedges[i1] != i2 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
293 return fmt.Errorf("invalid halfedge connection")
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
294 }
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
295 if i2 != -1 && t.Halfedges[i2] != int32(i1) {
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
296 return fmt.Errorf("invalid halfedge connection")
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
297 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
298 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
299
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
300 // verify convex hull area vs sum of triangle areas
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
301 hull1 := t.ConvexHull
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
302 hull2 := ConvexHull(t.Points)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
303 area1 := polygonArea(hull1)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
304 area2 := polygonArea(hull2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
305 area3 := t.area()
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
306 if math.Abs(area1-area2) > 1e-9 || math.Abs(area1-area3) > 1e-9 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
307 return fmt.Errorf("hull areas disagree: %f, %f, %f", area1, area2, area3)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
308 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
309
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
310 // verify convex hull perimeter
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
311 perimeter1 := polygonPerimeter(hull1)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
312 perimeter2 := polygonPerimeter(hull2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
313 if math.Abs(perimeter1-perimeter2) > 1e-9 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
314 return fmt.Errorf("hull perimeters disagree: %f, %f", perimeter1, perimeter2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
315 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
316
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
317 return nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
318 }