# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1560257174 -7200
# Node ID 943c454d5633066d2d6d1a807aee7bcd30a9ab9d
# Parent  1973fa69b2bb0f3dfd5bba8c29285fa9b61a6a04# Parent  3012d0b3badc17927f82eb040e042e367f881653
Merged default into single-beam branch.

diff -r 3012d0b3badc -r 943c454d5633 3rdpartylibs.sh
--- a/3rdpartylibs.sh	Wed Jun 05 18:50:54 2019 +0200
+++ b/3rdpartylibs.sh	Tue Jun 11 14:46:14 2019 +0200
@@ -44,6 +44,9 @@
 go get -u -v gonum.org/v1/gonum/stat
 # BSD-3-Clause
 
+go get -u -v github.com/ajstarks/svgo
+# Attribution 3.0 United States (CC BY 3.0 US)
+
 ## list of additional licenses that get fetched and installed as dependencies
 # github.com/fsnotify/fsnotify/ BSD-3-Clause
 # github.com/hashicorp/hcl/ MPL-2.0
diff -r 3012d0b3badc -r 943c454d5633 pkg/octree/triangulation.go
--- a/pkg/octree/triangulation.go	Wed Jun 05 18:50:54 2019 +0200
+++ b/pkg/octree/triangulation.go	Tue Jun 11 14:46:14 2019 +0200
@@ -23,6 +23,9 @@
 	"fmt"
 	"log"
 	"math"
+	"os"
+
+	svg "github.com/ajstarks/svgo"
 )
 
 type Triangulation struct {
@@ -40,10 +43,33 @@
 }
 
 func (t *Triangulation) ConcaveHull(tooLong float64) []int32 {
+	var (
+		minX float64 = math.MaxFloat64
+		minY float64 = math.MaxFloat64
+		maxX float64 = -math.MaxFloat64
+		maxY float64 = -math.MaxFloat64
+	)
+
+	linear := func(x1, y1, x2, y2 float64) func(float64) float64 {
+		// y1 = x1*m + b
+		// y2 = x2*m + b
+		// b = y1 - x1*m
+		// y1-y2 = (x1-x2)*m
+		// m = (y1-y2)/(x1-x2) for x1 != x2
+
+		if x1 == x2 {
+			return func(float64) float64 { return (y1 + y2) * 0.5 }
+		}
+
+		m := (y1 - y2) / (x1 - x2)
+		b := y1 - x1*m
+
+		return func(x float64) float64 { return m*x + b }
+	}
 
 	tooLong *= tooLong
 
-	var oldCandidates []int32
+	var candidates []int32
 
 	for i, num := 0, len(t.Triangles)/3; i < num; i++ {
 		idx := i * 3
@@ -56,7 +82,7 @@
 			}
 		}
 		if max > tooLong {
-			oldCandidates = append(oldCandidates, int32(i))
+			candidates = append(candidates, int32(i))
 		}
 	}
 
@@ -66,21 +92,64 @@
 		n *= 3
 		for i := int32(0); i < 3; i++ {
 			e := n + i
-			if t.Halfedges[e] == -1 || removed[e] {
+			if o := t.Halfedges[e]; o < 0 || removed[o/3] {
 				return true
 			}
 		}
 		return false
 	}
 
+	for _, i := range candidates {
+		vs := t.Triangles[i*3 : i*3+3]
+		for _, vj := range vs {
+			p := t.Points[vj]
+			minX = math.Min(p.X, minX)
+			maxX = math.Max(p.X, maxX)
+			minY = math.Min(p.Y, minY)
+			maxY = math.Max(p.Y, maxY)
+		}
+	}
+
+	xf := linear(minX, 0, maxX, 1500)
+	yf := linear(minY, 1500, maxY, 0)
+
+	f, err := os.Create("/tmp/prehull.svg")
+	if err == nil {
+		canvas := svg.New(f)
+		canvas.Start(1500, 1500)
+
+		for _, i := range candidates {
+			var style string
+			if isBorder(i) {
+				style = "stroke:red"
+			} else {
+				style = "stroke:black"
+			}
+			vs := t.Triangles[i*3 : i*3+3]
+			for j, vj := range vs {
+				p0 := t.Points[vj]
+				p1 := t.Points[vs[(j+1)%3]]
+
+				x1 := int(math.Floor(xf(p0.X)))
+				y1 := int(math.Floor(yf(p0.Y)))
+				x2 := int(math.Floor(xf(p1.X)))
+				y2 := int(math.Floor(yf(p1.Y)))
+				canvas.Line(x1, y1, x2, y2, style)
+			}
+
+		}
+		canvas.End()
+		f.Close()
+	}
+
 	var newCandidates []int32
 
-	for len(oldCandidates) > 0 {
-		log.Printf("candidates: %d\n", len(oldCandidates))
+	log.Printf("info: candidates: %d\n", len(candidates))
+	for len(candidates) > 0 {
 
 		oldRemoved := len(removed)
 
-		for _, i := range oldCandidates {
+		for _, i := range candidates {
 
 			if isBorder(i) {
 				removed[i] = true
@@ -93,12 +162,62 @@
 			break
 		}
 
-		oldCandidates = newCandidates
+		candidates = newCandidates
 		newCandidates = newCandidates[:0]
 	}
 
+	log.Printf("info: candidates left: %d\n", len(candidates))
+	log.Printf("info: triangles: %d\n", len(t.Triangles)/3)
 	log.Printf("info: triangles to remove: %d\n", len(removed))
 
+	var edges [][2]int32
+
+	for i, num := int32(0), int32(len(t.Triangles)/3); i < num; i++ {
+		if removed[i] {
+			continue
+		}
+		n := i * 3
+		for j := int32(0); j < 3; j++ {
+			e := n + j
+			if t.Halfedges[e] < 0 || removed[e/3] {
+				//if t.Halfedges[e] < 0 {
+				edges = append(edges, [2]int32{
+					t.Triangles[e],
+					t.Triangles[n+(j+1)%3],
+				})
+			}
+		}
+	}
+
+	for i := range edges {
+		fmt.Printf("%d - %d\n", edges[i][0], edges[i][1])
+	}
+
+	log.Printf("num vertices: %d\n", len(t.Points))
+
+	log.Printf("num of border triangles: %d\n", len(edges))
+	log.Printf("len convex hull: %d\n", len(t.ConvexHull))
+
+	f, err = os.Create("/tmp/hull.svg")
+	if err == nil {
+
+		canvas := svg.New(f)
+		canvas.Start(1500, 1500)
+
+		for i := range edges {
+			p0 := t.Points[edges[i][0]]
+			p1 := t.Points[edges[i][1]]
+			x1 := int(math.Floor(xf(p0.X)))
+			y1 := int(math.Floor(yf(p0.Y)))
+			x2 := int(math.Floor(xf(p1.X)))
+			y2 := int(math.Floor(yf(p1.Y)))
+			canvas.Line(x1, y1, x2, y2, "stroke:black")
+		}
+
+		canvas.End()
+		f.Close()
+	}
+	log.Println("after draw")
 	return nil
 }