Mercurial > gemma

comparison pkg/octree/strtree.go @ 2515:6bcaa8bf2603 octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 05 Mar 2019 15:55:14 +0100
parents 1534df518201
children 1ec4c5633eb6
comparison
equal deleted inserted replaced
2513:1534df518201 2515:6bcaa8bf2603
60 60
61 slices := make([][]int32, S) 61 slices := make([][]int32, S)
62 rest := items 62 rest := items
63 for i := range slices { 63 for i := range slices {
64 var n int 64 var n int
65 if len(rest) < sm { 65 if l := len(rest); l < sm {
66 n = len(rest) 66 n = l
67 } else { 67 } else {
68 n = sm 68 n = sm
69 } 69 }
70 slices[i] = rest[:n] 70 slices[i] = rest[:n]
71 rest = rest[n:] 71 rest = rest[n:]
75 75
76 for _, slice := range slices { 76 for _, slice := range slices {
77 sort.Slice(slice, func(i, j int) bool { 77 sort.Slice(slice, func(i, j int) bool {
78 ti := s.triangles[slice[i]] 78 ti := s.triangles[slice[i]]
79 tj := s.triangles[slice[j]] 79 tj := s.triangles[slice[j]]
80 return s.tri.Points[ti[0]].X < s.tri.Points[tj[0]].X 80 return s.tri.Points[ti[0]].Y < s.tri.Points[tj[0]].Y
81 }) 81 })
82 82
83 for len(slice) > 0 { 83 for len(slice) > 0 {
84 n := numEntries 84 n := numEntries
85 if l := len(slice); l < numEntries { 85 if l := len(slice); l < numEntries {
91 } 91 }
92 92
93 return s.buildNodes(leaves) 93 return s.buildNodes(leaves)
94 } 94 }
95 95
96 func bboxIndex(idx int32) int32 { 96 func (s *STRTree) bbox(idx int32) Box2D {
97 if idx < 0 { 97 if idx < 0 { // Don't care if leaf or node.
98 return -idx - 1 98 idx = -idx - 1
99 } 99 }
100 return idx 100 return s.bboxes[s.index[idx]]
101 } 101 }
102 102
103 func (s *STRTree) buildNodes(items []int32) int32 { 103 func (s *STRTree) buildNodes(items []int32) int32 {
104 104
105 if len(items) <= numEntries { 105 if len(items) <= numEntries {
106 return s.allocNode(items) 106 return s.allocNode(items)
107 } 107 }
108 108
109 sort.Slice(items, func(i, j int) bool { 109 sort.Slice(items, func(i, j int) bool {
110 bi := s.bboxes[s.index[bboxIndex(items[i])]] 110 return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
111 bj := s.bboxes[s.index[bboxIndex(items[j])]]
112 return bi.X1 < bj.X1
113 }) 111 })
114 112
115 P := int(math.Ceil(float64(len(items)) / float64(numEntries))) 113 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
116 S := int(math.Ceil(math.Sqrt(float64(P)))) 114 S := int(math.Ceil(math.Sqrt(float64(P))))
117 115
118 sm := S * numEntries 116 sm := S * numEntries
119 117
120 slices := make([][]int32, S) 118 slices := make([][]int32, S)
121 /*
122 log.Printf("S: %d\n", S)
123 log.Printf("SM: %d\n", sm)
124 log.Printf("S * SM: %d\n", S*sm)
125 log.Printf("N: %d\n", len(items))
126 */
127 119
128 rest := items 120 rest := items
129 for i := range slices { 121 for i := range slices {
130 var n int 122 var n int
131 if len(rest) < sm { 123 if l := len(rest); l < sm {
132 n = len(rest) 124 n = l
133 } else { 125 } else {
134 n = sm 126 n = sm
135 } 127 }
136 slices[i] = rest[:n] 128 slices[i] = rest[:n]
137 rest = rest[n:] 129 rest = rest[n:]
139 131
140 nodes := make([]int32, 0, S*S) 132 nodes := make([]int32, 0, S*S)
141 133
142 for _, slice := range slices { 134 for _, slice := range slices {
143 sort.Slice(slice, func(i, j int) bool { 135 sort.Slice(slice, func(i, j int) bool {
144 bi := s.bboxes[s.index[bboxIndex(slice[i])]] 136 return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1
145 bj := s.bboxes[s.index[bboxIndex(slice[j])]]
146 return bi.X1 < bj.X1
147 }) 137 })
148 138
149 for len(slice) > 0 { 139 for len(slice) > 0 {
150 n := numEntries 140 n := numEntries
151 if l := len(slice); l < numEntries { 141 if l := len(slice); l < numEntries {
159 return s.buildNodes(nodes) 149 return s.buildNodes(nodes)
160 } 150 }
161 151
162 func (s *STRTree) allocNode(items []int32) int32 { 152 func (s *STRTree) allocNode(items []int32) int32 {
163 pos := len(s.index) 153 pos := len(s.index)
164 s.index = append(s.index, 0) 154 s.index = append(s.index, 0, int32(len(items)))
165 s.index = append(s.index, items...) 155 s.index = append(s.index, items...)
166 if len(items) > 0 { 156 if len(items) > 0 {
167 box := s.bboxes[s.index[bboxIndex(items[0])]] 157 box := s.bbox(items[0])
168 for i := 1; i < len(items); i++ { 158 for i := 1; i < len(items); i++ {
169 it := items[i] 159 box = box.Union(s.bbox(items[i]))
170 b := s.bboxes[s.index[bboxIndex(it)]]
171 box = box.Union(b)
172 } 160 }
173 s.index[pos] = int32(s.allocBBox(box)) 161 s.index[pos] = int32(s.allocBBox(box))
174 } 162 }
175 return int32(pos) 163 return int32(pos)
176 } 164 }
181 return pos 169 return pos
182 } 170 }
183 171
184 func (s *STRTree) allocLeaf(items []int32) int32 { 172 func (s *STRTree) allocLeaf(items []int32) int32 {
185 pos := len(s.index) 173 pos := len(s.index)
186 s.index = append(s.index, 0) 174 s.index = append(s.index, 0, int32(len(items)))
187 s.index = append(s.index, items...) 175 s.index = append(s.index, items...)
188 if len(items) > 0 { 176 if len(items) > 0 {
177 vertices := s.tri.Points
189 ti := s.triangles[items[0]] 178 ti := s.triangles[items[0]]
190 t := Triangle{ 179 t := Triangle{
191 s.tri.Points[ti[0]], 180 vertices[ti[0]],
192 s.tri.Points[ti[1]], 181 vertices[ti[1]],
193 s.tri.Points[ti[2]], 182 vertices[ti[2]],
194 } 183 }
195 box := t.BBox() 184 box := t.BBox()
196 for i := 1; i < len(items); i++ { 185 for i := 1; i < len(items); i++ {
197 it := items[i] 186 it := items[i]
198 ti := s.triangles[it] 187 ti := s.triangles[it]
199 t := Triangle{ 188 t := Triangle{
200 s.tri.Points[ti[0]], 189 vertices[ti[0]],
201 s.tri.Points[ti[1]], 190 vertices[ti[1]],
202 s.tri.Points[ti[2]], 191 vertices[ti[2]],
203 } 192 }
204 box = box.Union(t.BBox()) 193 box = box.Union(t.BBox())
205 } 194 }
206 s.index[pos] = int32(s.allocBBox(box)) 195 s.index[pos] = int32(s.allocBBox(box))
207 } 196 }
208 return -int32(pos) - 1 197 return int32(-(pos + 1))
209 } 198 }