changeset 648:cf62cb84fa23

Cross sections: Added a naive O(N^2) algorithm to join the neighbored line segments.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Thu, 13 Sep 2018 16:54:52 +0200
parents 620a65f11b33
children 2745ac1ebe1e
files pkg/controllers/cross.go pkg/models/cross.go
diffstat 2 files changed, 72 insertions(+), 6 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/controllers/cross.go	Thu Sep 13 14:11:33 2018 +0200
+++ b/pkg/controllers/cross.go	Thu Sep 13 16:54:52 2018 +0200
@@ -41,7 +41,7 @@
 	}
 	defer rows.Close()
 
-	var segments []models.GeoJSONLineCoordinatesZ
+	var segments models.GeoJSONMultiLineCoordinatesZ
 
 	for rows.Next() {
 		var segment models.GeoJSONLineCoordinatesZ
@@ -55,13 +55,13 @@
 		return
 	}
 
-	// TODO: Join the segments.
+	joined := segments.Join()
 
 	jr = JSONResult{
 		Result: &models.CrossSectionOutput{
 			Type:        "Feature",
 			Geometry:    "MultLineString",
-			Coordinates: segments,
+			Coordinates: joined,
 		},
 	}
 
--- a/pkg/models/cross.go	Thu Sep 13 14:11:33 2018 +0200
+++ b/pkg/models/cross.go	Thu Sep 13 16:54:52 2018 +0200
@@ -6,6 +6,7 @@
 	"encoding/json"
 	"errors"
 	"fmt"
+	"log"
 	"math"
 	"time"
 )
@@ -39,6 +40,8 @@
 	GeoJSONLineCoordinates  []GeoJSONCoordinate
 	GeoJSONLineCoordinatesZ []GeoJSONCoordinateZ
 
+	GeoJSONMultiLineCoordinatesZ []GeoJSONLineCoordinatesZ
+
 	CrossSectionInput struct {
 		Type        GeoJSONFeature              `json:"type"`
 		Geometry    GeoJSONLineStringType       `json:"geometry"`
@@ -47,9 +50,9 @@
 	}
 
 	CrossSectionOutput struct {
-		Type        string                    `json:"type"`
-		Geometry    string                    `json:"geometry"`
-		Coordinates []GeoJSONLineCoordinatesZ `json:"coordinates"`
+		Type        string                       `json:"type"`
+		Geometry    string                       `json:"geometry"`
+		Coordinates GeoJSONMultiLineCoordinatesZ `json:"coordinates"`
 	}
 )
 
@@ -212,3 +215,66 @@
 
 	return nil
 }
+
+func (cz GeoJSONCoordinateZ) equals(other GeoJSONCoordinateZ) bool {
+	const (
+		xyEps = 1e-7
+		zEps  = 1e-5
+	)
+	return math.Abs(cz.Lat-other.Lat) < 0.000000001 &&
+		math.Abs(cz.Lon-other.Lon) < xyEps &&
+		math.Abs(cz.Z-other.Z) < zEps
+}
+
+func (cz GeoJSONCoordinateZ) mid(other GeoJSONCoordinateZ) GeoJSONCoordinateZ {
+	return GeoJSONCoordinateZ{
+		Lon: (cz.Lon + other.Lon) * 0.5,
+		Lat: (cz.Lat + other.Lat) * 0.5,
+		Z:   (cz.Z + other.Z) * 0.5,
+	}
+}
+
+func (ml GeoJSONMultiLineCoordinatesZ) Join() GeoJSONMultiLineCoordinatesZ {
+
+	if len(ml) < 2 {
+		return ml
+	}
+
+	start := time.Now()
+
+	lists := make(GeoJSONMultiLineCoordinatesZ, len(ml))
+	copy(lists, ml)
+
+next:
+	for j := 0; j < len(lists); {
+		front := lists[j]
+		tail := front[len(front)-1]
+
+		for i := 0; i < len(lists); i++ {
+			if i == j {
+				continue
+			}
+			curr := lists[i]
+			head := curr[0]
+			if tail.equals(head) {
+				n := make(GeoJSONLineCoordinatesZ, len(front)+len(curr)-1)
+				copy(n, front[:len(front)-1])
+				n[len(front)-1] = head.mid(tail)
+				copy(n[len(front):], curr[1:])
+				lists[j] = n
+				if i < len(lists)-1 {
+					copy(lists[i:], lists[i+1:])
+				}
+				lists[len(lists)-1] = nil
+				lists = lists[:len(lists)-1]
+				continue next
+			}
+		}
+		j++
+	}
+
+	log.Printf("joining took: %s\n", time.Since(start))
+	log.Printf("segments before/after: %d %d\n", len(ml), len(lists))
+
+	return lists
+}