Mercurial > gemma

comparison pkg/octree/strtree.go @ 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 114979e97a6c
children 680f1d8802f0
comparison
equal deleted inserted replaced
4589:9cd00133dff9 4591:f456ce0a6a0e
16 import ( 16 import (
17 "math" 17 "math"
18 "sort" 18 "sort"
19 ) 19 )
20 20
21 const numEntries = 8 21 const STRTreeDefaultEntries = 8
22 22
23 type STRTree struct { 23 type STRTree struct {
24 tin *Tin 24 Entries int
25 index []int32 25 tin *Tin
26 bboxes []Box2D 26 index []int32
27 bboxes []Box2D
27 } 28 }
28 29
29 func (s *STRTree) Build(t *Tin) { 30 func (s *STRTree) Build(t *Tin) {
31
32 if s.Entries == 0 {
33 s.Entries = STRTreeDefaultEntries
34 }
30 35
31 s.tin = t 36 s.tin = t
32 37
33 all := make([]int32, len(t.Triangles)) 38 all := make([]int32, len(t.Triangles))
34 39
111 ti := s.tin.Triangles[items[i]] 116 ti := s.tin.Triangles[items[i]]
112 tj := s.tin.Triangles[items[j]] 117 tj := s.tin.Triangles[items[j]]
113 return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X 118 return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
114 }) 119 })
115 120
116 P := int(math.Ceil(float64(len(items)) / float64(numEntries))) 121 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
117 S := int(math.Ceil(math.Sqrt(float64(P)))) 122 S := int(math.Ceil(math.Sqrt(float64(P))))
118 123
119 slices := strSplit(items, S) 124 slices := s.strSplit(items, S)
120 125
121 leaves := strJoin( 126 leaves := s.strJoin(
122 slices, S, 127 slices, S,
123 func(i, j int32) bool { 128 func(i, j int32) bool {
124 ti := s.tin.Triangles[i] 129 ti := s.tin.Triangles[i]
125 tj := s.tin.Triangles[j] 130 tj := s.tin.Triangles[j]
126 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y 131 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
131 return s.buildNodes(leaves) 136 return s.buildNodes(leaves)
132 } 137 }
133 138
134 func (s *STRTree) buildNodes(items []int32) int32 { 139 func (s *STRTree) buildNodes(items []int32) int32 {
135 140
136 if len(items) <= numEntries { 141 if len(items) <= s.Entries {
137 return s.allocNode(items) 142 return s.allocNode(items)
138 } 143 }
139 144
140 sort.Slice(items, func(i, j int) bool { 145 sort.Slice(items, func(i, j int) bool {
141 return s.bbox(items[i]).X1 < s.bbox(items[j]).X1 146 return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
142 }) 147 })
143 148
144 P := int(math.Ceil(float64(len(items)) / float64(numEntries))) 149 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
145 S := int(math.Ceil(math.Sqrt(float64(P)))) 150 S := int(math.Ceil(math.Sqrt(float64(P))))
146 151
147 slices := strSplit(items, S) 152 slices := s.strSplit(items, S)
148 153
149 nodes := strJoin( 154 nodes := s.strJoin(
150 slices, S, 155 slices, S,
151 func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 }, 156 func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 },
152 s.allocNode, 157 s.allocNode,
153 ) 158 )
154 159
160 idx = -idx - 1 165 idx = -idx - 1
161 } 166 }
162 return s.bboxes[s.index[idx]] 167 return s.bboxes[s.index[idx]]
163 } 168 }
164 169
165 func strSplit(items []int32, S int) [][]int32 { 170 func (s *STRTree) strSplit(items []int32, S int) [][]int32 {
166 sm := S * numEntries 171 sm := S * s.Entries
167 slices := make([][]int32, S) 172 slices := make([][]int32, S)
168 for i := range slices { 173 for i := range slices {
169 var n int 174 var n int
170 if l := len(items); l < sm { 175 if l := len(items); l < sm {
171 n = l 176 n = l
176 items = items[n:] 181 items = items[n:]
177 } 182 }
178 return slices 183 return slices
179 } 184 }
180 185
181 func strJoin( 186 func (s *STRTree) strJoin(
182 slices [][]int32, S int, 187 slices [][]int32, S int,
183 less func(int32, int32) bool, 188 less func(int32, int32) bool,
184 alloc func([]int32) int32, 189 alloc func([]int32) int32,
185 ) []int32 { 190 ) []int32 {
186 nodes := make([]int32, 0, S*S) 191 nodes := make([]int32, 0, S*S)
190 return less(slice[i], slice[j]) 195 return less(slice[i], slice[j])
191 }) 196 })
192 197
193 for len(slice) > 0 { 198 for len(slice) > 0 {
194 var n int 199 var n int
195 if l := len(slice); l >= numEntries { 200 if l := len(slice); l >= s.Entries {
196 n = numEntries 201 n = s.Entries
197 } else { 202 } else {
198 n = l 203 n = l
199 } 204 }
200 nodes = append(nodes, alloc(slice[:n])) 205 nodes = append(nodes, alloc(slice[:n]))
201 slice = slice[n:] 206 slice = slice[n:]