# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1707673237 -3600
# Node ID a87900c0fd11721620dc20c59df80b2a7c1d9b0b
# Parent  03dfbe67584274a347dcbb81488b4b746ce323f9
Remove triangles that are not registered in the spatial index.

diff -r 03dfbe675842 -r a87900c0fd11 pkg/mesh/meshserialize.go
--- a/pkg/mesh/meshserialize.go	Sun Feb 11 12:37:09 2024 +0100
+++ b/pkg/mesh/meshserialize.go	Sun Feb 11 18:40:37 2024 +0100
@@ -36,8 +36,9 @@
 
 func (s *STRTree) OptimizeForSerialization(version int) {
 	version = coalesceVersion(version)
-	// TODO: Implement me!
-	_ = version
+	if version == 2 {
+		s.optimizeForSerializationV2()
+	}
 }
 
 // Bytes serializes this tree to a byte slice.
diff -r 03dfbe675842 -r a87900c0fd11 pkg/mesh/meshserialize_v2.go
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pkg/mesh/meshserialize_v2.go	Sun Feb 11 18:40:37 2024 +0100
@@ -0,0 +1,50 @@
+// This is Free Software under GNU Affero General Public License v >= 3.0
+// without warranty, see README.md and license for details.
+//
+// SPDX-License-Identifier: AGPL-3.0-or-later
+// License-Filename: LICENSES/AGPL-3.0.txt
+//
+// Copyright (C) 2024 by via donau
+//   – Österreichische Wasserstraßen-Gesellschaft mbH
+// Software engineering by Intevation GmbH
+//
+// Author(s):
+//  * Sascha L. Teichmann <sascha.teichmann@intevation.de>
+
+package mesh
+
+func (s *STRTree) optimizeForSerializationV2() {
+	s.removeUnusedTriangles()
+	// TODO: Implement me!
+}
+
+// removeUnusedTriangles removes all triangles from the
+// TIN that are not registered in the spatial index.
+func (s *STRTree) removeUnusedTriangles() {
+	used := make([]bool, len(s.tin.Triangles))
+	unused := len(used)
+	s.allTriangleIndices(func(indices []int32) {
+		for _, idx := range indices {
+			used[idx] = true
+			unused-- // They only occur once in the spatial index.
+		}
+	})
+	if unused <= 0 {
+		return
+	}
+	newTris := make([][]int32, 0, len(s.tin.Triangles)-unused)
+	remap := map[int32]int32{}
+	for idx, tri := range s.tin.Triangles {
+		if used[idx] {
+			remap[int32(idx)] = int32(len(newTris))
+			newTris = append(newTris, tri)
+		}
+	}
+	s.tin.Triangles = newTris
+	// Update the spatial index as the gaps are now closed.
+	s.allTriangleIndices(func(indices []int32) {
+		for i, idx := range indices {
+			indices[i] = remap[idx]
+		}
+	})
+}
diff -r 03dfbe675842 -r a87900c0fd11 pkg/mesh/strtree.go
--- a/pkg/mesh/strtree.go	Sun Feb 11 12:37:09 2024 +0100
+++ b/pkg/mesh/strtree.go	Sun Feb 11 18:40:37 2024 +0100
@@ -409,3 +409,20 @@
 	}
 	return int32(-(pos + 1))
 }
+
+// allTriangleIndices passes all triangle indices to callback fn.
+func (s *STRTree) allTriangleIndices(fn func([]int32)) {
+	stack := []int32{s.index[0]}
+	for len(stack) > 0 {
+		top := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+		if top > 0 { // node
+			n := s.index[top+1]
+			stack = append(stack, s.index[top+2:top+2+n]...)
+		} else { // leaf
+			top = -top - 1
+			n := s.index[top+1]
+			fn(s.index[top+2 : top+2+n])
+		}
+	}
+}