# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1551797714 -3600
# Node ID 6bcaa8bf260391c82a00d3bdf16335df5ca00406
# Parent  1534df518201efa37cdc347378cd223290aafb7c
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.

diff -r 1534df518201 -r 6bcaa8bf2603 pkg/octree/strtree.go
--- a/pkg/octree/strtree.go	Tue Mar 05 15:00:42 2019 +0100
+++ b/pkg/octree/strtree.go	Tue Mar 05 15:55:14 2019 +0100
@@ -62,8 +62,8 @@
 	rest := items
 	for i := range slices {
 		var n int
-		if len(rest) < sm {
-			n = len(rest)
+		if l := len(rest); l < sm {
+			n = l
 		} else {
 			n = sm
 		}
@@ -77,7 +77,7 @@
 		sort.Slice(slice, func(i, j int) bool {
 			ti := s.triangles[slice[i]]
 			tj := s.triangles[slice[j]]
-			return s.tri.Points[ti[0]].X < s.tri.Points[tj[0]].X
+			return s.tri.Points[ti[0]].Y < s.tri.Points[tj[0]].Y
 		})
 
 		for len(slice) > 0 {
@@ -93,11 +93,11 @@
 	return s.buildNodes(leaves)
 }
 
-func bboxIndex(idx int32) int32 {
-	if idx < 0 {
-		return -idx - 1
+func (s *STRTree) bbox(idx int32) Box2D {
+	if idx < 0 { // Don't care if leaf or node.
+		idx = -idx - 1
 	}
-	return idx
+	return s.bboxes[s.index[idx]]
 }
 
 func (s *STRTree) buildNodes(items []int32) int32 {
@@ -107,9 +107,7 @@
 	}
 
 	sort.Slice(items, func(i, j int) bool {
-		bi := s.bboxes[s.index[bboxIndex(items[i])]]
-		bj := s.bboxes[s.index[bboxIndex(items[j])]]
-		return bi.X1 < bj.X1
+		return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
 	})
 
 	P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
@@ -118,18 +116,12 @@
 	sm := S * numEntries
 
 	slices := make([][]int32, S)
-	/*
-		log.Printf("S: %d\n", S)
-		log.Printf("SM: %d\n", sm)
-		log.Printf("S * SM: %d\n", S*sm)
-		log.Printf("N: %d\n", len(items))
-	*/
 
 	rest := items
 	for i := range slices {
 		var n int
-		if len(rest) < sm {
-			n = len(rest)
+		if l := len(rest); l < sm {
+			n = l
 		} else {
 			n = sm
 		}
@@ -141,9 +133,7 @@
 
 	for _, slice := range slices {
 		sort.Slice(slice, func(i, j int) bool {
-			bi := s.bboxes[s.index[bboxIndex(slice[i])]]
-			bj := s.bboxes[s.index[bboxIndex(slice[j])]]
-			return bi.X1 < bj.X1
+			return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1
 		})
 
 		for len(slice) > 0 {
@@ -161,14 +151,12 @@
 
 func (s *STRTree) allocNode(items []int32) int32 {
 	pos := len(s.index)
-	s.index = append(s.index, 0)
+	s.index = append(s.index, 0, int32(len(items)))
 	s.index = append(s.index, items...)
 	if len(items) > 0 {
-		box := s.bboxes[s.index[bboxIndex(items[0])]]
+		box := s.bbox(items[0])
 		for i := 1; i < len(items); i++ {
-			it := items[i]
-			b := s.bboxes[s.index[bboxIndex(it)]]
-			box = box.Union(b)
+			box = box.Union(s.bbox(items[i]))
 		}
 		s.index[pos] = int32(s.allocBBox(box))
 	}
@@ -183,27 +171,28 @@
 
 func (s *STRTree) allocLeaf(items []int32) int32 {
 	pos := len(s.index)
-	s.index = append(s.index, 0)
+	s.index = append(s.index, 0, int32(len(items)))
 	s.index = append(s.index, items...)
 	if len(items) > 0 {
+		vertices := s.tri.Points
 		ti := s.triangles[items[0]]
 		t := Triangle{
-			s.tri.Points[ti[0]],
-			s.tri.Points[ti[1]],
-			s.tri.Points[ti[2]],
+			vertices[ti[0]],
+			vertices[ti[1]],
+			vertices[ti[2]],
 		}
 		box := t.BBox()
 		for i := 1; i < len(items); i++ {
 			it := items[i]
 			ti := s.triangles[it]
 			t := Triangle{
-				s.tri.Points[ti[0]],
-				s.tri.Points[ti[1]],
-				s.tri.Points[ti[2]],
+				vertices[ti[0]],
+				vertices[ti[1]],
+				vertices[ti[2]],
 			}
 			box = box.Union(t.BBox())
 		}
 		s.index[pos] = int32(s.allocBBox(box))
 	}
-	return -int32(pos) - 1
+	return int32(-(pos + 1))
 }