gemma: pkg/mesh/triangulator.go annotate

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

Finsh serializing v2 meshes.

author	Sascha L. Teichmann <sascha.teichmann@intevation.de>
date	Mon, 12 Feb 2024 02:27:41 +0100
parents	f4abfd0ee8ad
children

rev	line source
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	1 // Copyright (C) 2018 Michael Fogleman
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	2 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	3 // Permission is hereby granted, free of charge, to any person obtaining
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	4 // a copy of this software and associated documentation files (the "Software"),
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	5 // to deal in the Software without restriction, including without limitation
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	6 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	7 // and/or sell copies of the Software, and to permit persons to whom the
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	8 // Software is furnished to do so, subject to the following conditions:
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	9 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	10 // The above copyright notice and this permission notice shall be included
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	11 // in all copies or substantial portions of the Software.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	12 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	14 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	16 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	19
4827 f4abfd0ee8ad Renamed octree package to mesh as there is no octree any more. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4151 diff changeset	20 package mesh
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	21
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	22 import (
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	23 "errors"
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	24 "math"
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	25 "sort"
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 triangulator 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 squaredDistances []float64
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	31 ids []int32
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	32 center Vertex
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	33 triangles []int32
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	34 halfedges []int32
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	35 trianglesLen int
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	36 hull *node
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	37 hash []*node
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	38 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	39
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	40 func newTriangulator(points []Vertex) *triangulator {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	41 return &triangulator{points: points}
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	42 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	43
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	44 // sorting a triangulator sorts the `ids` such that the referenced points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	45 // are in order by their distance to `center`
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	46 func (tri *triangulator) Len() int {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	47 return len(tri.points)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	48 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	49
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	50 func (tri *triangulator) Swap(i, j int) {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	51 tri.ids[i], tri.ids[j] = tri.ids[j], tri.ids[i]
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	52 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	53
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	54 func (tri *triangulator) Less(i, j int) bool {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	55 d1 := tri.squaredDistances[tri.ids[i]]
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	56 d2 := tri.squaredDistances[tri.ids[j]]
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	57 if d1 != d2 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	58 return d1 < d2
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	59 }
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	60 p1 := tri.points[tri.ids[i]]
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	61 p2 := tri.points[tri.ids[j]]
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	62 if p1.X != p2.X {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	63 return p1.X < p2.X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	64 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	65 return p1.Y < p2.Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	66 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	67
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	68 func (tri *triangulator) triangulate() error {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	69 points := tri.points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	70
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	71 n := len(points)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	72 if n == 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	73 return nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	74 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	75
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	76 tri.ids = make([]int32, n)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	77
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	78 // compute bounds
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	79 x0 := points[0].X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	80 y0 := points[0].Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	81 x1 := points[0].X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	82 y1 := points[0].Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	83 for i, p := range points {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	84 if p.X < x0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	85 x0 = p.X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	86 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	87 if p.X > x1 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	88 x1 = p.X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	89 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	90 if p.Y < y0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	91 y0 = p.Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	92 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	93 if p.Y > y1 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	94 y1 = p.Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	95 }
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	96 tri.ids[i] = int32(i)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	97 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	98
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	99 var i0, i1, i2 int32
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	100
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	101 // pick a seed point close to midpoint
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	102 m := Vertex{X: (x0 + x1) / 2, Y: (y0 + y1) / 2}
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	103 minDist := infinity
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	104 for i, p := range points {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	105 d := p.SquaredDistance2D(m)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	106 if d < minDist {
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	107 i0 = int32(i)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	108 minDist = d
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	109 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	110 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	111
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	112 // find point closest to seed point
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	113 minDist = infinity
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	114 for i, p := range points {
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	115 if int32(i) == i0 {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	116 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	117 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	118 d := p.SquaredDistance2D(points[i0])
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	119 if d > 0 && d < minDist {
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	120 i1 = int32(i)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	121 minDist = d
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	122 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	123 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	124
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	125 // find the third point which forms the smallest circumcircle
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	126 minRadius := infinity
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	127 for i, p := range points {
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	128 if int32(i) == i0 \|\| int32(i) == i1 {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	129 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	130 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	131 r := circumradius(points[i0], points[i1], p)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	132 if r < minRadius {
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	133 i2 = int32(i)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	134 minRadius = r
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	135 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	136 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	137 if minRadius == infinity {
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	138 return errors.New("no delaunay triangulation exists for this input")
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	139 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	140
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	141 // swap the order of the seed points for counter-clockwise orientation
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	142 if area(points[i0], points[i1], points[i2]) < 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	143 i1, i2 = i2, i1
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
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	146 tri.center = circumcenter(points[i0], points[i1], points[i2])
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 // sort the points by distance from the seed triangle circumcenter
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	149 tri.squaredDistances = make([]float64, n)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	150 for i, p := range points {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	151 tri.squaredDistances[i] = p.SquaredDistance2D(tri.center)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	152 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	153 sort.Sort(tri)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	154
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	155 // initialize a hash table for storing edges of the advancing convex hull
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	156 hashSize := int(math.Ceil(math.Sqrt(float64(n))))
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	157 tri.hash = make([]*node, hashSize)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	158
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	159 // initialize a circular doubly-linked list that will hold an advancing convex hull
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	160 nodes := make([]node, n)
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 e := newNode(nodes, i0, nil)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	163 e.t = 0
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	164 tri.hashEdge(e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	165
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	166 e = newNode(nodes, i1, e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	167 e.t = 1
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	168 tri.hashEdge(e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	169
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	170 e = newNode(nodes, i2, e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	171 e.t = 2
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	172 tri.hashEdge(e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	173
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	174 tri.hull = e
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	175
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	176 maxTriangles := 2*n - 5
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	177 tri.triangles = make([]int32, maxTriangles*3)
4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	178 tri.halfedges = make([]int32, maxTriangles*3)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	179
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	180 tri.addTriangle(i0, i1, i2, -1, -1, -1)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	181
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	182 pp := Vertex{X: infinity, Y: infinity}
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	183 for k := 0; k < n; k++ {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	184 i := tri.ids[k]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	185 p := points[i]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	186
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	187 // skip nearly-duplicate points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	188 if p.SquaredDistance2D(pp) < eps {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	189 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	190 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	191 pp = p
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	192
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	193 // skip seed triangle points
2484 4fa92d468164 Use fogleman's triangulation. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2483 diff changeset	194 if i == int32(i0) \|\| i == int32(i1) \|\| i == int32(i2) {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	195 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	196 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	197
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	198 // find a visible edge on the convex hull using edge hash
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	199 var start *node
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	200 key := tri.hashKey(p)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	201 for j := 0; j < len(tri.hash); j++ {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	202 start = tri.hash[key]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	203 if start != nil && start.i >= 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	204 break
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	205 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	206 key++
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	207 if key >= len(tri.hash) {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	208 key = 0
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	209 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	210 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	211 start = start.prev
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	212
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	213 e := start
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	214 for area(p, points[e.i], points[e.next.i]) >= 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	215 e = e.next
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	216 if e == start {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	217 e = nil
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	218 break
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	219 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	220 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	221 if e == nil {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	222 // likely a near-duplicate point; skip it
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	223 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	224 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	225 walkBack := e == start
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	226
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	227 // add the first triangle from the point
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	228 t := tri.addTriangle(e.i, i, e.next.i, -1, -1, e.t)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	229 e.t = t // keep track of boundary triangles on the hull
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	230 e = newNode(nodes, i, e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	231
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	232 // recursively flip triangles from the point until they satisfy the Delaunay condition
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	233 e.t = tri.legalize(t + 2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	234
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	235 // walk forward through the hull, adding more triangles and flipping recursively
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	236 q := e.next
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	237 for area(p, points[q.i], points[q.next.i]) < 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	238 t = tri.addTriangle(q.i, i, q.next.i, q.prev.t, -1, q.t)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	239 q.prev.t = tri.legalize(t + 2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	240 tri.hull = q.remove()
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	241 q = q.next
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	242 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	243
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	244 if walkBack {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	245 // walk backward from the other side, adding more triangles and flipping
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	246 q := e.prev
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	247 for area(p, points[q.prev.i], points[q.i]) < 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	248 t = tri.addTriangle(q.prev.i, i, q.i, -1, q.t, q.prev.t)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	249 tri.legalize(t + 2)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	250 q.prev.t = t
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	251 tri.hull = q.remove()
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	252 q = q.prev
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	253 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	254 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	255
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	256 // save the two new edges in the hash table
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	257 tri.hashEdge(e)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	258 tri.hashEdge(e.prev)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	259 }
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 tri.triangles = tri.triangles[:tri.trianglesLen]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	262 tri.halfedges = tri.halfedges[:tri.trianglesLen]
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 nil
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
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	267 func (tri *triangulator) hashKey(point Vertex) int {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	268 d := point.Sub2D(tri.center)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	269 return int(pseudoAngle(d.X, d.Y) * float64(len(tri.hash)))
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	270 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	271
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	272 func (tri triangulator) hashEdge(e node) {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	273 tri.hash[tri.hashKey(tri.points[e.i])] = e
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	274 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	275
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	276 func (tri *triangulator) addTriangle(i0, i1, i2, a, b, c int32) int32 {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	277 i := int32(tri.trianglesLen)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	278 tri.triangles[i] = i0
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	279 tri.triangles[i+1] = i1
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	280 tri.triangles[i+2] = i2
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	281 tri.link(i, a)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	282 tri.link(i+1, b)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	283 tri.link(i+2, c)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	284 tri.trianglesLen += 3
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	285 return i
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	286 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	287
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	288 func (tri *triangulator) link(a, b int32) {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	289 tri.halfedges[a] = b
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	290 if b >= 0 {
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	291 tri.halfedges[b] = a
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	292 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	293 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	294
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	295 func (tri *triangulator) legalize(a int32) int32 {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	296 // if the pair of triangles doesn't satisfy the Delaunay condition
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	297 // (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	298 // then do the same check/flip recursively for the new pair of triangles
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	299 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	300 // pl pl
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	301 // /\|\|\ / \
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	302 // al/ \|\| \bl al/ \a
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	303 // / \|\| \ / \
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	304 // / a\|\|b \ flip /___ar___\
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	305 // p0\ \|\| /p1 => p0\---bl---/p1
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	306 // \ \|\| / \ /
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	307 // ar\ \|\| /br b\ /br
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	308 // \\|\|/ \ /
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	309 // pr pr
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	310
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	311 b := tri.halfedges[a]
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	312
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	313 a0 := a - a%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	314 b0 := b - b%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	315
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	316 al := a0 + (a+1)%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	317 ar := a0 + (a+2)%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	318 bl := b0 + (b+2)%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	319
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	320 if b < 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	321 return ar
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	322 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	323
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	324 p0 := tri.triangles[ar]
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	325 pr := tri.triangles[a]
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	326 pl := tri.triangles[al]
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	327 p1 := tri.triangles[bl]
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	328
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	329 illegal := inCircle(tri.points[p0], tri.points[pr], tri.points[pl], tri.points[p1])
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	330
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	331 if illegal {
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	332 tri.triangles[a] = p1
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	333 tri.triangles[b] = p0
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	334
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	335 // edge swapped on the other side of the hull (rare)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	336 // fix the halfedge reference
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	337 if tri.halfedges[bl] == -1 {
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	338 e := tri.hull
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	339 for {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	340 if e.t == bl {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	341 e.t = a
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	342 break
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	343 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	344 e = e.next
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	345 if e == tri.hull {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	346 break
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	347 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	348 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	349 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	350
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	351 tri.link(a, tri.halfedges[bl])
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	352 tri.link(b, tri.halfedges[ar])
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	353 tri.link(ar, bl)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	354
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	355 br := b0 + (b+1)%3
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	356
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	357 tri.legalize(a)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	358 return tri.legalize(br)
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	359 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	360
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	361 return ar
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	362 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	363
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	364 func (tri *triangulator) convexHull() []Vertex {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	365 var result []Vertex
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	366 e := tri.hull
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	367 for e != nil {
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	368 result = append(result, tri.points[e.i])
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	369 e = e.prev
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2484 diff changeset	370 if e == tri.hull {
2483 620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	371 break
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	372 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	373 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	374 return result
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	375 }

Mercurial > gemma

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