Mercurial > gemma
changeset 4591:f456ce0a6a0e
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 }