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 
32 namespace geos {
33 namespace index {
34 namespace strtree {
35 
56 template<typename ItemType, typename BoundsTraits>
58 public:
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 
159  TemplateSTRtreeImpl& operator=(TemplateSTRtreeImpl other)
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>
215  std::pair<ItemType, ItemType> nearestNeighbour(TemplateSTRtreeImpl<ItemType, BoundsTraits> & other,
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 
412 protected:
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 
684 struct 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 
735 struct 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 
766 template<typename ItemType, typename BoundsTraits = EnvelopeTraits>
767 class TemplateSTRtree : public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
768 public:
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*.
775 template<typename ItemType>
776 class TemplateSTRtree<ItemType*, EnvelopeTraits> : public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>, public SpatialIndex {
777 public:
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 }
bool built() const
Definition: TemplateSTRtree.h:366
void insert(const BoundsType &itemEnv, const ItemType &item)
Definition: TemplateSTRtree.h:190
TemplateSTRtreeImpl(size_t p_nodeCapacity=10)
Definition: TemplateSTRtree.h:130
const Node * getRoot()
Definition: TemplateSTRtree.h:371
void insert(const BoundsType &itemEnv, ItemType &&item)
Definition: TemplateSTRtree.h:183
void iterate(F &&func)
Definition: TemplateSTRtree.h:330
void insert(const ItemType &item)
Definition: TemplateSTRtree.h:178
void build()
Definition: TemplateSTRtree.h:379
TemplateSTRtreeImpl(const TemplateSTRtreeImpl &other)
Definition: TemplateSTRtree.h:152
Items items()
Definition: TemplateSTRtree.h:320
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other)
Definition: TemplateSTRtree.h:227
void insert(ItemType &&item)
Definition: TemplateSTRtree.h:173
A function method which computes the distance between two ItemBoundables in an STRtree. Used for Nearest Neighbour searches.
Definition: ItemDistance.h:33
std::pair< ItemType, ItemType > nearestNeighbour(ItemDistance &distance)
Definition: TemplateSTRtree.h:202
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other, ItemDistance &distance)
Definition: TemplateSTRtree.h:215
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25
TemplateSTRtreeImpl(size_t p_nodeCapacity, size_t itemCapacity)
Definition: TemplateSTRtree.h:141
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For one- or two-dimensiona...
Definition: TemplateSTRtree.h:57
std::pair< ItemType, ItemType > nearestNeighbour()
Definition: TemplateSTRtree.h:208