# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1559745292 -7200
# Node ID 2893ee8ce06f99a068809e22b5b9de44c12ca324
# Parent  c03170a1c3334025d50397b5a99f3396b197019c
concave hulls for single beam scans ... WIP.

diff -r c03170a1c333 -r 2893ee8ce06f 3rdpartylibs.sh
--- a/3rdpartylibs.sh	Wed Jun 05 15:47:30 2019 +0200
+++ b/3rdpartylibs.sh	Wed Jun 05 16:34:52 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 c03170a1c333 -r 2893ee8ce06f pkg/octree/triangulation.go
--- a/pkg/octree/triangulation.go	Wed Jun 05 15:47:30 2019 +0200
+++ b/pkg/octree/triangulation.go	Wed Jun 05 16:34:52 2019 +0200
@@ -23,6 +23,9 @@
 	"fmt"
 	"log"
 	"math"
+	"os"
+
+	svg "github.com/ajstarks/svgo"
 )
 
 type Triangulation struct {
@@ -43,7 +46,7 @@
 
 	tooLong *= tooLong
 
-	var oldCandidates []int32
+	var candidates []int32
 
 	for i, num := 0, len(t.Triangles)/3; i < num; i++ {
 		idx := i * 3
@@ -56,7 +59,7 @@
 			}
 		}
 		if max > tooLong {
-			oldCandidates = append(oldCandidates, int32(i))
+			candidates = append(candidates, int32(i))
 		}
 	}
 
@@ -66,7 +69,7 @@
 		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
 			}
 		}
@@ -75,12 +78,12 @@
 
 	var newCandidates []int32
 
-	for len(oldCandidates) > 0 {
-		log.Printf("candidates: %d\n", len(oldCandidates))
+	for len(candidates) > 0 {
+		log.Printf("info: candidates: %d\n", len(candidates))
 
 		oldRemoved := len(removed)
 
-		for _, i := range oldCandidates {
+		for _, i := range candidates {
 
 			if isBorder(i) {
 				removed[i] = true
@@ -93,12 +96,98 @@
 			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] {
+				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 of border triangles: %d\n", len(edges))
+	log.Printf("len convex hull: %d\n", len(t.ConvexHull))
+
+	var (
+		minX float64 = math.MaxFloat64
+		minY float64 = math.MaxFloat64
+		maxX float64 = -math.MaxFloat64
+		maxY float64 = -math.MaxFloat64
+	)
+
+	for i := range edges {
+		p0 := t.Points[edges[i][0]]
+		p1 := t.Points[edges[i][1]]
+
+		minX = math.Min(p0.X, minX)
+		maxX = math.Max(p0.X, maxX)
+		minY = math.Min(p0.Y, minY)
+		maxY = math.Max(p0.Y, maxY)
+
+		minX = math.Min(p1.X, minX)
+		maxX = math.Max(p1.X, maxX)
+		minY = math.Min(p1.Y, minY)
+		maxY = math.Max(p1.Y, maxY)
+	}
+	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 }
+	}
+	xf := linear(minX, 0, maxX, 1499)
+	yf := linear(minY, 0, maxY, 1499)
+
+	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()
+	}
 	return nil
 }