Mercurial > gemma
changeset 3634:db7136854a51 single-beam
Hash the vertices of the concave hull together.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Tue, 11 Jun 2019 18:20:41 +0200 |
parents | cfb4e01f2b7f |
children | 2a4216c81e7b |
files | 3rdpartylibs.sh pkg/octree/triangulation.go |
diffstat | 2 files changed, 71 insertions(+), 102 deletions(-) [+] |
line wrap: on
line diff
--- a/3rdpartylibs.sh Tue Jun 11 14:58:39 2019 +0200 +++ b/3rdpartylibs.sh Tue Jun 11 18:20:41 2019 +0200 @@ -44,7 +44,8 @@ go get -u -v gonum.org/v1/gonum/stat # BSD-3-Clause -go get -u -v github.com/ajstarks/svgo +# Only needed when generating SVG graphics for debugging. +# 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
--- a/pkg/octree/triangulation.go Tue Jun 11 14:58:39 2019 +0200 +++ b/pkg/octree/triangulation.go Tue Jun 11 18:20:41 2019 +0200 @@ -23,9 +23,6 @@ "fmt" "log" "math" - "os" - - svg "github.com/ajstarks/svgo" ) type Triangulation struct { @@ -43,29 +40,6 @@ } 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 @@ -99,49 +73,6 @@ 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 log.Printf("info: candidates: %d\n", len(candidates)) @@ -170,7 +101,22 @@ log.Printf("info: triangles: %d\n", len(t.Triangles)/3) log.Printf("info: triangles to remove: %d\n", len(removed)) - var edges [][2]int32 + type edge struct { + a, b int32 + prev, next *edge + } + + isClosed := func(e *edge) bool { + for curr := e.next; curr != nil; curr = curr.next { + if curr == e { + return true + } + } + return false + } + + open := map[int32]*edge{} + var rings []*edge for i, num := int32(0), int32(len(t.Triangles)/3); i < num; i++ { if removed[i] { @@ -180,45 +126,67 @@ for j := int32(0); j < 3; j++ { e := n + j if f := t.Halfedges[e]; f < 0 || removed[f/3] { - //if t.Halfedges[e] < 0 { - edges = append(edges, [2]int32{ - t.Triangles[e], - t.Triangles[n+(j+1)%3], - }) + a := t.Triangles[e] + b := t.Triangles[n+(j+1)%3] + + curr := &edge{a: a, b: b} + + if old := open[a]; old != nil { + delete(open, a) + if old.a == a { + old.prev = curr + curr.next = old + } else { + old.next = curr + curr.prev = old + } + + if isClosed(old) { + rings = append(rings, old) + } + } else { + open[a] = curr + } + + if old := open[b]; old != nil { + delete(open, b) + if old.b == b { + old.next = curr + curr.prev = old + } else { + old.prev = curr + curr.next = old + } + + if isClosed(old) { + rings = append(rings, old) + } + } else { + open[b] = curr + } } } } - for i := range edges { - fmt.Printf("%d - %d\n", edges[i][0], edges[i][1]) + if len(open) > 0 { + log.Printf("warn: open vertices left: %d\n", len(open)) + } + + if len(rings) == 0 { + log.Println("warn: no ring found") + return nil } - 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) + curr := rings[0] + vertices := []int32{curr.a, curr.b} - 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") - } + for curr = curr.next; curr != rings[0]; curr = curr.next { + vertices = append(vertices, curr.b) + } - canvas.End() - f.Close() - } - log.Println("after draw") - return nil + log.Printf("length of boundary: %d\n", len(vertices)) + + return vertices } func (t *Triangulation) TriangleSlices() [][]int32 {