Mercurial > gemma

annotate pkg/mesh/triangulation.go @ 5688:6281c18b109f sr-v2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Finsh serializing v2 meshes.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 12 Feb 2024 02:27:41 +0100
parents 1222b777f51f
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
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 (
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 "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
24
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
25 "gemma.intevation.de/gemma/pkg/log"
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 "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
5601
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
29 // Triangulation represents a triangulation
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
30 // consisting of its vertices, the convex hull,
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
31 // the triangles and a half edge representation.
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 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
33 Points []Vertex
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 ConvexHull []Vertex
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
35 Triangles []int32
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
36 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
37 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 // 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
40 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
41 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
42 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
43 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
44 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45
5601
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
46 // EstimateTooLong estimates an edge length which is too long
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
47 // to be a real triangle in the triangulation.
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
48 // It is assumed that the triangles in this mesh are
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
49 // more or less equally sized. If an edge length is more
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
50 // than the 3.5 of the standard dev of the medium length
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
51 // it is considered as too long.
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
52 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
53
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 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
55
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 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
57
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 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
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 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
61 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
62 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
63 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
64 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
65 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
66 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
67 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
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 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
70 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
71 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
72 }
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
73 }
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 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
75 }
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 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
78 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
79 }
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
80
5601
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
81 // ConcaveHull constructs a concave hull for this mesh,
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
82 // Triangles that are considered as too large based on
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
83 // the EstimateTooLong estimation are removed from the border.
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
84 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
85
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
86 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
87 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
88 }
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
89
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
90 tooLong *= tooLong
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
91
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
92 var candidates []int32
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
93
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
94 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
95
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
96 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
97 idx := i * 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
98 var max float64
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
99 vs := t.Triangles[idx : idx+3]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
100 for j, vj := range vs {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
101 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
102 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
103 max = l
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
104 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
105 }
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
106 if max > tooLong {
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
107 candidates = append(candidates, int32(i))
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
108 }
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
109 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
110
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
111 removed := map[int32]struct{}{}
3604
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 isBorder := func(n int32) bool {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
114 n *= 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
115 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
116 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
117 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
118 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
119 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
120 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
121 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
122 return true
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
123 }
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 return false
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
126 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
127
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
128 var newCandidates []int32
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
129
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
130 log.Infof("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
131 for len(candidates) > 0 {
3604
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 oldRemoved := len(removed)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
134
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
135 for _, i := range candidates {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
136
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
137 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
138 removed[i] = struct{}{}
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
139 } else {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
140 newCandidates = append(newCandidates, i)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
141 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
142 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
143
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
144 if oldRemoved == len(removed) {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
145 break
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
146 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
147
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
148 candidates = newCandidates
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
149 newCandidates = newCandidates[:0]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
150 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
151
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
152 log.Infof("candidates left: %d\n", len(candidates))
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
153 log.Infof("triangles: %d\n", len(t.Triangles)/3)
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
154 log.Infof("info: triangles to remove: %d\n", len(removed))
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
155
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
156 type edge struct {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
157 a, b int32
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
158 prev, next *edge
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
159 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
160
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
161 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
162 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
163 if curr == e {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
164 return true
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
165 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
166 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
167 return false
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
168 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
169
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
170 open := map[int32]*edge{}
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
171 var rings []*edge
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
172
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
173 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
174 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
175 continue
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
176 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
177 n := i * 3
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
178 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
179 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
180 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
181 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
182 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
183 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
184 }
2a4216c81e7b Extract the removed triangles 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 }
2a4216c81e7b Extract the removed triangles 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 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
187 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
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 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
190
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
191 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
192 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
193 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
194 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
195 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
196 } 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
197 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
198 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
199 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
200
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
201 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
202 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
203 }
2a4216c81e7b Extract the removed triangles 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 } 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
205 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
206 }
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
207
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
208 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
209 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
210 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
211 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
212 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
213 } 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
214 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
215 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
216 }
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
217
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
218 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
219 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
220 }
2a4216c81e7b Extract the removed triangles 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 } 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
222 open[b] = curr
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 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
225 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
226
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
227 if len(open) > 0 {
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
228 log.Warnf("open vertices left: %d\n", len(open))
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
229 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
230
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
231 if len(rings) == 0 {
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
232 log.Warnln("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
233 return nil, removed
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
234 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
235
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
236 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
237
2a4216c81e7b Extract the removed triangles 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 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
239 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
240 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
241 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
242
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
243 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
244 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
245 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
246
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
247 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
248
5490
5f47eeea988d Use own logging package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4833
diff changeset
249 log.Infof("length of boundary: %d\n", len(polygon))
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
250
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
251 return polygon, removed
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
252 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
253
5601
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
254 // TriangleSlices returns the indices of the triangles
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
255 // of the mesh as slices og length three.
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
256 func (t *Triangulation) TriangleSlices() [][]int32 {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
257 sl := make([][]int32, len(t.Triangles)/3)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
258 var j int
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
259 for i := range sl {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
260 sl[i] = t.Triangles[j : j+3]
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
261 j += 3
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 return sl
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
5601
1222b777f51f Made golint finally happy.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 5490
diff changeset
266 // Tin creates a TIN out of this triangulation.
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
267 func (t *Triangulation) Tin() *Tin {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
268
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
269 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
270 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64}
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 vertices := t.Points
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
273
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
274 for _, v := range vertices {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
275 min.Minimize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
276 max.Maximize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
277 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
278
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
279 return &Tin{
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
280 Vertices: vertices,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
281 Triangles: t.TriangleSlices(),
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
282 Min: min,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
283 Max: max,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
284 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
285 }