changeset 2565:114979e97a6c

STR tree: More code simplification.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 11 Mar 2019 11:14:44 +0100
parents 27501719e79b
children 83b938bf4da9
files pkg/octree/strtree.go
diffstat 1 files changed, 52 insertions(+), 46 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/strtree.go	Mon Mar 11 10:49:16 2019 +0100
+++ b/pkg/octree/strtree.go	Mon Mar 11 11:14:44 2019 +0100
@@ -106,22 +106,6 @@
 	}
 }
 
-func strSplit(items []int32, S int) [][]int32 {
-	sm := S * numEntries
-	slices := make([][]int32, S)
-	for i := range slices {
-		var n int
-		if l := len(items); l < sm {
-			n = l
-		} else {
-			n = sm
-		}
-		slices[i] = items[:n]
-		items = items[n:]
-	}
-	return slices
-}
-
 func (s *STRTree) build(items []int32) int32 {
 	sort.Slice(items, func(i, j int) bool {
 		ti := s.tin.Triangles[items[i]]
@@ -134,35 +118,19 @@
 
 	slices := strSplit(items, S)
 
-	leaves := make([]int32, 0, S*S)
-
-	for _, slice := range slices {
-		sort.Slice(slice, func(i, j int) bool {
-			ti := s.tin.Triangles[slice[i]]
-			tj := s.tin.Triangles[slice[j]]
+	leaves := strJoin(
+		slices, S,
+		func(i, j int32) bool {
+			ti := s.tin.Triangles[i]
+			tj := s.tin.Triangles[j]
 			return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
-		})
-
-		for len(slice) > 0 {
-			n := numEntries
-			if l := len(slice); l < numEntries {
-				n = l
-			}
-			leaves = append(leaves, s.allocLeaf(slice[:n]))
-			slice = slice[n:]
-		}
-	}
+		},
+		s.allocLeaf,
+	)
 
 	return s.buildNodes(leaves)
 }
 
-func (s *STRTree) bbox(idx int32) Box2D {
-	if idx < 0 { // Don't care if leaf or node.
-		idx = -idx - 1
-	}
-	return s.bboxes[s.index[idx]]
-}
-
 func (s *STRTree) buildNodes(items []int32) int32 {
 
 	if len(items) <= numEntries {
@@ -178,24 +146,62 @@
 
 	slices := strSplit(items, S)
 
+	nodes := strJoin(
+		slices, S,
+		func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 },
+		s.allocNode,
+	)
+
+	return s.buildNodes(nodes)
+}
+
+func (s *STRTree) bbox(idx int32) Box2D {
+	if idx < 0 { // Don't care if leaf or node.
+		idx = -idx - 1
+	}
+	return s.bboxes[s.index[idx]]
+}
+
+func strSplit(items []int32, S int) [][]int32 {
+	sm := S * numEntries
+	slices := make([][]int32, S)
+	for i := range slices {
+		var n int
+		if l := len(items); l < sm {
+			n = l
+		} else {
+			n = sm
+		}
+		slices[i] = items[:n]
+		items = items[n:]
+	}
+	return slices
+}
+
+func strJoin(
+	slices [][]int32, S int,
+	less func(int32, int32) bool,
+	alloc func([]int32) int32,
+) []int32 {
 	nodes := make([]int32, 0, S*S)
 
 	for _, slice := range slices {
 		sort.Slice(slice, func(i, j int) bool {
-			return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1
+			return less(slice[i], slice[j])
 		})
 
 		for len(slice) > 0 {
-			n := numEntries
-			if l := len(slice); l < numEntries {
+			var n int
+			if l := len(slice); l >= numEntries {
+				n = numEntries
+			} else {
 				n = l
 			}
-			nodes = append(nodes, s.allocNode(slice[:n]))
+			nodes = append(nodes, alloc(slice[:n]))
 			slice = slice[n:]
 		}
 	}
-
-	return s.buildNodes(nodes)
+	return nodes
 }
 
 func (s *STRTree) allocNode(items []int32) int32 {