GEOS 3.15.0dev
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 validateConstruction();
136 }
137
143 TemplateSTRtreeImpl(size_t p_nodeCapacity, size_t itemCapacity) :
144 root(nullptr),
145 nodeCapacity(p_nodeCapacity),
146 numItems(0)
147 {
148 auto finalSize = treeSize(itemCapacity);
149 nodes.reserve(finalSize);
150 validateConstruction();
151 }
152
157 root(other.root),
158 nodeCapacity(other.nodeCapacity),
159 numItems(other.numItems) {
160 nodes = other.nodes;
161 }
162
164 {
165 root = other.root;
166 nodeCapacity = other.nodeCapacity;
167 numItems = other.numItems;
168 nodes = other.nodes;
169 return *this;
170 }
171
175
177 void insert(ItemType&& item) {
178 insert(BoundsTraits::fromItem(item), std::forward<ItemType>(item));
179 }
180
182 void insert(const ItemType& item) {
183 insert(BoundsTraits::fromItem(item), item);
184 }
185
187 void insert(const BoundsType& itemEnv, ItemType&& item) {
188 if (!BoundsTraits::isNull(itemEnv)) {
189 createLeafNode(std::forward<ItemType>(item), itemEnv);
190 }
191 }
192
194 void insert(const BoundsType& itemEnv, const ItemType& item) {
195 if (!BoundsTraits::isNull(itemEnv)) {
196 createLeafNode(item, itemEnv);
197 }
198 }
199
203
205 template<typename ItemDistance>
206 std::pair<ItemType, ItemType> nearestNeighbour(ItemDistance& distance) {
207 return nearestNeighbour(*this, distance);
208 }
209
211 template<typename ItemDistance>
212 std::pair<ItemType, ItemType> nearestNeighbour() {
213 return nearestNeighbour(*this);
214 }
215
217 template<typename ItemDistance>
219 ItemDistance & distance) {
220 if (!getRoot() || !other.getRoot()) {
221 return { nullptr, nullptr };
222 }
223
224 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(distance);
225 return td.nearestNeighbour(*root, *other.root);
226 }
227
229 template<typename ItemDistance>
230 std::pair<ItemType, ItemType> nearestNeighbour(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other) {
231 ItemDistance id;
232 return nearestNeighbour(other, id);
233 }
234
235 template<typename ItemDistance>
236 ItemType nearestNeighbour(const BoundsType& env, const ItemType& item, ItemDistance& itemDist) {
237 build();
238
239 if (getRoot() == nullptr) {
240 return nullptr;
241 }
242
243 TemplateSTRNode<ItemType, BoundsTraits> bnd(item, env);
244 TemplateSTRNodePair<ItemType, BoundsTraits, ItemDistance> pair(*getRoot(), bnd, itemDist);
245
246 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
247 return td.nearestNeighbour(pair).first;
248 }
249
250 template<typename ItemDistance>
251 ItemType nearestNeighbour(const BoundsType& env, const ItemType& item) {
252 ItemDistance id;
253 return nearestNeighbour(env, item, id);
254 }
255
256 template<typename ItemDistance>
257 bool isWithinDistance(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other, double maxDistance) {
258 ItemDistance itemDist;
259
260 if (!getRoot() || !other.getRoot()) {
261 return false;
262 }
263
264 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
265 return td.isWithinDistance(*root, *other.root, maxDistance);
266 }
267
271
272 // Query the tree using the specified visitor. The visitor must be callable
273 // either with a single argument of `const ItemType&` or with the
274 // arguments `(const BoundsType&, const ItemType&).
275 // The visitor need not return a value, but if it does return a value,
276 // false values will be taken as a signal to stop the query.
277 template<typename Visitor>
278 void query(const BoundsType& queryEnv, Visitor &&visitor) {
279 if (!built()) {
280 build();
281 }
282
283 if (root && root->boundsIntersect(queryEnv)) {
284 if (root->isLeaf()) {
285 visitLeaf(visitor, *root);
286 } else {
287 query(queryEnv, *root, visitor);
288 }
289 }
290 }
291
292 // Query the tree for all pairs whose bounds intersect. The visitor must
293 // be callable with arguments (const ItemType&, const ItemType&).
294 // The visitor will be called for each pair once, with first-inserted
295 // item used for the first argument.
296 // The visitor need not return a value, but if it does return a value,
297 // false values will be taken as a signal to stop the query.
298 template<typename Visitor>
299 void queryPairs(Visitor&& visitor) {
300 if (!built()) {
301 build();
302 }
303
304 if (numItems < 2) {
305 return;
306 }
307
308 for (std::size_t i = 0; i < numItems; i++) {
309 queryPairs(nodes[i], *root, visitor);
310 }
311 }
312
313 // Query the tree and collect items in the provided vector.
314 void query(const BoundsType& queryEnv, std::vector<ItemType>& results) {
315 query(queryEnv, [&results](const ItemType& x) {
316 results.push_back(x);
317 });
318 }
319
323 Items items() {
324 build();
325 return Items(*this);
326 }
327
332 template<typename F>
333 void iterate(F&& func) {
334 auto n = built() ? numItems : nodes.size();
335 for (size_t i = 0; i < n; i++) {
336 if (!nodes[i].isDeleted()) {
337 func(nodes[i].getItem());
338 }
339 }
340 }
341
345
346 bool remove(const BoundsType& itemEnv, const ItemType& item) {
347 build();
348
349 if (root == nullptr) {
350 return false;
351 }
352
353 if (root->isLeaf()) {
354 if (!root->isDeleted() && root->getItem() == item) {
355 root->removeItem();
356 return true;
357 }
358 return false;
359 }
360
361 return remove(itemEnv, *root, item);
362 }
363
367
369 bool built() const {
370 return root != nullptr;
371 }
372
374 const Node* getRoot() {
375 build();
376 return root;
377 }
378
380
382 void build() {
383 std::lock_guard<std::mutex> lock(lock_);
384
385 if (built()) {
386 return;
387 }
388
389 if (nodes.empty()) {
390 return;
391 }
392
393 numItems = nodes.size();
394
395 // compute final size of tree and set it aside in a single
396 // block of memory
397 auto finalSize = treeSize(numItems);
398 nodes.reserve(finalSize);
399
400 // begin and end define a range of nodes needing parents
401 auto begin = nodes.begin();
402 auto number = static_cast<size_t>(std::distance(begin, nodes.end()));
403
404 while (number > 1) {
405 createParentNodes(begin, number);
406 std::advance(begin, static_cast<long>(number)); // parents just added become children in the next round
407 number = static_cast<size_t>(std::distance(begin, nodes.end()));
408 }
409
410 assert(finalSize == nodes.size());
411
412 root = &nodes.back();
413 }
414
415protected:
416 std::mutex lock_;
417 NodeList nodes; //**< a list of all leaf and branch nodes in the tree. */
418 Node* root; //**< a pointer to the root node, if the tree has been built. */
419 size_t nodeCapacity; //*< maximum number of children of each node */
420 size_t numItems; //*< total number of items in the tree, if it has been built. */
421
422 // Prevent instantiation of base class.
423 // ~TemplateSTRtreeImpl() = default;
424
425 void createLeafNode(ItemType&& item, const BoundsType& env) {
426 nodes.emplace_back(std::forward<ItemType>(item), env);
427 }
428
429 void createLeafNode(const ItemType& item, const BoundsType& env) {
430 nodes.emplace_back(item, env);
431 }
432
433 void createBranchNode(const Node *begin, const Node *end) {
434 assert(nodes.size() < nodes.capacity());
435 nodes.emplace_back(begin, end);
436 }
437
438 // calculate what the tree size will be when it is build. This is simply
439 // a version of createParentNodes that doesn't actually create anything.
440 size_t treeSize(size_t numLeafNodes) {
441 size_t nodesInTree = numLeafNodes;
442
443 size_t nodesWithoutParents = numLeafNodes;
444 while (nodesWithoutParents > 1) {
445 auto numSlices = sliceCount(nodesWithoutParents);
446 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
447
448 size_t parentNodesAdded = 0;
449 for (size_t j = 0; j < numSlices; j++) {
450 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
451 nodesWithoutParents -= nodesInSlice;
452
453 parentNodesAdded += static_cast<size_t>(std::ceil(
454 static_cast<double>(nodesInSlice) / static_cast<double>(nodeCapacity)));
455 }
456
457 nodesInTree += parentNodesAdded;
458 nodesWithoutParents = parentNodesAdded;
459 }
460
461 return nodesInTree;
462 }
463
464 void createParentNodes(const NodeListIterator& begin, size_t number) {
465 // Arrange child nodes in two dimensions.
466 // First, divide them into vertical slices of a given size (left-to-right)
467 // Then create nodes within those slices (bottom-to-top)
468 auto numSlices = sliceCount(number);
469 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
470
471 // We could sort all of the nodes here, but we don't actually need them to be
472 // completely sorted. They need to be sorted enough for each node to end up
473 // in the right vertical slice, but their relative position within the slice
474 // doesn't matter. So we do a partial sort for each slice below instead.
475 auto end = begin + static_cast<long>(number);
476 sortNodesX(begin, end);
477
478 auto startOfSlice = begin;
479 for (decltype(numSlices) j = 0; j < numSlices; j++) {
480 // end iterator is being invalidated at each iteration
481 end = begin + static_cast<long>(number);
482 auto nodesRemaining = static_cast<size_t>(std::distance(startOfSlice, end));
483 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
484 auto endOfSlice = std::next(startOfSlice, static_cast<long>(nodesInSlice));
485
486 // Make sure that every node that should be in this slice ends up somewhere
487 // between startOfSlice and endOfSlice. We don't require any ordering among
488 // nodes between startOfSlice and endOfSlice.
489 //partialSortNodes(startOfSlice, endOfSlice, end);
490
491 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
492
493 startOfSlice = endOfSlice;
494 }
495 }
496
497 void addParentNodesFromVerticalSlice(const NodeListIterator& begin, const NodeListIterator& end) {
498 if (BoundsTraits::TwoDimensional::value) {
499 sortNodesY(begin, end);
500 }
501
502 // Arrange the nodes vertically and full up parent nodes sequentially until they're full.
503 // A possible improvement would be to rework this such so that if we have 81 nodes we
504 // put 9 into each parent instead of 10 or 1.
505 auto firstChild = begin;
506 while (firstChild != end) {
507 auto childrenRemaining = static_cast<size_t>(std::distance(firstChild, end));
508 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
509 auto lastChild = std::next(firstChild, static_cast<long>(childrenForNode));
510
511 //partialSortNodes(firstChild, lastChild, end);
512
513 // Ideally we would be able to store firstChild and lastChild instead of
514 // having to convert them to pointers, but I wasn't sure how to access
515 // the NodeListIterator type from within Node without creating some weird
516 // circular dependency.
517 const Node *ptr_first = &*firstChild;
518 const Node *ptr_end = ptr_first + childrenForNode;
519
520 createBranchNode(ptr_first, ptr_end);
521 firstChild = lastChild;
522 }
523 }
524
525 void sortNodesX(const NodeListIterator& begin, const NodeListIterator& end) {
526 std::sort(begin, end, [](const Node &a, const Node &b) {
527 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
528 });
529 }
530
531 void sortNodesY(const NodeListIterator& begin, const NodeListIterator& end) {
532 std::sort(begin, end, [](const Node &a, const Node &b) {
533 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
534 });
535 }
536
537 // Helper function to visit an item using a visitor that has no return value.
538 // In this case, we will always return true, indicating that querying should
539 // continue.
540 template<typename Visitor,
541 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
542 bool visitLeaf(Visitor&& visitor, const Node& node)
543 {
544 visitor(node.getItem());
545 return true;
546 }
547
548 template<typename Visitor,
549 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
550 bool visitLeaves(Visitor&& visitor, const Node& node1, const Node& node2)
551 {
552 visitor(node1.getItem(), node2.getItem());
553 return true;
554 }
555
556 // MSVC 2015 does not implement C++11 expression SFINAE and considers this a
557 // redefinition of a previous method
558#if !defined(_MSC_VER) || _MSC_VER >= 1910
559 template<typename Visitor,
560 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
561 bool visitLeaf(Visitor&& visitor, const Node& node)
562 {
563 visitor(node.getBounds(), node.getItem());
564 return true;
565 }
566#endif
567
568 // If the visitor function does return a value, we will use this to indicate
569 // that querying should continue.
570 template<typename Visitor,
571 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr>
572 bool visitLeaf(Visitor&& visitor, const Node& node)
573 {
574 return visitor(node.getItem());
575 }
576
577 template<typename Visitor,
578 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr >
579 bool visitLeaves(Visitor&& visitor, const Node& node1, const Node& node2)
580 {
581 return visitor(node1.getItem(), node2.getItem());
582 }
583
584 // MSVC 2015 does not implement C++11 expression SFINAE and considers this a
585 // redefinition of a previous method
586#if !defined(_MSC_VER) || _MSC_VER >= 1910
587 template<typename Visitor,
588 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type = nullptr>
589 bool visitLeaf(Visitor&& visitor, const Node& node)
590 {
591 return visitor(node.getBounds(), node.getItem());
592 }
593#endif
594
595 template<typename Visitor>
596 bool query(const BoundsType& queryEnv,
597 const Node& node,
598 Visitor&& visitor) {
599
600 assert(!node.isLeaf());
601
602 for (auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
603 if (child->boundsIntersect(queryEnv)) {
604 if (child->isLeaf()) {
605 if (!child->isDeleted()) {
606 if (!visitLeaf(visitor, *child)) {
607 return false; // abort query
608 }
609 }
610 } else {
611 if (!query(queryEnv, *child, visitor)) {
612 return false; // abort query
613 }
614 }
615 }
616 }
617 return true; // continue searching
618 }
619
620 template<typename Visitor>
621 bool queryPairs(const Node& queryNode,
622 const Node& searchNode,
623 Visitor&& visitor) {
624
625 assert(!searchNode.isLeaf());
626
627 for (auto* child = searchNode.beginChildren(); child < searchNode.endChildren(); ++child) {
628 if (child->isLeaf()) {
629 // Only visit leaf nodes if they have a higher address than the query node,
630 // to avoid processing the same pairs twice.
631 if (child > &queryNode && !child->isDeleted() && child->boundsIntersect(queryNode.getBounds())) {
632 if (!visitLeaves(visitor, queryNode, *child)) {
633 return false; // abort query
634 }
635 }
636 } else {
637 if (child->boundsIntersect(queryNode.getBounds())) {
638 if (!queryPairs(queryNode, *child, visitor)) {
639 return false; // abort query
640 }
641 }
642 }
643 }
644
645 return true; // continue searching
646 }
647
648 bool remove(const BoundsType& queryEnv,
649 const Node& node,
650 const ItemType& item) {
651
652 assert(!node.isLeaf());
653
654 for (auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
655 if (child->boundsIntersect(queryEnv)) {
656 if (child->isLeaf()) {
657 if (!child->isDeleted() && child->getItem() == item) {
658 // const cast is ugly, but alternative seems to be to remove all
659 // const qualifiers in Node and open up mutability everywhere?
660 auto mutableChild = const_cast<Node*>(child);
661 mutableChild->removeItem();
662 return true;
663 }
664 } else {
665 bool removed = remove(queryEnv, *child, item);
666 if (removed) {
667 return true;
668 }
669 }
670 }
671 }
672
673 return false;
674 }
675
676 size_t sliceCount(size_t numNodes) const {
677 double minLeafCount = std::ceil(static_cast<double>(numNodes) / static_cast<double>(nodeCapacity));
678
679 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
680 }
681
682 static size_t sliceCapacity(size_t numNodes, size_t numSlices) {
683 return static_cast<size_t>(std::ceil(static_cast<double>(numNodes) / static_cast<double>(numSlices)));
684 }
685
686 void validateConstruction() const {
687 if (nodeCapacity < 2) {
688 throw util::IllegalArgumentException("STRTree node capacity must be >= 2");
689 }
690 }
691};
692
693struct EnvelopeTraits {
694 using BoundsType = geom::Envelope;
695 using TwoDimensional = std::true_type;
696
697 static bool intersects(const BoundsType& a, const BoundsType& b) {
698 return a.intersects(b);
699 }
700
701 static double size(const BoundsType& a) {
702 return a.getArea();
703 }
704
705 static double distance(const BoundsType& a, const BoundsType& b) {
706 return a.distance(b);
707 }
708
709 static double maxDistance(const BoundsType& a, const BoundsType& b) {
710 return a.maxDistance(b);
711 }
712
713 static BoundsType empty() {
714 return {};
715 }
716
717 template<typename ItemType>
718 static const BoundsType& fromItem(const ItemType& i) {
719 return *(i->getEnvelopeInternal());
720 }
721
722 template<typename ItemType>
723 static const BoundsType& fromItem(ItemType&& i) {
724 return *(i->getEnvelopeInternal());
725 }
726
727 static double getX(const BoundsType& a) {
728 return a.getMinX() + a.getMaxX();
729 }
730
731 static double getY(const BoundsType& a) {
732 return a.getMinY() + a.getMaxY();
733 }
734
735 static void expandToInclude(BoundsType& a, const BoundsType& b) {
736 a.expandToInclude(b);
737 }
738
739 static bool isNull(const BoundsType& a) {
740 return a.isNull();
741 }
742};
743
744struct IntervalTraits {
745 using BoundsType = Interval;
746 using TwoDimensional = std::false_type;
747
748 static bool intersects(const BoundsType& a, const BoundsType& b) {
749 return a.intersects(&b);
750 }
751
752 static double size(const BoundsType& a) {
753 return a.getWidth();
754 }
755
756 static double getX(const BoundsType& a) {
757 return a.getMin() + a.getMax();
758 }
759
760 static double getY(const BoundsType& a) {
761 return a.getMin() + a.getMax();
762 }
763
764 static void expandToInclude(BoundsType& a, const BoundsType& b) {
765 a.expandToInclude(&b);
766 }
767
768 static bool isNull(const BoundsType& a) {
769 (void) a;
770 return false;
771 }
772};
773
774
775template<typename ItemType, typename BoundsTraits = EnvelopeTraits>
776class TemplateSTRtree : public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
777public:
778 using TemplateSTRtreeImpl<ItemType, BoundsTraits>::TemplateSTRtreeImpl;
779};
780
781// When ItemType is a pointer and our bounds are geom::Envelope, adopt
782// the SpatialIndex interface which requires queries via an envelope
783// and items to be representable as void*.
784template<typename ItemType>
785class TemplateSTRtree<ItemType*, EnvelopeTraits> : public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>, public SpatialIndex {
786public:
787 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::TemplateSTRtreeImpl;
788 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::insert;
789 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::query;
790 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::remove;
791
792 // The SpatialIndex methods only work when we are storing a pointer type.
793 void query(const geom::Envelope* queryEnv, std::vector<void*>& results) override {
794 query(*queryEnv, [&results](const ItemType* x) {
795 results.push_back(const_cast<void*>(static_cast<const void*>(x)));
796 });
797 }
798
799 void query(const geom::Envelope* queryEnv, ItemVisitor& visitor) override {
800 query(*queryEnv, [&visitor](const ItemType* x) {
801 visitor.visitItem(const_cast<void*>(static_cast<const void*>(x)));
802 });
803 }
804
805 bool remove(const geom::Envelope* itemEnv, void* item) override {
806 return remove(*itemEnv, static_cast<ItemType*>(item));
807 }
808
809 void insert(const geom::Envelope* itemEnv, void* item) override {
810 insert(*itemEnv, std::move(static_cast<ItemType*>(item)));
811 }
812};
813
814
815}
816}
817}
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:382
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other)
Definition TemplateSTRtree.h:230
std::pair< ItemType, ItemType > nearestNeighbour()
Definition TemplateSTRtree.h:212
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other, ItemDistance &distance)
Definition TemplateSTRtree.h:218
std::pair< ItemType, ItemType > nearestNeighbour(ItemDistance &distance)
Definition TemplateSTRtree.h:206
TemplateSTRtreeImpl(size_t p_nodeCapacity=10)
Definition TemplateSTRtree.h:130
TemplateSTRtreeImpl(size_t p_nodeCapacity, size_t itemCapacity)
Definition TemplateSTRtree.h:143
TemplateSTRtreeImpl(const TemplateSTRtreeImpl &other)
Definition TemplateSTRtree.h:156
void insert(const BoundsType &itemEnv, const ItemType &item)
Definition TemplateSTRtree.h:194
void insert(const ItemType &item)
Definition TemplateSTRtree.h:182
void insert(ItemType &&item)
Definition TemplateSTRtree.h:177
void insert(const BoundsType &itemEnv, ItemType &&item)
Definition TemplateSTRtree.h:187
bool built() const
Definition TemplateSTRtree.h:369
const Node * getRoot()
Definition TemplateSTRtree.h:374
void iterate(F &&func)
Definition TemplateSTRtree.h:333
Items items()
Definition TemplateSTRtree.h:323
Basic namespace for all GEOS functionalities.
Definition geos.h:38