GEOS 3.12.0
TemplateSTRtree.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2020-2021 Daniel Baston
7 *
8 * This is free software; you can redistribute and/or modify it under
9 * the terms of the GNU Lesser General Public Licence as published
10 * by the Free Software Foundation.
11 * See the COPYING file for more information.
12 *
13 **********************************************************************/
14
15#pragma once
16
17#include <geos/geom/Geometry.h>
18#include <geos/index/SpatialIndex.h> // for inheritance
19#include <geos/index/chain/MonotoneChain.h>
20#include <geos/index/ItemVisitor.h>
21#include <geos/util.h>
22
23#include <geos/index/strtree/TemplateSTRNode.h>
24#include <geos/index/strtree/TemplateSTRNodePair.h>
25#include <geos/index/strtree/TemplateSTRtreeDistance.h>
26#include <geos/index/strtree/Interval.h>
27
28#include <vector>
29#include <queue>
30#include <mutex>
31
32namespace geos {
33namespace index {
34namespace strtree {
35
56template<typename ItemType, typename BoundsTraits>
58public:
59 using Node = TemplateSTRNode<ItemType, BoundsTraits>;
60 using NodeList = std::vector<Node>;
61 using NodeListIterator = typename NodeList::iterator;
62 using BoundsType = typename BoundsTraits::BoundsType;
63
64 class Iterator {
65 public:
66 using iterator_category = std::forward_iterator_tag;
67 using value_type = ItemType;
68 using difference_type = typename NodeList::const_iterator::difference_type;
69 using pointer = ItemType*;
70 using reference = ItemType&;
71
72 Iterator(typename NodeList::const_iterator&& iter,
73 typename NodeList::const_iterator&& end) : m_iter(iter), m_end(end) {
74 skipDeleted();
75 }
76
77 const ItemType& operator*() const {
78 return m_iter->getItem();
79 }
80
81 Iterator& operator++() {
82 m_iter++;
83 skipDeleted();
84 return *this;
85 }
86
87 friend bool operator==(const Iterator& a, const Iterator& b) {
88 return a.m_iter == b.m_iter;
89 }
90
91 friend bool operator!=(const Iterator& a, const Iterator& b) {
92 return a.m_iter != b.m_iter;
93 }
94
95 private:
96 void skipDeleted() {
97 while(m_iter != m_end && m_iter->isDeleted()) {
98 m_iter++;
99 }
100 }
101
102 typename NodeList::const_iterator m_iter;
103 typename NodeList::const_iterator m_end;
104 };
105
106 class Items {
107 public:
108 explicit Items(TemplateSTRtreeImpl& tree) : m_tree(tree) {}
109
110 Iterator begin() {
111 return Iterator(m_tree.nodes.cbegin(),
112 std::next(m_tree.nodes.cbegin(), static_cast<long>(m_tree.numItems)));
113 }
114
115 Iterator end() {
116 return Iterator(std::next(m_tree.nodes.cbegin(), static_cast<long>(m_tree.numItems)),
117 std::next(m_tree.nodes.cbegin(), static_cast<long>(m_tree.numItems)));
118 }
119 private:
120 TemplateSTRtreeImpl& m_tree;
121 };
122
125
130 explicit TemplateSTRtreeImpl(size_t p_nodeCapacity = 10) :
131 root(nullptr),
132 nodeCapacity(p_nodeCapacity),
133 numItems(0)
134 {}
135
141 TemplateSTRtreeImpl(size_t p_nodeCapacity, size_t itemCapacity) :
142 root(nullptr),
143 nodeCapacity(p_nodeCapacity),
144 numItems(0) {
145 auto finalSize = treeSize(itemCapacity);
146 nodes.reserve(finalSize);
147 }
148
153 root(other.root),
154 nodeCapacity(other.nodeCapacity),
155 numItems(other.numItems) {
156 nodes = other.nodes;
157 }
158
160 {
161 root = other.root;
162 nodeCapacity = other.nodeCapacity;
163 numItems = other.numItems;
164 nodes = other.nodes;
165 return *this;
166 }
167
171
173 void insert(ItemType&& item) {
174 insert(BoundsTraits::fromItem(item), std::forward<ItemType>(item));
175 }
176
178 void insert(const ItemType& item) {
179 insert(BoundsTraits::fromItem(item), item);
180 }
181
183 void insert(const BoundsType& itemEnv, ItemType&& item) {
184 if (!BoundsTraits::isNull(itemEnv)) {
185 createLeafNode(std::forward<ItemType>(item), itemEnv);
186 }
187 }
188
190 void insert(const BoundsType& itemEnv, const ItemType& item) {
191 if (!BoundsTraits::isNull(itemEnv)) {
192 createLeafNode(item, itemEnv);
193 }
194 }
195
199
201 template<typename ItemDistance>
202 std::pair<ItemType, ItemType> nearestNeighbour(ItemDistance& distance) {
203 return nearestNeighbour(*this, distance);
204 }
205
207 template<typename ItemDistance>
208 std::pair<ItemType, ItemType> nearestNeighbour() {
209 ItemDistance id;
210 return nearestNeighbour(*this);
211 }
212
214 template<typename ItemDistance>
216 ItemDistance & distance) {
217 if (!getRoot() || !other.getRoot()) {
218 return { nullptr, nullptr };
219 }
220
221 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(distance);
222 return td.nearestNeighbour(*root, *other.root);
223 }
224
226 template<typename ItemDistance>
227 std::pair<ItemType, ItemType> nearestNeighbour(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other) {
228 ItemDistance id;
229 return nearestNeighbour(other, id);
230 }
231
232 template<typename ItemDistance>
233 ItemType nearestNeighbour(const BoundsType& env, const ItemType& item, ItemDistance& itemDist) {
234 build();
235
236 if (getRoot() == nullptr) {
237 return nullptr;
238 }
239
240 TemplateSTRNode<ItemType, BoundsTraits> bnd(item, env);
241 TemplateSTRNodePair<ItemType, BoundsTraits, ItemDistance> pair(*getRoot(), bnd, itemDist);
242
243 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
244 return td.nearestNeighbour(pair).first;
245 }
246
247 template<typename ItemDistance>
248 ItemType nearestNeighbour(const BoundsType& env, const ItemType& item) {
249 ItemDistance id;
250 return nearestNeighbour(env, item, id);
251 }
252
253 template<typename ItemDistance>
254 bool isWithinDistance(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other, double maxDistance) {
255 ItemDistance itemDist;
256
257 if (!getRoot() || !other.getRoot()) {
258 return false;
259 }
260
261 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
262 return td.isWithinDistance(*root, *other.root, maxDistance);
263 }
264
268
269 // Query the tree using the specified visitor. The visitor must be callable
270 // either with a single argument of `const ItemType&` or with the
271 // arguments `(const BoundsType&, const ItemType&).
272 // The visitor need not return a value, but if it does return a value,
273 // false values will be taken as a signal to stop the query.
274 template<typename Visitor>
275 void query(const BoundsType& queryEnv, Visitor &&visitor) {
276 if (!built()) {
277 build();
278 }
279
280 if (root && root->boundsIntersect(queryEnv)) {
281 if (root->isLeaf()) {
282 visitLeaf(visitor, *root);
283 } else {
284 query(queryEnv, *root, visitor);
285 }
286 }
287 }
288
289 // Query the tree for all pairs whose bounds intersect. The visitor must
290 // be callable with arguments (const ItemType&, const ItemType&).
291 // The visitor will be called for each pair once, with first-inserted
292 // item used for the first argument.
293 // The visitor need not return a value, but if it does return a value,
294 // false values will be taken as a signal to stop the query.
295 template<typename Visitor>
296 void queryPairs(Visitor&& visitor) {
297 if (!built()) {
298 build();
299 }
300
301 if (numItems < 2) {
302 return;
303 }
304
305 for (std::size_t i = 0; i < numItems; i++) {
306 queryPairs(nodes[i], *root, visitor);
307 }
308 }
309
310 // Query the tree and collect items in the provided vector.
311 void query(const BoundsType& queryEnv, std::vector<ItemType>& results) {
312 query(queryEnv, [&results](const ItemType& x) {
313 results.push_back(x);
314 });
315 }
316
320 Items items() {
321 build();
322 return Items(*this);
323 }
324
329 template<typename F>
330 void iterate(F&& func) {
331 auto n = built() ? numItems : nodes.size();
332 for (size_t i = 0; i < n; i++) {
333 if (!nodes[i].isDeleted()) {
334 func(nodes[i].getItem());
335 }
336 }
337 }
338
342
343 bool remove(const BoundsType& itemEnv, const ItemType& item) {
344 build();
345
346 if (root == nullptr) {
347 return false;
348 }
349
350 if (root->isLeaf()) {
351 if (!root->isDeleted() && root->getItem() == item) {
352 root->removeItem();
353 return true;
354 }
355 return false;
356 }
357
358 return remove(itemEnv, *root, item);
359 }
360
364
366 bool built() const {
367 return root != nullptr;
368 }
369
371 const Node* getRoot() {
372 build();
373 return root;
374 }
375
377
379 void build() {
380 std::lock_guard<std::mutex> lock(lock_);
381
382 if (built()) {
383 return;
384 }
385
386 if (nodes.empty()) {
387 return;
388 }
389
390 numItems = nodes.size();
391
392 // compute final size of tree and set it aside in a single
393 // block of memory
394 auto finalSize = treeSize(numItems);
395 nodes.reserve(finalSize);
396
397 // begin and end define a range of nodes needing parents
398 auto begin = nodes.begin();
399 auto number = static_cast<size_t>(std::distance(begin, nodes.end()));
400
401 while (number > 1) {
402 createParentNodes(begin, number);
403 std::advance(begin, static_cast<long>(number)); // parents just added become children in the next round
404 number = static_cast<size_t>(std::distance(begin, nodes.end()));
405 }
406
407 assert(finalSize == nodes.size());
408
409 root = &nodes.back();
410 }
411
412protected:
413 std::mutex lock_;
414 NodeList nodes; //**< a list of all leaf and branch nodes in the tree. */
415 Node* root; //**< a pointer to the root node, if the tree has been built. */
416 size_t nodeCapacity; //*< maximum number of children of each node */
417 size_t numItems; //*< total number of items in the tree, if it has been built. */
418
419 // Prevent instantiation of base class.
420 // ~TemplateSTRtreeImpl() = default;
421
422 void createLeafNode(ItemType&& item, const BoundsType& env) {
423 nodes.emplace_back(std::forward<ItemType>(item), env);
424 }
425
426 void createLeafNode(const ItemType& item, const BoundsType& env) {
427 nodes.emplace_back(item, env);
428 }
429
430 void createBranchNode(const Node *begin, const Node *end) {
431 assert(nodes.size() < nodes.capacity());
432 nodes.emplace_back(begin, end);
433 }
434
435 // calculate what the tree size will be when it is build. This is simply
436 // a version of createParentNodes that doesn't actually create anything.
437 size_t treeSize(size_t numLeafNodes) {
438 size_t nodesInTree = numLeafNodes;
439
440 size_t nodesWithoutParents = numLeafNodes;
441 while (nodesWithoutParents > 1) {
442 auto numSlices = sliceCount(nodesWithoutParents);
443 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
444
445 size_t parentNodesAdded = 0;
446 for (size_t j = 0; j < numSlices; j++) {
447 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
448 nodesWithoutParents -= nodesInSlice;
449
450 parentNodesAdded += static_cast<size_t>(std::ceil(
451 static_cast<double>(nodesInSlice) / static_cast<double>(nodeCapacity)));
452 }
453
454 nodesInTree += parentNodesAdded;
455 nodesWithoutParents = parentNodesAdded;
456 }
457
458 return nodesInTree;
459 }
460
461 void createParentNodes(const NodeListIterator& begin, size_t number) {
462 // Arrange child nodes in two dimensions.
463 // First, divide them into vertical slices of a given size (left-to-right)
464 // Then create nodes within those slices (bottom-to-top)
465 auto numSlices = sliceCount(number);
466 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
467
468 // We could sort all of the nodes here, but we don't actually need them to be
469 // completely sorted. They need to be sorted enough for each node to end up
470 // in the right vertical slice, but their relative position within the slice
471 // doesn't matter. So we do a partial sort for each slice below instead.
472 auto end = begin + static_cast<long>(number);
473 sortNodesX(begin, end);
474
475 auto startOfSlice = begin;
476 for (decltype(numSlices) j = 0; j < numSlices; j++) {
477 // end iterator is being invalidated at each iteration
478 end = begin + static_cast<long>(number);
479 auto nodesRemaining = static_cast<size_t>(std::distance(startOfSlice, end));
480 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
481 auto endOfSlice = std::next(startOfSlice, static_cast<long>(nodesInSlice));
482
483 // Make sure that every node that should be in this slice ends up somewhere
484 // between startOfSlice and endOfSlice. We don't require any ordering among
485 // nodes between startOfSlice and endOfSlice.
486 //partialSortNodes(startOfSlice, endOfSlice, end);
487
488 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
489
490 startOfSlice = endOfSlice;
491 }
492 }
493
494 void addParentNodesFromVerticalSlice(const NodeListIterator& begin, const NodeListIterator& end) {
495 if (BoundsTraits::TwoDimensional::value) {
496 sortNodesY(begin, end);
497 }
498
499 // Arrange the nodes vertically and full up parent nodes sequentially until they're full.
500 // A possible improvement would be to rework this such so that if we have 81 nodes we
501 // put 9 into each parent instead of 10 or 1.
502 auto firstChild = begin;
503 while (firstChild != end) {
504 auto childrenRemaining = static_cast<size_t>(std::distance(firstChild, end));
505 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
506 auto lastChild = std::next(firstChild, static_cast<long>(childrenForNode));
507
508 //partialSortNodes(firstChild, lastChild, end);
509
510 // Ideally we would be able to store firstChild and lastChild instead of
511 // having to convert them to pointers, but I wasn't sure how to access
512 // the NodeListIterator type from within Node without creating some weird
513 // circular dependency.
514 const Node *ptr_first = &*firstChild;
515 const Node *ptr_end = ptr_first + childrenForNode;
516
517 createBranchNode(ptr_first, ptr_end);
518 firstChild = lastChild;
519 }
520 }
521
522 void sortNodesX(const NodeListIterator& begin, const NodeListIterator& end) {
523 std::sort(begin, end, [](const Node &a, const Node &b) {
524 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
525 });
526 }
527
528 void sortNodesY(const NodeListIterator& begin, const NodeListIterator& end) {
529 std::sort(begin, end, [](const Node &a, const Node &b) {
530 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
531 });
532 }
533
534 // Helper function to visit an item using a visitor that has no return value.
535 // In this case, we will always return true, indicating that querying should
536 // continue.
537 template<typename Visitor,
538 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
539 bool visitLeaf(Visitor&& visitor, const Node& node)
540 {
541 visitor(node.getItem());
542 return true;
543 }
544
545 template<typename Visitor,
546 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
547 bool visitLeaves(Visitor&& visitor, const Node& node1, const Node& node2)
548 {
549 visitor(node1.getItem(), node2.getItem());
550 return true;
551 }
552
553 // MSVC 2015 does not implement C++11 expression SFINAE and considers this a
554 // redefinition of a previous method
555#if !defined(_MSC_VER) || _MSC_VER >= 1910
556 template<typename Visitor,
557 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
558 bool visitLeaf(Visitor&& visitor, const Node& node)
559 {
560 visitor(node.getBounds(), node.getItem());
561 return true;
562 }
563#endif
564
565 // If the visitor function does return a value, we will use this to indicate
566 // that querying should continue.
567 template<typename Visitor,
568 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr>
569 bool visitLeaf(Visitor&& visitor, const Node& node)
570 {
571 return visitor(node.getItem());
572 }
573
574 template<typename Visitor,
575 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
576 bool visitLeaves(Visitor&& visitor, const Node& node1, const Node& node2)
577 {
578 return visitor(node1.getItem(), node2.getItem());
579 }
580
581 // MSVC 2015 does not implement C++11 expression SFINAE and considers this a
582 // redefinition of a previous method
583#if !defined(_MSC_VER) || _MSC_VER >= 1910
584 template<typename Visitor,
585 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr>
586 bool visitLeaf(Visitor&& visitor, const Node& node)
587 {
588 return visitor(node.getBounds(), node.getItem());
589 }
590#endif
591
592 template<typename Visitor>
593 bool query(const BoundsType& queryEnv,
594 const Node& node,
595 Visitor&& visitor) {
596
597 assert(!node.isLeaf());
598
599 for (auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
600 if (child->boundsIntersect(queryEnv)) {
601 if (child->isLeaf()) {
602 if (!child->isDeleted()) {
603 if (!visitLeaf(visitor, *child)) {
604 return false; // abort query
605 }
606 }
607 } else {
608 if (!query(queryEnv, *child, visitor)) {
609 return false; // abort query
610 }
611 }
612 }
613 }
614 return true; // continue searching
615 }
616
617 template<typename Visitor>
618 bool queryPairs(const Node& queryNode,
619 const Node& searchNode,
620 Visitor&& visitor) {
621
622 assert(!searchNode.isLeaf());
623
624 for (auto* child = searchNode.beginChildren(); child < searchNode.endChildren(); ++child) {
625 if (child->isLeaf()) {
626 // Only visit leaf nodes if they have a higher address than the query node,
627 // to avoid processing the same pairs twice.
628 if (child > &queryNode && !child->isDeleted() && child->boundsIntersect(queryNode.getBounds())) {
629 if (!visitLeaves(visitor, queryNode, *child)) {
630 return false; // abort query
631 }
632 }
633 } else {
634 if (child->boundsIntersect(queryNode.getBounds())) {
635 if (!queryPairs(queryNode, *child, visitor)) {
636 return false; // abort query
637 }
638 }
639 }
640 }
641
642 return true; // continue searching
643 }
644
645 bool remove(const BoundsType& queryEnv,
646 const Node& node,
647 const ItemType& item) {
648
649 assert(!node.isLeaf());
650
651 for (auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
652 if (child->boundsIntersect(queryEnv)) {
653 if (child->isLeaf()) {
654 if (!child->isDeleted() && child->getItem() == item) {
655 // const cast is ugly, but alternative seems to be to remove all
656 // const qualifiers in Node and open up mutability everywhere?
657 auto mutableChild = const_cast<Node*>(child);
658 mutableChild->removeItem();
659 return true;
660 }
661 } else {
662 bool removed = remove(queryEnv, *child, item);
663 if (removed) {
664 return true;
665 }
666 }
667 }
668 }
669
670 return false;
671 }
672
673 size_t sliceCount(size_t numNodes) const {
674 double minLeafCount = std::ceil(static_cast<double>(numNodes) / static_cast<double>(nodeCapacity));
675
676 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
677 }
678
679 static size_t sliceCapacity(size_t numNodes, size_t numSlices) {
680 return static_cast<size_t>(std::ceil(static_cast<double>(numNodes) / static_cast<double>(numSlices)));
681 }
682};
683
684struct EnvelopeTraits {
685 using BoundsType = geom::Envelope;
686 using TwoDimensional = std::true_type;
687
688 static bool intersects(const BoundsType& a, const BoundsType& b) {
689 return a.intersects(b);
690 }
691
692 static double size(const BoundsType& a) {
693 return a.getArea();
694 }
695
696 static double distance(const BoundsType& a, const BoundsType& b) {
697 return a.distance(b);
698 }
699
700 static double maxDistance(const BoundsType& a, const BoundsType& b) {
701 return a.maxDistance(b);
702 }
703
704 static BoundsType empty() {
705 return {};
706 }
707
708 template<typename ItemType>
709 static const BoundsType& fromItem(const ItemType& i) {
710 return *(i->getEnvelopeInternal());
711 }
712
713 template<typename ItemType>
714 static const BoundsType& fromItem(ItemType&& i) {
715 return *(i->getEnvelopeInternal());
716 }
717
718 static double getX(const BoundsType& a) {
719 return a.getMinX() + a.getMaxX();
720 }
721
722 static double getY(const BoundsType& a) {
723 return a.getMinY() + a.getMaxY();
724 }
725
726 static void expandToInclude(BoundsType& a, const BoundsType& b) {
727 a.expandToInclude(b);
728 }
729
730 static bool isNull(const BoundsType& a) {
731 return a.isNull();
732 }
733};
734
735struct IntervalTraits {
736 using BoundsType = Interval;
737 using TwoDimensional = std::false_type;
738
739 static bool intersects(const BoundsType& a, const BoundsType& b) {
740 return a.intersects(&b);
741 }
742
743 static double size(const BoundsType& a) {
744 return a.getWidth();
745 }
746
747 static double getX(const BoundsType& a) {
748 return a.getMin() + a.getMax();
749 }
750
751 static double getY(const BoundsType& a) {
752 return a.getMin() + a.getMax();
753 }
754
755 static void expandToInclude(BoundsType& a, const BoundsType& b) {
756 a.expandToInclude(&b);
757 }
758
759 static bool isNull(const BoundsType& a) {
760 (void) a;
761 return false;
762 }
763};
764
765
766template<typename ItemType, typename BoundsTraits = EnvelopeTraits>
767class TemplateSTRtree : public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
768public:
769 using TemplateSTRtreeImpl<ItemType, BoundsTraits>::TemplateSTRtreeImpl;
770};
771
772// When ItemType is a pointer and our bounds are geom::Envelope, adopt
773// the SpatialIndex interface which requires queries via an envelope
774// and items to be representable as void*.
775template<typename ItemType>
776class TemplateSTRtree<ItemType*, EnvelopeTraits> : public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>, public SpatialIndex {
777public:
778 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::TemplateSTRtreeImpl;
779 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::insert;
780 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::query;
781 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::remove;
782
783 // The SpatialIndex methods only work when we are storing a pointer type.
784 void query(const geom::Envelope* queryEnv, std::vector<void*>& results) override {
785 query(*queryEnv, [&results](const ItemType* x) {
786 results.push_back(const_cast<void*>(static_cast<const void*>(x)));
787 });
788 }
789
790 void query(const geom::Envelope* queryEnv, ItemVisitor& visitor) override {
791 query(*queryEnv, [&visitor](const ItemType* x) {
792 visitor.visitItem(const_cast<void*>(static_cast<const void*>(x)));
793 });
794 }
795
796 bool remove(const geom::Envelope* itemEnv, void* item) override {
797 return remove(*itemEnv, static_cast<ItemType*>(item));
798 }
799
800 void insert(const geom::Envelope* itemEnv, void* item) override {
801 insert(*itemEnv, std::move(static_cast<ItemType*>(item)));
802 }
803};
804
805
806}
807}
808}
A function method which computes the distance between two ItemBoundables in an STRtree....
Definition ItemDistance.h:33
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For one- or two-dimensiona...
Definition TemplateSTRtree.h:57
void build()
Definition TemplateSTRtree.h:379
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other)
Definition TemplateSTRtree.h:227
std::pair< ItemType, ItemType > nearestNeighbour()
Definition TemplateSTRtree.h:208
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other, ItemDistance &distance)
Definition TemplateSTRtree.h:215
std::pair< ItemType, ItemType > nearestNeighbour(ItemDistance &distance)
Definition TemplateSTRtree.h:202
TemplateSTRtreeImpl(size_t p_nodeCapacity=10)
Definition TemplateSTRtree.h:130
TemplateSTRtreeImpl(size_t p_nodeCapacity, size_t itemCapacity)
Definition TemplateSTRtree.h:141
TemplateSTRtreeImpl(const TemplateSTRtreeImpl &other)
Definition TemplateSTRtree.h:152
void insert(const BoundsType &itemEnv, const ItemType &item)
Definition TemplateSTRtree.h:190
void insert(const ItemType &item)
Definition TemplateSTRtree.h:178
void insert(ItemType &&item)
Definition TemplateSTRtree.h:173
void insert(const BoundsType &itemEnv, ItemType &&item)
Definition TemplateSTRtree.h:183
bool built() const
Definition TemplateSTRtree.h:366
const Node * getRoot()
Definition TemplateSTRtree.h:371
void iterate(F &&func)
Definition TemplateSTRtree.h:330
Items items()
Definition TemplateSTRtree.h:320
Basic namespace for all GEOS functionalities.
Definition geos.h:39