# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1707687175 -3600
# Node ID 536e842d9bfaaf5edd9664f8d6253a983c3cf71a
# Parent  31973f6f5cca400dc9c921861e653b2095412776
Reorder vertices in tins to minimize delta distances.

diff -r 31973f6f5cca -r 536e842d9bfa pkg/mesh/meshserialize_v2.go
--- a/pkg/mesh/meshserialize_v2.go	Sun Feb 11 21:37:00 2024 +0100
+++ b/pkg/mesh/meshserialize_v2.go	Sun Feb 11 22:32:55 2024 +0100
@@ -13,9 +13,16 @@
 
 package mesh
 
+import (
+	"cmp"
+	"math"
+	"slices"
+	"sort"
+)
+
 func (s *STRTree) optimizeForSerializationV2() {
 	s.removeUnusedTriangles()
-	// TODO: Implement me!
+	s.sortVertices()
 	s.sortIndices()
 }
 
@@ -49,3 +56,44 @@
 		}
 	})
 }
+
+// sortVertices so that the deltas between neighbors are minimized.
+func (s *STRTree) sortVertices() {
+	vertices := s.tin.Vertices
+	indices := make([]int32, len(vertices))
+	for i := range len(indices) {
+		indices[i] = int32(i)
+	}
+
+	slices.SortFunc(indices, func(a, b int32) int {
+		return cmp.Compare(vertices[a].X, vertices[b].X)
+	})
+
+	n := int(math.Sqrt(float64(len(vertices))))
+	m := len(vertices) / n
+
+	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)
+		p = p[l:]
+	}
+
+	// We really need to to sort the vertices actually, too.
+	sort.Slice(vertices, func(i, j int) bool { return indices[i] < indices[j] })
+
+	reindices := make([]int32, len(indices))
+	for i, idx := range indices {
+		reindices[idx] = int32(i)
+	}
+
+	// Update the indices in the triangles.
+	for _, tri := range s.tin.Triangles {
+		for i, idx := range tri {
+			tri[i] = reindices[idx]
+		}
+	}
+}