NDEVR
API Documentation
RTree.hpp
1/*--------------------------------------------------------------------------------------------
2Copyright (c) 2019, NDEVR LLC
3tyler.parke@ndevr.org
4 __ __ ____ _____ __ __ _______
5 | \ | | | __ \ | ___|\ \ / / | __ \
6 | \ | | | | \ \ | |___ \ \ / / | |__) |
7 | . \| | | |__/ / | |___ \ V / | _ /
8 | |\ |_|_____/__|_____|___\_/____| | \ \
9 |__| \__________________________________| \__\
10
11Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants
12Licensee a limited, non-exclusive, non-transferable, royalty-free license
13(without the right to sublicense) to use the API solely for the purpose of
14Licensee's internal development efforts to develop applications for which
15the API was provided.
16
17The above copyright notice and this permission notice shall be included in all
18copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
21INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
22PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
23FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25DEALINGS IN THE SOFTWARE.
26
27Library: Tree
28File: RTree
29Included in API: False
30Author(s): Tyler Parke
31\internal
32 *-----------------------------------------------------------------------------------------**/
33#pragma once
34#include <NDEVR/TreeIterator.h>
35#include <NDEVR/Node.h>
36#include <NDEVR/Tree.h>
37#include <NDEVR/TreeSorter.h>
38#include <NDEVR/BaseValues.h>
39#include <NDEVR/Buffer.h>
40#include <NDEVR/Bounds.h>
41#include <NDEVR/Median.h>
42#include <NDEVR/OpenMP.h>
43#include <NDEVR/InfoPipe.h>
44#include <NDEVR/Vector.h>
45#include <NDEVR/VectorFunctions.h>
46#include <NDEVR/Intersection.h>
47#include <NDEVR/Distance.h>
48#include <NDEVR/BinaryHeap.h>
49#include <NDEVR/BinaryFile.h>
50#include <NDEVR/BinaryFileTableInfo.h>
51#include <functional>
52namespace NDEVR
53{
54 template<uint01 t_dims, class t_type>
55 class RNode : public TreeNode
56 {
57 public:
58 RNode()
59 : TreeNode(Constant<uint04>::Invalid)
60 , m_cache_bounds(Constant<Bounds<t_dims, t_type>>::Invalid)
61 {}
62 explicit RNode(uint04 index_start)
63 : TreeNode(index_start)
64 , m_cache_bounds(Constant<Bounds<t_dims, t_type>>::Min)
65 {}
66 void clear(uint04 index_start)
67 {
68 setBegin(index_start);
69 m_cache_bounds = Constant<Bounds<t_dims, t_type>>::Invalid;
70 m_element_size = 0;
71 }
72 void clear(uint04 index_start, const Bounds<t_dims, t_type>& bounds)
73 {
74 setBegin(index_start);
75 m_cache_bounds = bounds;
76 m_element_size = 0;
77 }
78
79 uint04 left() const
80 {
81 return uint04(m_child_start);
82 }
83 uint04 right() const
84 {
85 return uint04(m_child_start) + 1;
86 }
87
88 const Bounds<t_dims, t_type>& bounds() const
89 {
90 return m_cache_bounds;
91 }
92 Bounds<t_dims, t_type>& bounds()
93 {
94 return m_cache_bounds;
95 }
96 void setBounds(const Bounds<t_dims, t_type>& bounds)
97 {
98 m_cache_bounds = bounds;
99 }
100
101 protected:
102 Bounds<t_dims, t_type> m_cache_bounds;
103 };
104
105
106
107 template<uint01 t_dims, class t_type>
108 class RTreeBase : public TreeBase<RNode<t_dims, t_type>, t_type, 2>
109 {
110 public:
111 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_nodes;
112 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::root_node;
113 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_indices;
114 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_bucket_size;
115 explicit RTreeBase<t_dims, t_type>(uint04 bucket_size)
116 : TreeBase<RNode<t_dims, t_type>, t_type, 2>(bucket_size)
117 {}
118 RTreeBase<t_dims, t_type>(const RTreeBase<t_dims, t_type>& tree)
119 : TreeBase<RNode<t_dims, t_type>, t_type, 2>(tree)
120 {}
121 RTreeBase<t_dims, t_type>(RTreeBase<t_dims, t_type>&& tree)
122 : TreeBase<RNode<t_dims, t_type>, t_type, 2>(std::move(tree))
123 {}
124 protected:
125 RTreeBase<t_dims, t_type>(const Buffer<RNode<t_dims, t_type>>& nodes, const Buffer<uint04>& indices, bool is_read_only)
126 : TreeBase<RNode<t_dims, t_type>, t_type, 2>(nodes, indices, is_read_only)
127 {}
128 public:
129 template<class t_buffer_type>
130 bool validate(const t_buffer_type& elements)
131 {
132 TreeIterator iterator(root_node);
133
134 Buffer<uint04> values;
135 values.setSize(elements.size());
136 if (elements.size() == 0)
137 return true;
138 uint04 i = 0;
139 while (iterator.valid())
140 {
141 if (i++ > m_nodes.size())
142 {
143 lib_assert(false, "invalid tree");
144 return false;
145 }
146 const uint04 node_index = iterator.get();
147 RNode<t_dims, t_type>& node = m_nodes[node_index];
148 iterator.pop();
149
150 values.clear();
151 if(m_indices.size() == 0)
152 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<true>(node_index, values);
153 else
154 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(node_index, values);
155 if (node.size() != values.size())
156 {
157 lib_assert(false, "invalid tree");
158 return false;
159 }
160 if (IsValid(node.bounds()))
161 {
162 if (node.size() != 0 && !node.bounds().validate())
163 {
164 lib_assert(false, "invalid tree");
165 return false;
166 }
167 }
168 if (node.isLeaf())
169 {
170 const uint04 end = node.begin() + node.size();
171 if (m_indices.size() > 0)
172 {
173 for (uint04 idx = node.begin(); idx < end; idx++)
174 {
175 const auto& element = elements[m_indices[idx]];
176 if (IsValid(element) && classify(node.bounds(), element.template as<t_dims, t_type>()) != IntersectionTypes::e_inside)
177 {
178 lib_assert(false, "invalid tree");
179 return false;
180 }
181 }
182 }
183 else
184 {
185 for (uint04 idx = node.begin(); idx < end; idx++)
186 {
187 const auto& element = elements[idx];
188 if (IsValid(element) && classify(node.bounds(), element.template as<t_dims, t_type>()) != IntersectionTypes::e_inside)
189 {
190 lib_assert(false, "invalid tree");
191 return false;
192 }
193 }
194 }
195 }
196 else
197 {
198 if (node.size() != m_nodes[node.left()].size() + m_nodes[node.right()].size())
199 {
200 lib_assert(false, "invalid tree");
201 return false;
202 }
203 if(IsValid(node.bounds()) && IsValid(m_nodes[node.left()].bounds()))
204 if (classify(node.bounds(), m_nodes[node.left()].bounds()) != IntersectionTypes::e_inside)
205 {
206 lib_assert(false, "invalid tree");
207 return false;
208 }
209 if (IsValid(node.bounds()) && IsValid(m_nodes[node.right()].bounds()))
210 if (classify(node.bounds(), m_nodes[node.right()].bounds()) != IntersectionTypes::e_inside)
211 {
212 lib_assert(false, "invalid tree");
213 return false;
214 }
215
216 iterator.addAndGoToIndex(node.left(), node.right());
217 }
218 }
219 return true;
220 }
221 void traverse(const std::function<void(uint04 node_index, const PrimitiveBuffer<RNode<t_dims, t_type>>& node, const Buffer<uint04>& indices)>& callback) const
222 {
223 TreeIterator iterator(root_node);
224 while (iterator.valid())
225 {
226 const uint04 node_index = iterator.get();
227 const RNode<t_dims, t_type>& node = m_nodes[node_index];
228 iterator.pop();
229 callback(node_index, m_nodes, m_indices);
230 if (!node.isLeaf())
231 {
232 iterator.addAndGoToIndex(node.left(), node.right());
233 }
234 }
235 }
236 protected:
237
238 template<class t_buffer_type>
239 uint04 _calculateAndSplit(uint04 node_index, TreeBoundarySorter<t_dims, t_type>& sorter, const t_buffer_type& elements, uint04 start, uint04 end, bool is_precise)
240 {
241 UNUSED(is_precise);
242 Vector<t_dims, t_type> d_size;//The difference between the right and left size if a given node is chosen
243 for (uint01 dim = 0; dim < t_dims; ++dim)
244 {
245 if (m_nodes[node_index].bounds().span(dim) != 0)
246 {
247 Vector<2, Bounds<t_dims, t_type>> potential_bounds = sorter.getMedianBounds(dim, start, end, elements);
248 d_size[dim] = potential_bounds[0].surfaceArea() + potential_bounds[1].surfaceArea();
249 }
250
251 }
252 const uint01 split_dim = d_size.template dimensionalIndex<MIN>();//maximize our smallest split dimension
253
254 sorter.getMedian(split_dim, start, end);
255 const uint04 median_location = ((end - start) / 2) + start;
256
257 TreeBase<RNode<t_dims, t_type>, t_type, 2>::splitLeafNode(node_index);
258 auto left = sorter.getBounds(start, median_location, elements);
259 auto right = sorter.getBounds(median_location, end, elements);
260#ifdef _DEBUG
261 if (IsValid(m_nodes[node_index].bounds()) && IsValid(left))
262 if (classify(m_nodes[node_index].bounds(), left) != IntersectionTypes::e_inside)
263 lib_assert(false, "bad bounds creation");
264 if (IsValid(m_nodes[node_index].bounds()) && IsValid(right))
265 if (classify(m_nodes[node_index].bounds(), right) != IntersectionTypes::e_inside)
266 lib_assert(false, "bad bounds creation");
267#endif
268 m_nodes[m_nodes[node_index].left()].setBounds(left);
269 m_nodes[m_nodes[node_index].right()].setBounds(right);
270
271 return median_location;
272 }
273 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
274 bool _balanceLeafNode(uint04 top_index, const t_buffer_type& elements, Buffer<uint04>& indices, uint04 top_start, uint04 top_end, bool is_precise)
275 {
276 TreeBoundarySorter<t_dims, t_type> sorter;
277 if constexpr (t_uses_boundary)
278 {
279 sorter.template createBoundarySortList<t_has_nans>(indices, elements);
280 }
281 else
282 {
283 sorter.template createCenterSortList<t_has_nans>(indices, elements);
284 }
285 m_nodes[top_index].setBounds(sorter.getBounds(0, (top_end - top_start), elements));
286 uint04 start_stack[256];
287 uint04 end_stack[256];
288 start_stack[0] = top_start;
289 end_stack[0] = top_end;
290 TreeIterator iterator(top_index);
291 while (iterator.valid())
292 {
293 uint01 level = iterator.depth();
294 uint04 start = start_stack[level];
295 uint04 end = end_stack[level];
296 uint04 node_index = iterator.get();
297 iterator.pop();
298 m_nodes[node_index].setSize(end - start);
299
300 if ((end - start) > m_bucket_size)
301 {
302 const uint04 new_left = _calculateAndSplit(node_index, sorter, elements, start, end, is_precise);
303
304 iterator.addAndGoToIndex(m_nodes[node_index].right());
305 start_stack[iterator.depth()] = new_left;
306 end_stack[iterator.depth()] = end;
307
308 iterator.addAndGoToIndex(m_nodes[node_index].left());
309 start_stack[iterator.depth()] = start;
310 end_stack[iterator.depth()] = new_left;
311 }
312 else
313 {
314 sorter.getList(0, start, end, m_indices, m_nodes[node_index].begin());
315 }
316 }
317 return true;
318 }
319 template<class t_location_type>
320 bool predictBranch(uint04& index, const RNode<t_dims, t_type>& node, const t_location_type& selector, MinHeap<t_type, uint04>& node_heap, t_type min_distance_squared) const
321 {
322 t_type left_distance = distanceSquared(selector, m_nodes[node.left()].bounds());
323 if(left_distance <= t_type(0))
324 left_distance = -(cast<t_type>(1) / distanceSquared(selector, m_nodes[node.left()].bounds().center()));
325 t_type right_distance = distanceSquared(selector, m_nodes[node.right()].bounds());
326 if (right_distance <= t_type(0))
327 right_distance = -(cast<t_type>(1) / distanceSquared(selector, m_nodes[node.right()].bounds().center()));
328 if (left_distance < right_distance)
329 {
330 if (left_distance >= min_distance_squared)
331 {
332 if (node_heap.size() == 0 || node_heap.extremeComp() >= min_distance_squared)
333 return false;
334 index = node_heap.popExtreme();
335 }
336 else if(node_heap.size() > 0 && node_heap.extremeComp() < left_distance)
337 {
338 index = node_heap.popExtreme();
339 node_heap.insert(left_distance, node.left());
340 if (right_distance < min_distance_squared)
341 node_heap.insert(right_distance, node.right());
342 }
343 else
344 {
345 index = node.left();
346 if (right_distance < min_distance_squared)
347 node_heap.insert(right_distance, node.right());
348 }
349 }
350 else
351 {
352 if (right_distance >= min_distance_squared)
353 {
354 if (node_heap.size() == 0 || node_heap.extremeComp() >= min_distance_squared)
355 return false;
356 index = node_heap.popExtreme();
357 }
358 else if (node_heap.size() > 0 && node_heap.extremeComp() < right_distance)
359 {
360 index = node_heap.popExtreme();
361 node_heap.insert(right_distance, node.right());
362 if (left_distance < min_distance_squared)
363 node_heap.insert(left_distance, node.right());
364 }
365 else
366 {
367 index = node.right();
368 if (left_distance < min_distance_squared)
369 node_heap.insert(left_distance, node.left());
370 }
371 }
372 return true;
373 }
374 template<bool t_presorted, class t_location_type, class t_buffer_type>
375 void _getClosestElement(uint04 top_index, const t_location_type& selector, const t_buffer_type& elements, t_type& min_distance_squared, const t_type& epsilon, uint04& min_index) const
376 {
377 t_type root_distance = distanceSquared(selector, m_nodes[top_index].bounds());
378 lib_assert(min_distance_squared >= 0.0f, "Cannot search for 0.0 distance. Use epsilon");
379 if (root_distance >= min_distance_squared)
380 return;
381 MinHeap<t_type, uint04> node_heap(cast<uint04>(sqrt(cast<t_type>(m_nodes.size()))));
382 uint04 index = top_index;
383 for(;;)
384 {
385 const RNode<t_dims, t_type>& node = m_nodes[index];
386 if (node.isLeaf())
387 {
388 const uint04 end = node.end();
389 const uint04 start_index = node.begin();
390 for(uint04 i = start_index; i < end; ++i)
391 {
392 uint04 check_index;
393 if constexpr(t_presorted)
394 check_index = i;
395 else
396 check_index = m_indices[i];
397 t_type distance = distanceSquared(selector, elements[check_index].template as<t_dims, t_type>());
398 if (distance < min_distance_squared)
399 {
400 min_distance_squared = distance;
401 min_index = check_index;
402 if (min_distance_squared <= epsilon)
403 return;
404 }
405 }
406 if (node_heap.size() == 0 || node_heap.extremeComp() >= min_distance_squared)
407 return;
408 index = node_heap.popExtreme();
409 }
410 else
411 {
412 if (!predictBranch(index, node, selector, node_heap, min_distance_squared))
413 return;
414 }
415 }
416 }
417
418 template<bool t_presorted, class t_buffer_type, class t_reference_type>
419 void _getClosestElements(uint04 top_index, const t_reference_type& selector, const t_buffer_type& elements, t_type& min_distance_squared, const t_type& epsilon, MaxHeap<t_type, uint04>& value_heap, uint04 size) const
420 {
421 MinHeap<t_type, uint04> node_heap(cast<uint04>(sqrt(cast<t_type>(m_nodes.size()))));
422 t_type root_distance = distanceSquared(selector, m_nodes[top_index].bounds());
423 if (root_distance >= min_distance_squared)
424 return;
425 uint04 index = top_index;
426 for(;;)
427 {
428 const RNode<t_dims, t_type>& node = m_nodes[index];
429 if (node.isLeaf())
430 {
431 const uint04 end = node.end();
432 for (uint04 i = node.begin(); i < end; ++i)
433 {
434 uint04 check_index;
435 if constexpr (t_presorted)
436 check_index = i;
437 else
438 check_index = m_indices[i];
439 t_type distance = distanceSquared(selector, elements[check_index]);
440 if (distance < min_distance_squared)
441 {
442 value_heap.insert(distance, check_index);
443 if (value_heap.size() > size)
444 {
445 value_heap.deleteExtreme();
446 min_distance_squared = value_heap.extremeComp();
447 if (min_distance_squared <= epsilon)
448 return;
449 }
450 }
451 }
452 if (node_heap.size() == 0 || node_heap.extremeComp() >= min_distance_squared)
453 return;
454 index = node_heap.popExtreme();
455 }
456 else
457 {
458 if (!predictBranch(index, node, selector, node_heap, min_distance_squared))
459 return;
460 }
461 }
462 }
463 template<bool t_presorted, class t_area_type, class t_buffer_type>
464 void _getEnclosedElements(uint04 top_node, t_area_type area, Buffer<bool>& indices, const t_buffer_type& elements) const
465 {
466 TreeIterator iterator(top_node);
467 while (iterator.valid())
468 {
469 uint04 index = iterator.get();
470 const RNode<t_dims, t_type>& node = m_nodes[index];
471 iterator.pop();
472 switch (classify(area, node.bounds()))
473 {
474 case IntersectionTypes::e_inside:
475 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAllT<t_presorted, true>(index, indices);
476 break;
477 case IntersectionTypes::e_outside:
478 break;
479 case IntersectionTypes::e_mixed:
480 if (node.isLeaf())
481 {
482 const uint04 end = node.begin() + node.size();
483 for (uint04 i = node.begin(); i < end; i++)
484 {
485 uint04 idx;
486 if (t_presorted)
487 idx = i;
488 else
489 idx = m_indices[i];
490 if (classify(area, elements[idx]) != IntersectionTypes::e_outside)
491 {
492 indices[idx] = true;
493 }
494 }
495 }
496 else
497 {
498 iterator.addAndGoToIndex(node.left(), node.right());
499 }
500 break;
501 }
502 }
503 }
504
505 template<bool t_is_presorted, class t_area_type, class t_buffer_type>
506 void _getEnclosedElements(uint04 top_node, t_area_type area, Buffer<uint04>& indices, const t_buffer_type& elements) const
507 {
508 TreeIterator iterator(top_node);
509 while (iterator.valid())
510 {
511 uint04 index = iterator.get();
512 const RNode<t_dims, t_type>& node = m_nodes[index];
513 iterator.pop();
514 switch (classify(area, node.bounds()))
515 {
516 case IntersectionTypes::e_inside:
517 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<t_is_presorted>(index, indices);
518 break;
519 case IntersectionTypes::e_mixed:
520 if (node.isLeaf())
521 {
522 const uint04 end = node.begin() + node.size();
523 for (uint04 i = node.begin(); i < end; ++i)
524 {
525 uint04 local_index;
526 if constexpr (t_is_presorted)
527 local_index = i;
528 else
529 local_index = m_indices[i];
530 if (classify(area, elements[local_index]) != IntersectionTypes::e_outside)
531 {
532 indices.add(local_index);
533 }
534 }
535 }
536 else
537 {
538 iterator.addAndGoToIndex(node.left(), node.right());
539 }
540 break;
541 case IntersectionTypes::e_outside:
542 break;
543 }
544 }
545 }
546 template<bool t_presorted, class t_area_type, class t_buffer_type>
547 void _getNearElements(uint04 top_node, t_area_type area, Buffer<bool>& indices, const t_buffer_type& elements, t_type max_distance_sqrd) const
548 {
549 TreeIterator iterator(top_node);
550 while (iterator.valid())
551 {
552 uint04 index = iterator.get();
553 const RNode<t_dims, t_type>& node = m_nodes[index];
554 iterator.pop();
555 t_type distance = distanceSquared(area, node.bounds());
556 if (distance <= max_distance_sqrd)
557 {
558 if (node.isLeaf())
559 {
560 const uint04 end = node.begin() + node.size();
561 for (uint04 i = node.begin(); i < end; i++)
562 {
563 uint04 idx;
564 if (t_presorted)
565 idx = i;
566 else
567 idx = m_indices[i];
568 if (distanceSquared(area, elements[idx]) <= max_distance_sqrd)
569 {
570 indices[idx] = true;
571 }
572 }
573 }
574 else
575 {
576 iterator.addAndGoToIndex(node.left(), node.right());
577 }
578 break;
579 }
580 }
581 }
582 template<bool t_presorted, class t_area_type, class t_buffer_type>
583 void _getNearElements(uint04 top_node, t_area_type area, Buffer<uint04>& indices, const t_buffer_type& elements, t_type max_distance_sqrd) const
584 {
585 TreeIterator iterator(top_node);
586 while (iterator.valid())
587 {
588 uint04 index = iterator.get();
589 const RNode<t_dims, t_type>& node = m_nodes[index];
590 iterator.pop();
591 t_type distance = distanceSquared(area, node.bounds());
592 if (distance <= max_distance_sqrd)
593 {
594 if (node.isLeaf())
595 {
596 const uint04 end = node.begin() + node.size();
597 for (uint04 i = node.begin(); i < end; i++)
598 {
599 uint04 idx;
600 if (t_presorted)
601 idx = i;
602 else
603 idx = m_indices[i];
604 if (distanceSquared(area, elements[idx]) <= max_distance_sqrd)
605 {
606 indices.add(idx);
607 }
608 }
609 }
610 else
611 {
612 iterator.addAndGoToIndex(node.left(), node.right());
613 }
614 }
615 }
616 }
617 template<class t_area_type, class t_buffer_type>
618 uint04 _getNumberOfEnclosedElements(uint04 top_node, const t_area_type& area, const t_buffer_type& elements) const
619 {
620 TreeIterator iterator(top_node);
621 uint04 size = 0;
622 while (iterator.valid())
623 {
624 uint04 index = iterator.get();
625 const RNode<t_dims, t_type>& node = m_nodes[index];
626 iterator.pop();
627 switch (TreeBase<RNode<t_dims, t_type>, t_type, 2>::classify(area, node.bounds()))
628 {
629 case IntersectionTypes::e_inside:
630 size += node.size();
631 break;
632 case IntersectionTypes::e_outside:
633 break;
634 case IntersectionTypes::e_mixed:
635 if (node.isLeaf())
636 {
637 const uint04 end = node.begin() + node.size();
638 for (int i = node.begin(); i < end; i++)
639 {
640 if (TreeBase<RNode<t_dims, t_type>, t_type, 2>::classify(area, elements[m_indices[i]]) != IntersectionTypes::e_outside)
641 {
642 ++size;
643 }
644 }
645 }
646 else
647 {
648 iterator.addAndGoToIndex(node.left(), node.right());
649 }
650 break;
651 }
652 }
653 return size;
654 }
655
656 template<class t_area_type, class t_buffer_type>
657 void _getNearElements(uint04 top_node, t_type max_distance, const t_area_type& area, Buffer<bool>& indices, const t_buffer_type& elements) const
658 {
659 TreeIterator iterator(top_node);
660 while (iterator.valid())
661 {
662 const uint04 index = iterator.get();
663 const RNode<t_dims, t_type>& node = m_nodes[index];
664 iterator.pop();
665 Bounds<t_dims, t_type> bounds = node.bounds();
666 bounds.expand(max_distance);
667 switch (classify(bounds, area))
668 {
669#if __clang__
670 #pragma clang diagnostic push
671 #pragma clang diagnostic ignored "-Wunused-value"//It makes no sense this error is being reported?
672#endif
673 case IntersectionTypes::e_inside:
674 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(index, indices);
675 break;
676#if __clang__
677 #pragma clang diagnostic pop
678#endif
679 case IntersectionTypes::e_outside:
680 break;
681 case IntersectionTypes::e_mixed:
682 if (node.isLeaf())
683 {
684 const uint04 end = node.begin() + node.size();
685 for (uint04 i = node.begin(); i < end; i++)
686 {
687 if (distanceSqaured(area, elements[m_indices[i]]) < max_distance)
688 {
689 indices[m_indices[i]] = true;
690 }
691 }
692 }
693 else
694 {
695 iterator.addAndGoToIndex(node.left(), node.right());
696 }
697 break;
698 }
699 }
700 }
701 template<bool t_presorted, bool t_allow_enable, bool t_allow_disable, class t_area_type, class t_buffer_type>
702 void _getChangedElements(uint04 top_node, const t_area_type& new_area, const t_area_type& old_area, Buffer<bool>& indices, const t_buffer_type& elements) const
703 {
704 TreeIterator iterator(top_node);
705 while (iterator.valid())
706 {
707 bool is_mixed = false;
708 uint04 index = iterator.get();
709 const RNode<t_dims, t_type>& node = m_nodes[index];
710 iterator.pop();
711 switch (classify(new_area, node.bounds()))
712 {
713 case IntersectionTypes::e_inside:
714 switch (classify(old_area, node.bounds()))
715 {
716 case IntersectionTypes::e_inside:
717 break;
718 case IntersectionTypes::e_outside:
719 if(t_allow_enable)
720 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAllT<t_presorted, true>(index, indices);
721 break;
722 case IntersectionTypes::e_mixed:
723 is_mixed = true;
724 break;
725 }
726 break;
727 case IntersectionTypes::e_outside:
728 switch (classify(old_area, node.bounds()))
729 {
730 case IntersectionTypes::e_inside:
731 if(t_allow_disable)
732 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAllT<t_presorted, false>(index, indices);
733 break;
734 case IntersectionTypes::e_outside:
735 break;
736 case IntersectionTypes::e_mixed:
737 is_mixed = true;
738 break;
739 }
740 break;
741 case IntersectionTypes::e_mixed:
742 is_mixed = true;
743 break;
744 }
745 if (is_mixed)
746 {
747 if (node.isLeaf())
748 {
749 const uint04 end = node.begin() + node.size();
750 for (uint04 i = node.begin(); i < end; i++)
751 {
752 uint04 idx;
753 if constexpr (t_presorted)
754 idx = i;
755 else
756 idx = m_indices[i];
757 if constexpr (t_allow_enable && t_allow_disable)
758 {
759 indices[idx] = (classify(new_area, elements[idx]) != IntersectionTypes::e_outside);
760 }
761 else if (t_allow_disable)
762 {
763 if (!indices[idx])
764 continue;
765 if(classify(new_area, elements[idx]) == IntersectionTypes::e_outside)
766 indices[idx] = false;
767 }
768 else if (t_allow_enable)
769 {
770 if (indices[idx])
771 continue;
772 if(classify(new_area, elements[idx]) != IntersectionTypes::e_outside)
773 indices[idx] = true;
774 }
775 }
776 }
777 else
778 {
779 iterator.addAndGoToIndex(node.left(), node.right());
780 }
781 }
782 }
783 }
784
785 template<class t_buffer_type>
786 void _removeValue(uint04 top_node, uint04 index, const t_buffer_type& elements)
787 {
788 bool recalculate_bounds = false;
789 TreeIterator iterator(top_node);
790 while (iterator.valid())
791 {
792 const uint04 node_index = iterator.get();
793 RNode<t_dims, t_type>& node = m_nodes[node_index];
794 if (node.isLeaf())
795 {
796 uint04 end = node.end();
797 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
798 uint04 index_location = Constant<uint04>::Invalid;
799 for (uint04 i = node.begin(); i < end; i++)
800 {
801 uint04 check_index = m_indices[i];
802 if (index != check_index)
803 bounds.addToBounds(elements[check_index].template as<t_dims, t_type>());
804 else
805 index_location = i;
806 }
807 node.setSize(node.size() - 1);
808 if (node.size() != 0)
809 m_indices.swapIndices(index_location, node.end());
810 if (classify(node.bounds(), bounds) == IntersectionTypes::e_inside)
811 recalculate_bounds = true;
812 node.setBounds(bounds);
813 iterator.pop();
814 break;
815 }
816 else
817 {
818
819 bool needs_rebalance = false;
820 if (classify(m_nodes[node.left()].bounds(), elements[index]) == IntersectionTypes::e_inside)
821 {
822 if (needsRebalance(m_nodes[node.left()].size() - 1, m_nodes[node.right()].size()))
823 needs_rebalance = true;
824 else
825 iterator.addAndGoToIndex(node.left());
826 }
827 else
828 {
829 if (needsRebalance(m_nodes[node.left()].size(), m_nodes[node.right()].size() - 1))
830 needs_rebalance = true;
831 else
832 iterator.addAndGoToIndex(node.right());
833 }
834 if (needs_rebalance || node.size() - 1 == m_bucket_size)
835 {
836 Buffer<uint04> indices(node.size());
837 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(node_index, indices);
838 node.setSize(node.size() - 1);
839 indices.removeElement(index);
840 TreeBase<RNode<t_dims, t_type>, t_type, 2>::reclaimChildren(node_index);
841 //TreeBase<RNode<t_dims, t_type>, t_type, 2>::_balanceLeafNode(node_index, elements, indices, 0, indices.size(), false);
842 recalculate_bounds = true;
843 break;
844 }
845 else
846 {
847 node.setSize(node.size() - 1);
848 }
849 }
850 }
851 if (recalculate_bounds)
852 {
853 while (iterator.valid())
854 {
855 if (!recalculateBounds(iterator.get(), elements))
856 return;
857 iterator.pop();
858 }
859 }
860 }
861
862
863 template<class t_node_type, class t_buffer_type>
864 void _moveValue(uint04 top_node, uint04 index, const t_node_type& old_location, const t_buffer_type& elements, bool rebalance)
865 {
866 TreeIterator iterator(top_node);
867 bool recalculate_bounds = false;
868 while (iterator.valid())
869 {
870 const uint04 node_index = iterator.get();
871 RNode<t_dims, t_type>& node = m_nodes[node_index];
872 if (node.isLeaf())
873 {
874 //If the bounds of the node don't change, no need to do anything
875 if (classify(m_nodes[node.left()].bounds(), elements[index]) == IntersectionTypes::e_inside)
876 return;
877 uint04 end = node.end();
878 //Recalculate Node Bounds
879 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
880 uint04 index_location = Constant<uint04>::Invalid;
881 for (uint04 i = node.begin(); i < end; i++)
882 {
883 uint04 check_index = m_indices[i];
884 if (index != check_index)
885 bounds.addToBounds(elements[check_index]);
886 else
887 index_location = i;
888 }
889 //Check to see if bounding box is smaller
890 switch (classify(node.bounds(), bounds))
891 {
892 case IntersectionTypes::e_inside:
893 recalculate_bounds = true;//Node boundary made smaller
894 node.setBounds(bounds);
895 break;
896 case IntersectionTypes::e_mixed:
897 case IntersectionTypes::e_outside:
898 lib_assert(node.bounds() == bounds, "Unexpected Node Resize behavior: Removing object should not increase bounds");
899 recalculate_bounds = false;
900 break;
901 }
902
903 //reset Node Size
904 node.setSize(node.size() - 1);
905 if (node.size() != 0)
906 m_indices.swapIndices(index_location, node.end());
907
908 iterator.pop();
909 break;//Break to begin resetting bounds
910 }
911 else
912 {
913 if (classify(m_nodes[node.left()].bounds(), old_location) == IntersectionTypes::e_inside)
914 {
915 iterator.addAndGoToIndex(node.left());
916 }
917 else
918 {
919 lib_assert(classify(m_nodes[node.right()].bounds(), old_location) == IntersectionTypes::e_inside, "Original Element not in either bounds");
920 iterator.addAndGoToIndex(node.right());
921 }
922 }
923 }
924 bool added_in = false;
925 while (iterator.valid() && (!added_in || recalculate_bounds))
926 {
927 const uint04 node_index = iterator.get();
928 if (recalculate_bounds)
929 {
930 recalculate_bounds = recalculateBounds(node_index, elements);
931 }
932 if (!added_in)
933 {
934 RNode<t_dims, t_type>& node = m_nodes[node_index];
935 if (classify(node.bounds(), elements[index]) == IntersectionTypes::e_inside)
936 {
937 TreeBase<RNode<t_dims, t_type>, t_type, 2>::_addValue(node_index, index, elements, rebalance);
938 added_in = true;
939 }
940 }
941 iterator.pop();
942 }
943 if (!added_in)
944 {
945 TreeBase<RNode<t_dims, t_type>, t_type, 2>::_addValue(top_node, index, elements, rebalance);
946 }
947 }
948
949 bool needsRebalance(uint04 left_size, uint04 right_size)
950 {
951 const uint04 total_size = left_size + right_size;
952 return (left_size < total_size / 3 || right_size < total_size / 3);
953 }
954
955 bool useBulkResize(uint04 change_size)
956 {
957 return (change_size > TreeBase<RNode<t_dims, t_type>, t_type, 2>::size() / 4);
958 }
959 template<class t_buffer_type>
960 bool recalculateBounds(uint04 node_index, const t_buffer_type& elements)
961 {
962 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
963 RNode<t_dims, t_type>& node = m_nodes[node_index];
964 if (node.isLeaf())
965 {
966 uint04 end = node.end();
967 for (uint04 i = node.begin(); i < end; i++)
968 {
969 bounds.addToBounds(elements[m_indices[i]]);
970 }
971 }
972 else
973 {
974 bounds = Bounds<t_dims, t_type>(m_nodes[node.left()].bounds(), m_nodes[node.right()].bounds());
975 }
976 if (classify(node.bounds(), bounds) == IntersectionTypes::e_inside)
977 return false;
978 node.setBounds(bounds);
979 return true;
980 }
981 protected:
982 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
983 void _addValues(uint04 top_node, Buffer<uint04> indices, const t_buffer_type& elements, bool is_precise)
984 {
985 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(top_node, indices);
986 TreeBase<RNode<t_dims, t_type>, t_type, 2>::clear();
987 TreeBase<RNode<t_dims, t_type>, t_type, 2>::reclaimChildren(top_node);
988
989 uint04 max_node_size = 1;
990 uint04 max_index_size = m_bucket_size;
991 uint04 load_size = indices.size();
992 uint04 level = 1;
993 while (load_size >= m_bucket_size)
994 {
995 load_size = cast<uint04>(ceil(load_size / 2));
996 max_index_size = 2 * max_index_size;
997 max_node_size = cast<uint04>(pow(2, level++)) + max_node_size;
998 }
999 m_indices.ensureCapacity(max_index_size);
1000 m_nodes.ensureCapacity(max_node_size);
1001
1002 _balanceLeafNode<t_has_nans, t_uses_boundary>(top_node, elements, indices, 0, indices.size(), is_precise);
1003 }
1004
1005
1006 template<bool t_has_nans, bool t_uses_boundary, class t_buffer_type>
1007 void _addValue(uint04 node_index, uint04 index, const t_buffer_type& elements, bool balance)
1008 {
1009 Bounds<t_dims, t_type> bounds = m_nodes[node_index].bounds();
1010 const auto value = elements[index].template as<t_dims, t_type>();
1011 bounds.addToBounds(value);
1012 for (;;)
1013 {
1014 RNode<t_dims, t_type>& node = m_nodes[node_index];
1015 node.setBounds(bounds);
1016 if (node.isLeaf())
1017 {
1018 if (node.size() == m_bucket_size)
1019 {
1020 Buffer<uint04> indices(m_bucket_size + 1);
1021 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(node_index, indices);
1022 TreeBase<RNode<t_dims, t_type>, t_type, 2>::reclaimChildren(node_index);
1023 indices.add(index);
1024 _balanceLeafNode<t_has_nans, t_uses_boundary>(node_index, elements, indices, 0, m_bucket_size + 1, false);
1025 }
1026 else
1027 {
1028 m_indices[node.begin() + node.size()] = index;
1029 node.setSize(node.size() + 1);
1030 }
1031 return;
1032 }
1033 else
1034 {
1035 Bounds<t_dims, t_type> left = m_nodes[node.left()].bounds();
1036 Bounds<t_dims, t_type> right = m_nodes[node.right()].bounds();
1037
1038 left.addToBounds(value);
1039 right.addToBounds(value);
1040 bool needs_rebalance = false;
1041 t_type surface_diff =
1042 (left.surfaceArea() - m_nodes[node.left()].bounds().surfaceArea())
1043 - (right.surfaceArea() - m_nodes[node.right()].bounds().surfaceArea());
1044 if(surface_diff == 0)//Volumes are equal, insert to least full.
1045 {
1046 if (m_nodes[node.left()].size() < m_nodes[node.right()].size())
1047 {
1048 node_index = node.left();
1049 bounds = left;
1050 }
1051 else
1052 {
1053 node_index = node.right();
1054 bounds = right;
1055 }
1056 }
1057 else if (surface_diff < 0)//better to add it to left side
1058 {
1059 if (balance && needsRebalance(
1060 m_nodes[node.left()].size() + 1
1061 , m_nodes[node.right()].size()))
1062 needs_rebalance = true;
1063 else
1064 node_index = node.left();
1065 bounds = left;
1066 }
1067 else//better to add it to right side
1068 {
1069 if (balance && needsRebalance(
1070 m_nodes[node.left()].size()
1071 , m_nodes[node.right()].size() + 1))
1072 needs_rebalance = true;
1073 else
1074 node_index = node.right();
1075 bounds = right;
1076 }
1077 if (needs_rebalance)
1078 {
1079 Buffer<uint04> indices(node.size() + 1);
1080 TreeBase<RNode<t_dims, t_type>, t_type, 2>::template _getAll<false>(node_index, indices);
1081 indices.add(index);
1082 TreeBase<RNode<t_dims, t_type>, t_type, 2>::reclaimChildren(node_index);
1083 _balanceLeafNode<t_has_nans, t_uses_boundary>(node_index, elements, indices, 0, indices.size(), false);
1084 return;
1085 }
1086 else
1087 {
1088 node.setSize(node.size() + 1);
1089 }
1090 }
1091 }
1092 }
1093 //Returns true if bounds changed, false if stayed the same
1094
1095
1096 void _makeWriteable()
1097 {
1098 Buffer<uint04> indices(TreeBase<RNode<t_dims, t_type>, t_type, 2>::size());
1099
1100 TreeIterator iterator(root_node);
1101 while (iterator.valid())
1102 {
1103 RNode<t_dims, t_type>& node = m_nodes[iterator.get()];
1104 iterator.pop();
1105 if (node.isLeaf())
1106 {
1107 node.setBegin(iterator.get());
1108 indices.addAll(m_indices.begin(node.begin()), node.size());
1109 }
1110 else
1111 iterator.addAndGoToIndex(node.left(), node.right());
1112 }
1113 m_indices = indices;
1114 }
1115 };
1116
1117
1118 template<uint01 t_dims, class t_type>
1119 class RTree : public Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>
1120 {
1121 public:
1122 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_nodes;
1123 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::root_node;
1124 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_indices;
1125 using TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_bucket_size;
1126 RTree<t_dims, t_type>()
1127 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(16)
1128 {}
1129 explicit RTree<t_dims, t_type>(uint04 bucket_size)
1130 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(bucket_size)
1131 {}
1132 RTree<t_dims, t_type>(const RTreeBase<t_dims, t_type>& tree)
1133 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(tree)
1134 {}
1135 RTree<t_dims, t_type>(RTreeBase<t_dims, t_type>&& tree)
1136 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(std::move(tree))
1137 {}
1138 RTree<t_dims, t_type>(const RTree<t_dims, t_type>& value)
1139 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(16)
1140 {
1141 m_bucket_size = value.m_bucket_size;
1142 m_indices = value.m_indices;
1143 m_nodes = value.m_nodes;
1144 TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions = value.m_available_node_positions;
1145 TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions = value.m_available_indexed_positions;
1146 }
1147 RTree<t_dims, t_type>(RTree<t_dims, t_type>&& value) noexcept
1148 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(64)
1149 {
1150 m_bucket_size = value.m_bucket_size;
1151 std::swap(m_indices, value.m_indices);
1152 std::swap(m_nodes, value.m_nodes);
1153 std::swap(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions, value.m_available_node_positions);
1154 std::swap(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions, value.m_available_indexed_positions);
1155 }
1156 Bounds<t_dims, t_type> bounds() const
1157 {
1158 const RNode<t_dims, t_type>& node = m_nodes[root_node];
1159 return node.bounds();
1160 }
1161 protected:
1162 RTree<t_dims, t_type>(const Buffer<RNode<t_dims, t_type>>& nodes, const Buffer<uint04>& indices, bool is_read_only)
1163 : Tree<t_dims, t_type, RTreeBase<t_dims, t_type>>(nodes, indices, is_read_only)
1164 {}
1165 public:
1166 inline RTree& operator=(const RTree& value)
1167 {
1168 m_bucket_size = value.m_bucket_size;
1169 m_indices = value.m_indices;
1170 m_nodes = value.m_nodes;
1171 TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions = value.m_available_node_positions;
1172 TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions = value.m_available_indexed_positions;
1173 return (*this);
1174 }
1175 inline RTree& operator=(RTree&& value)
1176 {
1177 m_bucket_size = value.m_bucket_size;
1178 std::swap(m_indices, value.m_indices);
1179 std::swap(m_nodes, value.m_nodes);
1180 std::swap(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions, value.m_available_node_positions);
1181 std::swap(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions, value.m_available_indexed_positions);
1182 return (*this);
1183 }
1184 void mapToFile(BinaryFileTableInfo& file, Buffer<BinaryCompressionObject>& objects, uint04 compression_index = 0)
1185 {
1186 file.file.write(m_bucket_size);
1187 file.file.writeCompression(objects[compression_index + 0]);
1188 file.file.writeCompression(objects[compression_index + 1]);
1189 file.file.writeCompression(objects[compression_index + 2]);
1190 file.file.writeCompression(objects[compression_index + 3]);
1191 }
1192 void compress(Buffer<BinaryCompressionObject>& objects, Buffer<Buffer<uint01>>& compressed_data, uint04 compression_index, uint04 internal_index)
1193 {
1194 switch (internal_index)
1195 {
1196 case 0:
1197 Compressor::Compress(objects[compression_index]
1198 , compressed_data[compression_index]
1199 , m_indices);
1200 break;
1201 case 1:
1202 Compressor::Compress(objects[compression_index]
1203 , compressed_data[compression_index]
1204 , m_nodes);
1205 break;
1206 case 2:
1207 Compressor::Compress(objects[compression_index]
1208 , compressed_data[compression_index]
1209 , TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions);
1210 break;
1211 case 3:
1212 Compressor::Compress(objects[compression_index]
1213 , compressed_data[compression_index]
1214 , TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions);
1215 break;
1216 }
1217
1218 }
1219 void mapToFile(BinaryFileTableInfo& table_info, CompressionMode mode)
1220 {
1221 table_info.file.write(m_bucket_size);
1222 table_info.file.write(m_indices, mode);
1223 table_info.file.write(m_nodes, mode);
1224 table_info.file.write(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions, mode);
1225 table_info.file.write(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions, mode);
1226 }
1227 void mapFromFile(BinaryFileTableInfo& table_info)
1228 {
1229 m_bucket_size = table_info.file.read<uint04>();
1230 if (table_info.version_number < 1762047417)
1231 table_info.file.skip<bool>();//placeholder
1232 table_info.file.read(m_indices);
1233 table_info.file.read(m_nodes);
1234 table_info.file.read(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_node_positions);
1235 table_info.file.read(TreeBase<RNode<t_dims, t_type>, t_type, 2>::m_available_indexed_positions);
1236 }
1237 virtual const char* getTreeType() const override
1238 {
1239 return "R Tree";
1240 }
1241 };
1242}
1243/*--------------------------------------------------------------------------------------------
1244\endinternal
1245 *-----------------------------------------------------------------------------------------**/
Compressor::Compress
static std::enable_if<!ObjectInfo< t_type >::Buffer >::type Compress(BinaryCompressionObject &object, Buffer< uint01 > &compression_data, const Buffer< t_type, t_memory_manager > &data)
Compresses a buffer of non-buffer (flat) elements into the given compression object.
Definition Compressor.h:200
NDEVR
The primary namespace for the NDEVR SDK.
Definition ArialTileFetcherModule.h:35
IsValid
static constexpr bool IsValid(const Angle< t_type > &value)
Checks whether the given Angle holds a valid value.
Definition Angle.h:398
Invalid
constexpr HSLColor Constant< HSLColor >::Invalid
The invalid HSLColor constant with all components set to invalid.
Definition HSLColor.h:264
uint04
uint32_t uint04
-Defines an alias representing a 4 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:97
CompressionMode
CompressionMode
Forward declaration of the Module struct for module metadata.
Definition Compressor.h:17
uint01
uint8_t uint01
-Defines an alias representing a 1 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:81
NDPO::file
@ file
The source file path associated with this object.
Definition DesignProperties.h:257
NDPO::compressed_data
@ compressed_data
Compressed binary data storage.
Definition DesignProperties.h:270
sqrt
t_type sqrt(const t_type &value)
Definition VectorFunctions.hpp:1181
Min
constexpr HSLColor Constant< HSLColor >::Min
The minimum HSLColor constant with saturation, brightness, and alpha at zero.
Definition HSLColor.h:266
cast
constexpr t_to cast(const Angle< t_from > &value)
Casts an Angle from one backing type to another.
Definition Angle.h:408