gemma: pkg/octree/triangulation.go annotate

annotate pkg/octree/triangulation.go @ 3632:943c454d5633 single-beam

Merged default into single-beam branch.

author	Sascha L. Teichmann <sascha.teichmann@intevation.de>
date	Tue, 11 Jun 2019 14:46:14 +0200
parents	1973fa69b2bb
children	cfb4e01f2b7f

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"
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	26 "os"
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	27
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	28 svg "github.com/ajstarks/svgo"
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	29 )
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	30
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	31 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	32 Points []Vertex
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	33 ConvexHull []Vertex
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	34 Triangles []int32
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	35 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	36 }
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 // 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	39 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	40 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	41 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	42 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	43 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	44
3609 e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	45 func (t *Triangulation) ConcaveHull(tooLong float64) []int32 {
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	46 var (
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	47 minX float64 = math.MaxFloat64
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	48 minY float64 = math.MaxFloat64
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	49 maxX float64 = -math.MaxFloat64
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	50 maxY float64 = -math.MaxFloat64
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	51 )
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	52
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	53 linear := func(x1, y1, x2, y2 float64) func(float64) float64 {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	54 // y1 = x1*m + b
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	55 // y2 = x2*m + b
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	56 // b = y1 - x1*m
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	57 // y1-y2 = (x1-x2)*m
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	58 // m = (y1-y2)/(x1-x2) for x1 != x2
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	59
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	60 if x1 == x2 {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	61 return func(float64) float64 { return (y1 + y2) * 0.5 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	62 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	63
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	64 m := (y1 - y2) / (x1 - x2)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	65 b := y1 - x1*m
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	66
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	67 return func(x float64) float64 { return m*x + b }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	68 }
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	69
3609 e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	70 tooLong *= tooLong
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	71
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	72 var candidates []int32
3609 e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	73
e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	74 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	75 idx := i * 3
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	76 var max float64
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	77 vs := t.Triangles[idx : idx+3]
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	78 for j, vj := range vs {
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	79 k := (j + 1) % 3
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	80 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	81 max = l
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 }
3609 e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	84 if max > tooLong {
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	85 candidates = append(candidates, int32(i))
3609 e1021fd60190 Removed statistics from elimination of triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3604 diff changeset	86 }
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	87 }
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 removed := map[int32]bool{}
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 isBorder := func(n int32) bool {
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	92 n *= 3
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	93 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	94 e := n + i
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	95 if o := t.Halfedges[e]; o < 0 \|\| removed[o/3] {
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	96 return true
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	97 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	98 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	99 return false
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	100 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	101
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	102 for _, i := range candidates {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	103 vs := t.Triangles[i3 : i3+3]
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	104 for _, vj := range vs {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	105 p := t.Points[vj]
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	106 minX = math.Min(p.X, minX)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	107 maxX = math.Max(p.X, maxX)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	108 minY = math.Min(p.Y, minY)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	109 maxY = math.Max(p.Y, maxY)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	110 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	111 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	112
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	113 xf := linear(minX, 0, maxX, 1500)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	114 yf := linear(minY, 1500, maxY, 0)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	115
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	116 f, err := os.Create("/tmp/prehull.svg")
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	117 if err == nil {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	118 canvas := svg.New(f)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	119 canvas.Start(1500, 1500)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	120
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	121 for _, i := range candidates {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	122 var style string
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	123 if isBorder(i) {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	124 style = "stroke:red"
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	125 } else {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	126 style = "stroke:black"
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	127 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	128 vs := t.Triangles[i3 : i3+3]
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	129 for j, vj := range vs {
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	130 p0 := t.Points[vj]
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	131 p1 := t.Points[vs[(j+1)%3]]
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	132
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	133 x1 := int(math.Floor(xf(p0.X)))
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	134 y1 := int(math.Floor(yf(p0.Y)))
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	135 x2 := int(math.Floor(xf(p1.X)))
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	136 y2 := int(math.Floor(yf(p1.Y)))
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	137 canvas.Line(x1, y1, x2, y2, style)
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	138 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	139
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	140 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	141 canvas.End()
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	142 f.Close()
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	143 }
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	144
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	145 var newCandidates []int32
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	146
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	147 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	148 for len(candidates) > 0 {
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	149
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	150 oldRemoved := len(removed)
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	151
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	152 for _, i := range candidates {
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	153
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	154 if isBorder(i) {
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	155 removed[i] = true
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	156 } else {
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	157 newCandidates = append(newCandidates, i)
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	158 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	159 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	160
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	161 if oldRemoved == len(removed) {
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	162 break
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	163 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	164
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	165 candidates = newCandidates
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	166 newCandidates = newCandidates[:0]
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	167 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	168
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	169 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	170 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	171 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	172
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	173 var edges [][2]int32
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	174
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	175 for i, num := int32(0), int32(len(t.Triangles)/3); i < num; i++ {
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	176 if removed[i] {
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	177 continue
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	178 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	179 n := i * 3
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	180 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	181 e := n + j
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	182 if t.Halfedges[e] < 0 \|\| removed[e/3] {
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	183 //if t.Halfedges[e] < 0 {
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	184 edges = append(edges, [2]int32{
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	185 t.Triangles[e],
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	186 t.Triangles[n+(j+1)%3],
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	187 })
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	188 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	189 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	190 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	191
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	192 for i := range edges {
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	193 fmt.Printf("%d - %d\n", edges[i][0], edges[i][1])
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	194 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	195
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	196 log.Printf("num vertices: %d\n", len(t.Points))
1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	197
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	198 log.Printf("num of border triangles: %d\n", len(edges))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	199 log.Printf("len convex hull: %d\n", len(t.ConvexHull))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	200
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	201 f, err = os.Create("/tmp/hull.svg")
3621 2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	202 if err == nil {
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	203
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	204 canvas := svg.New(f)
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	205 canvas.Start(1500, 1500)
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	206
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	207 for i := range edges {
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	208 p0 := t.Points[edges[i][0]]
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	209 p1 := t.Points[edges[i][1]]
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	210 x1 := int(math.Floor(xf(p0.X)))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	211 y1 := int(math.Floor(yf(p0.Y)))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	212 x2 := int(math.Floor(xf(p1.X)))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	213 y2 := int(math.Floor(yf(p1.Y)))
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	214 canvas.Line(x1, y1, x2, y2, "stroke:black")
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	215 }
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	216
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	217 canvas.End()
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	218 f.Close()
2893ee8ce06f concave hulls for single beam scans ... WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3609 diff changeset	219 }
3623 1973fa69b2bb More SVG debug output. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3621 diff changeset	220 log.Println("after draw")
3604 6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	221 return nil
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	222 }
6248a4bc10c7 Moved triangle elimination to triangulation code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	223
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	224 func (t *Triangulation) TriangleSlices() [][]int32 {
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	225 sl := make([][]int32, len(t.Triangles)/3)
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	226 var j int
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	227 for i := range sl {
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	228 sl[i] = t.Triangles[j : j+3]
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	229 j += 3
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	230 }
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	231 return sl
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	232 }
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 func (t Triangulation) Tin() Tin {
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	235
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	236 min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	237 max := Vertex{-math.MaxFloat64, -math.MaxFloat64, -math.MaxFloat64}
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	238
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	239 vertices := t.Points
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	240
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	241 for _, v := range vertices {
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	242 min.Minimize(v)
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	243 max.Maximize(v)
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	244 }
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	245
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	246 return &Tin{
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	247 Vertices: vertices,
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	248 Triangles: t.TriangleSlices(),
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	249 Min: min,
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	250 Max: max,
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	251 }
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	252 }
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	253
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	254 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	255 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	256 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	257 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	258 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	259 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	260 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	261 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	262 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	263 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	264 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	265 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	266
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	267 // 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	268 // 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	269 // 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	270 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	271 // verify halfedges
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	272 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	273 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	274 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	275 }
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	276 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	277 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	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
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	281 // 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	282 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	283 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	284 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	285 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	286 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	287 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	288 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	289 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	290
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	291 // 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	292 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	293 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	294 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	295 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	296 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	297
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	298 return nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	299 }

Mercurial > gemma

annotate pkg/octree/triangulation.go @ 3632:943c454d5633 single-beam