# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1539003157 -7200
# Node ID ae1531e00344aa3e8986787a5074f0a4ba864733
# Parent  71445b091415dbd949be0b5b366bd8e6a7a1685c
Merged line merging from geo-style branch into default (where it belongs).

diff -r 71445b091415 -r ae1531e00344 cmd/octree2contour/main.go
--- a/cmd/octree2contour/main.go	Mon Oct 08 14:41:56 2018 +0200
+++ b/cmd/octree2contour/main.go	Mon Oct 08 14:52:37 2018 +0200
@@ -35,6 +35,7 @@
 				lines = append(lines, line)
 			}
 		})
+		lines = lines.Merge()
 		results <- result{h, lines}
 	}
 }
@@ -49,6 +50,7 @@
 				lines = append(lines, line)
 			}
 		})
+		lines = lines.Merge()
 		return []result{{*step, lines}}
 	}
 
diff -r 71445b091415 -r ae1531e00344 pkg/octree/vertex.go
--- a/pkg/octree/vertex.go	Mon Oct 08 14:41:56 2018 +0200
+++ b/pkg/octree/vertex.go	Mon Oct 08 14:52:37 2018 +0200
@@ -349,6 +349,123 @@
 	return buf.Bytes()
 }
 
+// Join joins two lines leaving the first of the secoung out.
+func (ls LineStringZ) Join(other LineStringZ) LineStringZ {
+	nline := make(LineStringZ, len(ls)+len(other)-1)
+	copy(nline, ls)
+	copy(nline[len(ls):], other[1:])
+	return nline
+}
+
+func (mls MultiLineStringZ) Merge() MultiLineStringZ {
+
+	var out MultiLineStringZ
+
+	min := Vertex{math.MaxFloat64, math.MaxFloat64, math.MaxFloat64}
+
+	for _, line := range mls {
+		for _, v := range line {
+			min.Minimize(v)
+		}
+	}
+
+	type point struct {
+		x int64
+		y int64
+	}
+
+	const precision = 1e7
+
+	quant := func(v Vertex) point {
+		return point{
+			x: int64(math.Round((v.X - min.X) * precision)),
+			y: int64(math.Round((v.Y - min.Y) * precision)),
+		}
+	}
+
+	heads := make(map[point]*[]LineStringZ)
+
+	for _, line := range mls {
+		if len(line) < 2 {
+			out = append(out, line)
+			continue
+		}
+		head := quant(line[0])
+		tail := quant(line[len(line)-1])
+		if head == tail { // its already a ring
+			out = append(out, line)
+			continue
+		}
+
+		if hs := heads[tail]; hs != nil {
+			l := len(*hs)
+			last := (*hs)[l-1]
+			if l == 1 {
+				delete(heads, tail)
+			} else {
+				(*hs)[l-1] = nil
+				*hs = (*hs)[:l-1]
+			}
+			line = line.Join(last)
+
+			if head == quant(line[len(line)-1]) { // its a ring
+				out = append(out, line)
+				continue
+			}
+		}
+
+		if hs := heads[head]; hs != nil {
+			*hs = append(*hs, line)
+		} else {
+			heads[head] = &[]LineStringZ{line}
+		}
+	}
+
+again:
+	for head, lines := range heads {
+		for i, line := range *lines {
+			tail := quant(line[len(line)-1])
+			if hs := heads[tail]; hs != nil {
+				l := len(*hs)
+				last := (*hs)[l-1]
+				if l == 1 {
+					delete(heads, tail)
+				} else {
+					(*hs)[l-1] = nil
+					*hs = (*hs)[:l-1]
+				}
+				line = line.Join(last)
+
+				if head == quant(line[len(line)-1]) { // its a ring
+					out = append(out, line)
+					// remove from current lines
+					copy((*lines)[i:], (*lines)[i+1:])
+					(*lines)[len(*lines)-1] = nil
+					*lines = (*lines)[:len(*lines)-1]
+				} else {
+					// overwrite in current lines
+					(*lines)[i] = line
+				}
+				goto again
+			}
+		}
+	}
+
+	rings := len(out)
+
+	// The rest are open line strings.
+	for _, lines := range heads {
+		for _, line := range *lines {
+			out = append(out, line)
+		}
+	}
+
+	log.Printf("segments before/after merge: %d/%d (%d rings)\n",
+		len(mls), len(out), rings)
+
+	return out
+}
+
 func (a Box2D) Intersects(b Box2D) bool {
 	return !(a.X2 < a.X1 || a.X2 < b.X1 ||
 		a.Y2 < a.Y1 || a.Y2 < b.Y1)