Mercurial > gemma

changeset 4591:f456ce0a6a0e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STRTree: Made number of entries per node a parameter.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 09 Oct 2019 11:40:11 +0200
parents 9cd00133dff9
children 680f1d8802f0
files pkg/octree/strtree.go
diffstat 1 files changed, 21 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/strtree.go	Wed Oct 09 09:46:10 2019 +0200
+++ b/pkg/octree/strtree.go	Wed Oct 09 11:40:11 2019 +0200
@@ -18,16 +18,21 @@
 	"sort"
 )
 
-const numEntries = 8
+const STRTreeDefaultEntries = 8
 
 type STRTree struct {
-	tin    *Tin
-	index  []int32
-	bboxes []Box2D
+	Entries int
+	tin     *Tin
+	index   []int32
+	bboxes  []Box2D
 }
 
 func (s *STRTree) Build(t *Tin) {
 
+	if s.Entries == 0 {
+		s.Entries = STRTreeDefaultEntries
+	}
+
 	s.tin = t
 
 	all := make([]int32, len(t.Triangles))
@@ -113,12 +118,12 @@
 		return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
 	})
 
-	P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
+	P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
 	S := int(math.Ceil(math.Sqrt(float64(P))))
 
-	slices := strSplit(items, S)
+	slices := s.strSplit(items, S)
 
-	leaves := strJoin(
+	leaves := s.strJoin(
 		slices, S,
 		func(i, j int32) bool {
 			ti := s.tin.Triangles[i]
@@ -133,7 +138,7 @@
 
 func (s *STRTree) buildNodes(items []int32) int32 {
 
-	if len(items) <= numEntries {
+	if len(items) <= s.Entries {
 		return s.allocNode(items)
 	}
 
@@ -141,12 +146,12 @@
 		return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
 	})
 
-	P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
+	P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
 	S := int(math.Ceil(math.Sqrt(float64(P))))
 
-	slices := strSplit(items, S)
+	slices := s.strSplit(items, S)
 
-	nodes := strJoin(
+	nodes := s.strJoin(
 		slices, S,
 		func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 },
 		s.allocNode,
@@ -162,8 +167,8 @@
 	return s.bboxes[s.index[idx]]
 }
 
-func strSplit(items []int32, S int) [][]int32 {
-	sm := S * numEntries
+func (s *STRTree) strSplit(items []int32, S int) [][]int32 {
+	sm := S * s.Entries
 	slices := make([][]int32, S)
 	for i := range slices {
 		var n int
@@ -178,7 +183,7 @@
 	return slices
 }
 
-func strJoin(
+func (s *STRTree) strJoin(
 	slices [][]int32, S int,
 	less func(int32, int32) bool,
 	alloc func([]int32) int32,
@@ -192,8 +197,8 @@
 
 		for len(slice) > 0 {
 			var n int
-			if l := len(slice); l >= numEntries {
-				n = numEntries
+			if l := len(slice); l >= s.Entries {
+				n = s.Entries
 			} else {
 				n = l
 			}