Mercurial > gemma

annotate pkg/octree/triangulation.go @ 3629:1825a1bc9fb1 configuration

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed typo in SQL statement.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 11 Jun 2019 12:17:47 +0200
parents e1021fd60190
children 2893ee8ce06f
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
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
42 func (t *Triangulation) ConcaveHull(tooLong float64) []int32 {
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
3609
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
46 var oldCandidates []int32
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 {
e1021fd60190 Removed statistics from elimination of triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3604
diff changeset
59 oldCandidates = append(oldCandidates, int32(i))
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
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
63 removed := map[int32]bool{}
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
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
69 if t.Halfedges[e] == -1 || removed[e] {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
70 return true
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
71 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
72 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
73 return false
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
74 }
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 var newCandidates []int32
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
77
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
78 for len(oldCandidates) > 0 {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
79 log.Printf("candidates: %d\n", len(oldCandidates))
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
80
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
81 oldRemoved := len(removed)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
82
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
83 for _, i := range oldCandidates {
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 if isBorder(i) {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
86 removed[i] = true
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
87 } else {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
88 newCandidates = append(newCandidates, i)
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
89 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
90 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
91
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
92 if oldRemoved == len(removed) {
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
93 break
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 oldCandidates = newCandidates
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
97 newCandidates = newCandidates[:0]
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
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
100 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
101
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
102 return nil
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
103 }
6248a4bc10c7 Moved triangle elimination to triangulation code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2484
diff changeset
104
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
105 func (t *Triangulation) TriangleSlices() [][]int32 {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
106 sl := make([][]int32, len(t.Triangles)/3)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
107 var j int
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
108 for i := range sl {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
109 sl[i] = t.Triangles[j : j+3]
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
110 j += 3
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
111 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
112 return sl
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
113 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
114
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
115 func (t *Triangulation) Tin() *Tin {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
116
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
117 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
118 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
119
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
120 vertices := t.Points
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
121
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
122 for _, v := range vertices {
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
123 min.Minimize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
124 max.Maximize(v)
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
125 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
126
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
127 return &Tin{
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
128 Vertices: vertices,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
129 Triangles: t.TriangleSlices(),
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
130 Min: min,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
131 Max: max,
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
132 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
133 }
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
134
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135 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
136 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
137 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
138 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
139 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
140 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
141 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
142 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
143 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
144 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
145 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
146 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
147
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
148 // 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
149 // 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
150 // 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
151 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
152 // verify halfedges
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
153 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
154 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
155 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
156 }
2484
4fa92d468164 Use fogleman's triangulation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2483
diff changeset
157 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
158 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
159 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
160 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
161
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
162 // 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
163 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
164 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
165 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
166 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
167 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
168 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
169 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
170 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
171
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
172 // 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
173 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
174 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
175 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
176 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
177 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
178
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
179 return nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
180 }