Mercurial > gemma
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 {