changeset 5685:0ee8ace01b60 sr-v2

When sorting vertices by x/y take aspectio ratio of bbox into acount.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 12 Feb 2024 01:02:53 +0100
parents 536e842d9bfa
children c33a5354328d
files pkg/mesh/meshserialize_v2.go
diffstat 1 files changed, 37 insertions(+), 12 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/mesh/meshserialize_v2.go	Sun Feb 11 22:32:55 2024 +0100
+++ b/pkg/mesh/meshserialize_v2.go	Mon Feb 12 01:02:53 2024 +0100
@@ -65,20 +65,45 @@
 		indices[i] = int32(i)
 	}
 
-	slices.SortFunc(indices, func(a, b int32) int {
-		return cmp.Compare(vertices[a].X, vertices[b].X)
-	})
+	// Take aspect ratio of bbox into account.
+	width := s.tin.Max.X - s.tin.Min.X
+	height := s.tin.Max.Y - s.tin.Min.Y
+	if width == 0 || height == 0 {
+		return
+	}
 
-	n := int(math.Sqrt(float64(len(vertices))))
-	m := len(vertices) / n
+	// v = len(vertices)
+	// r = max(w, h)/min(w, h)
+	// n * t = v <=> n = v/t
+	// n / t = r <=> n = r*t
+	// v/t = r*t
+	// v = r*t^2
+	// v/r = t^2
+	// t = sqrt(v/r)
+	r := float64(max(width, height)) / float64(min(width, height))
+	t := int(math.Ceil(math.Sqrt(float64(len(vertices)) / r)))
+
+	var d1, d2 func(int32, int32) int
 
-	var (
-		up   = func(a, b int32) int { return cmp.Compare(vertices[a].Y, vertices[b].Y) }
-		down = func(a, b int32) int { return cmp.Compare(vertices[b].Y, vertices[a].Y) }
-	)
-	for p := indices; len(p) > 0; up, down = down, up {
-		l := min(len(p), m)
-		slices.SortStableFunc(p[:l], down)
+	if width > height {
+		// Sort in X first and slices alternating up and down
+		slices.SortFunc(indices, func(a, b int32) int {
+			return cmp.Compare(vertices[a].X, vertices[b].X)
+		})
+		d1 = func(a, b int32) int { return cmp.Compare(vertices[a].Y, vertices[b].Y) }
+		d2 = func(a, b int32) int { return cmp.Compare(vertices[b].Y, vertices[a].Y) }
+	} else {
+		// Sort in Y first and slices alternating left and right
+		slices.SortFunc(indices, func(a, b int32) int {
+			return cmp.Compare(vertices[a].Y, vertices[b].Y)
+		})
+		d1 = func(a, b int32) int { return cmp.Compare(vertices[a].X, vertices[b].X) }
+		d2 = func(a, b int32) int { return cmp.Compare(vertices[b].X, vertices[a].X) }
+	}
+
+	for p := indices; len(p) > 0; d1, d2 = d2, d1 {
+		l := min(len(p), t)
+		slices.SortStableFunc(p[:l], d2)
 		p = p[l:]
 	}