changeset 4545:e7970d84cb4f iso-areas

Stitch together arcs on cuts.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Fri, 27 Sep 2019 17:13:29 +0200
parents e5ae16f6d846
children a3f1d92b8597
files cmd/isoareas/main.go
diffstat 1 files changed, 83 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/cmd/isoareas/main.go	Fri Sep 27 13:21:20 2019 +0200
+++ b/cmd/isoareas/main.go	Fri Sep 27 17:13:29 2019 +0200
@@ -94,7 +94,7 @@
 	index int32
 }
 
-func glue(a, b octree.LineStringZ) (octree.LineStringZ, bool) {
+func glue(a, b octree.LineStringZ) octree.LineStringZ {
 
 	a1, a2 := a[0], a[len(a)-1]
 	b1, b2 := b[0], b[len(b)-1]
@@ -103,14 +103,14 @@
 		c := make(octree.LineStringZ, len(a)-1+len(b))
 		copy(c, b)
 		copy(c[len(b):], a[1:])
-		return c, true
+		return c
 	}
 
 	if a2.EpsEquals(b1) {
 		c := make(octree.LineStringZ, len(a)-1+len(b))
 		copy(c, a)
 		copy(c[len(a):], b[1:])
-		return c, true
+		return c
 	}
 
 	if a1.EpsEquals(b1) {
@@ -118,7 +118,7 @@
 		copy(c, b)
 		c[:len(b)].Reverse()
 		copy(c[len(b):], a[1:])
-		return c, true
+		return c
 	}
 
 	if a2.EpsEquals(b2) {
@@ -126,15 +126,71 @@
 		copy(c, a)
 		copy(c[len(a):], b[:len(b)-1])
 		c[len(a):].Reverse()
-		return c, true
+		return c
 	}
 
-	return nil, false
+	return nil
 }
 
-func connectArcs(tri *octree.Triangulation, cut []indexedArc, arcs *[]octree.LineStringZ) {
+func connectArcs(tri *octree.Triangulation, cuts []indexedArc, arcs *[]octree.LineStringZ) {
+
+	origLen := int32(len(*arcs))
+
+	for i := range cuts {
+		if cuts[i].arc >= origLen {
+			// already has a connected arc assigned.
+			continue
+		}
+
+		line := (*arcs)[cuts[i].arc]
+
+		var modified []int
+		visited := map[int32]struct{}{}
+
+		var recursive func(int32)
+		recursive = func(idx int32) {
+			visited[idx] = struct{}{}
+
+			ns := neighbors(tri, idx)
+			for _, n := range ns {
+				n /= 3
+				if _, already := visited[n]; already {
+					continue
+				}
 
-	// TODO: Implement me!
+				arcIdx := findArc(n, cuts)
+				if arcIdx == -1 {
+					continue
+				}
+				arc := cuts[arcIdx].arc
+				if arc >= origLen {
+					// already a new arc.
+					continue
+				}
+				oline := (*arcs)[arc]
+
+				nline := glue(line, oline)
+				if nline == nil {
+					// not joinable
+					continue
+				}
+				line = nline
+				modified = append(modified, arcIdx)
+				recursive(cuts[arcIdx].index)
+			}
+		}
+		recursive(cuts[i].index)
+		if len(modified) > 0 {
+			// alloc a new line an fix the references.
+			nidx := int32(len(*arcs))
+			*arcs = append(*arcs, line)
+			cuts[i].arc = nidx
+			for _, j := range modified {
+				cuts[j].arc = nidx
+			}
+		}
+
+	}
 }
 
 func intersectTriangles(tri *octree.Triangulation, heights []float64) [][]octree.LineStringZ {
@@ -198,6 +254,9 @@
 
 		pb := polygonBuilder{open: list.New()}
 
+		usedArcs := map[int32]struct{}{}
+		var dupes int
+
 		var isolated, inside int
 	allInClass:
 		for _, idx := range c {
@@ -231,11 +290,19 @@
 							if l < 0 || l >= len(cuts) {
 								continue
 							}
+							arcIdx := findArc(ns[j], cuts[l])
+							if arcIdx == -1 {
+								continue
+							}
+							aIdx := cuts[l][arcIdx].arc
+							if _, already := usedArcs[aIdx]; already {
+								dupes++
+								continue
+							}
+							usedArcs[aIdx] = struct{}{}
 
-							if arc := findArc(ns[j], cuts[l]); arc >= 0 {
-								curr = arcs[arc]
-								break
-							}
+							curr = arcs[aIdx]
+							break
 						}
 
 						if curr == nil {
@@ -293,8 +360,8 @@
 			}
 		}
 
-		log.Printf("\t%d: inside: %d / isolated: %d open: %d closed: %d\n",
-			i, inside, isolated, pb.open.Len(), len(pb.polygons))
+		log.Printf("\t%d: inside: %d / isolated: %d open: %d closed: %d dupes: %d\n",
+			i, inside, isolated, pb.open.Len(), len(pb.polygons), dupes)
 
 		result[i] = pb.polygons
 	}
@@ -326,7 +393,7 @@
 	return t.Halfedges[idx : idx+3]
 }
 
-func findArc(needle int32, haystack []indexedArc) int32 {
+func findArc(needle int32, haystack []indexedArc) int {
 	lo, hi := 0, len(haystack)-1
 	for lo <= hi {
 		mid := (hi-lo)/2 + lo
@@ -336,7 +403,7 @@
 		case v > needle:
 			hi = mid - 1
 		default:
-			return haystack[mid].arc
+			return mid
 		}
 	}
 	return -1