Mercurial > gemma

annotate pkg/octree/triangulation.go @ 3674:a3d1fce63c9e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import_configuration: search for user and country
author Thomas Junk <thomas.junk@intevation.de>
date Mon, 17 Jun 2019 16:24:46 +0200
parents 2a4216c81e7b
children ec86a7155377
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"
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 )
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 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
29 Points []Vertex
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 ConvexHull []Vertex
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
31 Triangles []int32
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
32 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
33 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 // 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
36 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
37 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
38 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
39 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
40 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41
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
42 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
43
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
44 tooLong *= tooLong
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
45
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
46 var candidates []int32
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
47
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
48 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
49 idx := i * 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
50 var max float64
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
51 vs := t.Triangles[idx : idx+3]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
52 for j, vj := range vs {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
53 k := (j + 1) % 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
54 if l := t.Points[vj].SquaredDistance2D(t.Points[vs[k]]); l > max {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
55 max = l
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
56 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
57 }
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
58 if max > tooLong {
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
59 candidates = append(candidates, int32(i))
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
60 }
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
61 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
62
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
63 removed := map[int32]struct{}{}
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
64
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
65 isBorder := func(n int32) bool {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
66 n *= 3
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
67 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
68 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
69 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
70 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
71 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
72 }
2a4216c81e7b Extract the removed triangles 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 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
74 return true
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
75 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
76 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
77 return false
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
78 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
79
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
80 var newCandidates []int32
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
81
3623
1973fa69b2bb More SVG debug output.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3621
diff changeset
82 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
83 for len(candidates) > 0 {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
84
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
85 oldRemoved := len(removed)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
86
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
87 for _, i := range candidates {
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
88
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
89 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
90 removed[i] = struct{}{}
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
91 } else {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
92 newCandidates = append(newCandidates, i)
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 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
95
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
96 if oldRemoved == len(removed) {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
97 break
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
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
100 candidates = newCandidates
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
101 newCandidates = newCandidates[:0]
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
102 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
103
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
104 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
105 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
106 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
107
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
108 type edge struct {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
109 a, b int32
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
110 prev, next *edge
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
111 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
112
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
113 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
114 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
115 if curr == e {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
116 return true
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
117 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
118 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
119 return false
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
120 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
121
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
122 open := map[int32]*edge{}
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
123 var rings []*edge
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
124
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
125 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
126 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
127 continue
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
128 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
129 n := i * 3
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
130 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
131 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
132 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
133 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
134 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
135 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
136 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
137 }
2a4216c81e7b Extract the removed triangles 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 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
139 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
140
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
141 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
142
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
143 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
144 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
145 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
146 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
147 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
148 } 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
149 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
150 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
151 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
152
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
153 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
154 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
155 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
156 } 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
157 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
158 }
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
159
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
160 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
161 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
162 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
163 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
164 curr.prev = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
165 } 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
166 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
167 curr.next = old
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
168 }
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
2a4216c81e7b Extract the removed triangles 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 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
171 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
172 }
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
173 } 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
174 open[b] = curr
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
175 }
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 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
178
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
179 if len(open) > 0 {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
180 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
181 }
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
182
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
183 if len(rings) == 0 {
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
184 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
185 return nil, removed
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
186 }
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
187
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
188 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
189
2a4216c81e7b Extract the removed triangles 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 polygon := LineStringZ{
2a4216c81e7b Extract the removed triangles 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 t.Points[curr.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
192 t.Points[curr.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
193 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
194
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
195 for curr = curr.next; curr != rings[0]; curr = curr.next {
3639
2a4216c81e7b Extract the removed triangles from first triangulation, too. Useful to build a artifical DEM for second pass.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3634
diff changeset
196 polygon = append(polygon, t.Points[curr.b])
3634
db7136854a51 Hash the vertices of the concave hull together.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3633
diff changeset
197 }
3621
2893ee8ce06f concave hulls for single beam scans ... WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3609
diff changeset
198
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
199 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
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 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
202
2a4216c81e7b Extract the removed triangles 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 return polygon, removed
3604
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
204 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
205
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
206 func (t *Triangulation) TriangleSlices() [][]int32 {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
207 sl := make([][]int32, len(t.Triangles)/3)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
208 var j int
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
209 for i := range sl {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
210 sl[i] = t.Triangles[j : j+3]
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
211 j += 3
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
212 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
213 return sl
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
214 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
215
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
216 func (t *Triangulation) Tin() *Tin {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
217
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
218 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
219 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
220
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
221 vertices := t.Points
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
222
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
223 for _, v := range vertices {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
224 min.Minimize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
225 max.Maximize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
226 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
227
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
228 return &Tin{
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
229 Vertices: vertices,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
230 Triangles: t.TriangleSlices(),
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
231 Min: min,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
232 Max: max,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
233 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
234 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
235
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
236 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
237 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
238 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
239 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
240 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
241 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
242 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
243 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
244 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
245 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
246 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
247 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
248
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
249 // 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
250 // 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
251 // 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
252 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
253 // verify halfedges
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 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
255 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
256 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
257 }
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
258 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
259 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
260 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
261 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
262
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
263 // 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
264 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
265 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
266 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
267 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
268 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
269 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
270 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
271 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
272
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273 // 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
274 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
275 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
276 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
277 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
278 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
279
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
280 return nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
281 }