17#include <geos/geom/Geometry.h>
18#include <geos/index/SpatialIndex.h>
19#include <geos/index/chain/MonotoneChain.h>
20#include <geos/index/ItemVisitor.h>
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>
56template<
typename ItemType,
typename BoundsTraits>
59 using Node = TemplateSTRNode<ItemType, BoundsTraits>;
60 using NodeList = std::vector<Node>;
61 using NodeListIterator =
typename NodeList::iterator;
62 using BoundsType =
typename BoundsTraits::BoundsType;
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&;
72 Iterator(
typename NodeList::const_iterator&& iter,
73 typename NodeList::const_iterator&& end) : m_iter(iter), m_end(end) {
77 const ItemType& operator*()
const {
78 return m_iter->getItem();
81 Iterator& operator++() {
87 friend bool operator==(
const Iterator& a,
const Iterator& b) {
88 return a.m_iter == b.m_iter;
91 friend bool operator!=(
const Iterator& a,
const Iterator& b) {
92 return a.m_iter != b.m_iter;
97 while(m_iter != m_end && m_iter->isDeleted()) {
102 typename NodeList::const_iterator m_iter;
103 typename NodeList::const_iterator m_end;
111 return Iterator(m_tree.nodes.cbegin(),
112 std::next(m_tree.nodes.cbegin(),
static_cast<long>(m_tree.numItems)));
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)));
132 nodeCapacity(p_nodeCapacity),
143 nodeCapacity(p_nodeCapacity),
145 auto finalSize = treeSize(itemCapacity);
146 nodes.reserve(finalSize);
154 nodeCapacity(other.nodeCapacity),
155 numItems(other.numItems) {
162 nodeCapacity = other.nodeCapacity;
163 numItems = other.numItems;
174 insert(BoundsTraits::fromItem(item), std::forward<ItemType>(item));
179 insert(BoundsTraits::fromItem(item), item);
183 void insert(
const BoundsType& itemEnv, ItemType&& item) {
184 if (!BoundsTraits::isNull(itemEnv)) {
185 createLeafNode(std::forward<ItemType>(item), itemEnv);
190 void insert(
const BoundsType& itemEnv,
const ItemType& item) {
191 if (!BoundsTraits::isNull(itemEnv)) {
192 createLeafNode(item, itemEnv);
201 template<
typename ItemDistance>
207 template<
typename ItemDistance>
214 template<
typename ItemDistance>
218 return {
nullptr,
nullptr };
221 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(distance);
222 return td.nearestNeighbour(*root, *other.root);
226 template<
typename ItemDistance>
232 template<
typename ItemDistance>
240 TemplateSTRNode<ItemType, BoundsTraits> bnd(item, env);
241 TemplateSTRNodePair<ItemType, BoundsTraits, ItemDistance> pair(*
getRoot(), bnd, itemDist);
243 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
244 return td.nearestNeighbour(pair).first;
247 template<
typename ItemDistance>
253 template<
typename ItemDistance>
254 bool isWithinDistance(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other,
double maxDistance) {
255 ItemDistance itemDist;
257 if (!
getRoot() || !other.getRoot()) {
261 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
262 return td.isWithinDistance(*root, *other.root, maxDistance);
274 template<
typename Visitor>
275 void query(
const BoundsType& queryEnv, Visitor &&visitor) {
280 if (root && root->boundsIntersect(queryEnv)) {
281 if (root->isLeaf()) {
282 visitLeaf(visitor, *root);
284 query(queryEnv, *root, visitor);
295 template<
typename Visitor>
296 void queryPairs(Visitor&& visitor) {
305 for (std::size_t i = 0; i < numItems; i++) {
306 queryPairs(nodes[i], *root, visitor);
311 void query(
const BoundsType& queryEnv, std::vector<ItemType>& results) {
312 query(queryEnv, [&results](
const ItemType& x) {
313 results.push_back(x);
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());
343 bool remove(
const BoundsType& itemEnv,
const ItemType& item) {
346 if (root ==
nullptr) {
350 if (root->isLeaf()) {
351 if (!root->isDeleted() && root->getItem() == item) {
358 return remove(itemEnv, *root, item);
367 return root !=
nullptr;
380 std::lock_guard<std::mutex> lock(lock_);
390 numItems = nodes.size();
394 auto finalSize = treeSize(numItems);
395 nodes.reserve(finalSize);
398 auto begin = nodes.begin();
399 auto number =
static_cast<size_t>(std::distance(begin, nodes.end()));
402 createParentNodes(begin, number);
403 std::advance(begin,
static_cast<long>(number));
404 number =
static_cast<size_t>(std::distance(begin, nodes.end()));
407 assert(finalSize == nodes.size());
409 root = &nodes.back();
422 void createLeafNode(ItemType&& item,
const BoundsType& env) {
423 nodes.emplace_back(std::forward<ItemType>(item), env);
426 void createLeafNode(
const ItemType& item,
const BoundsType& env) {
427 nodes.emplace_back(item, env);
430 void createBranchNode(
const Node *begin,
const Node *end) {
431 assert(nodes.size() < nodes.capacity());
432 nodes.emplace_back(begin, end);
437 size_t treeSize(
size_t numLeafNodes) {
438 size_t nodesInTree = numLeafNodes;
440 size_t nodesWithoutParents = numLeafNodes;
441 while (nodesWithoutParents > 1) {
442 auto numSlices = sliceCount(nodesWithoutParents);
443 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
445 size_t parentNodesAdded = 0;
446 for (
size_t j = 0; j < numSlices; j++) {
447 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
448 nodesWithoutParents -= nodesInSlice;
450 parentNodesAdded +=
static_cast<size_t>(std::ceil(
451 static_cast<double>(nodesInSlice) /
static_cast<double>(nodeCapacity)));
454 nodesInTree += parentNodesAdded;
455 nodesWithoutParents = parentNodesAdded;
461 void createParentNodes(
const NodeListIterator& begin,
size_t number) {
465 auto numSlices = sliceCount(number);
466 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
472 auto end = begin +
static_cast<long>(number);
473 sortNodesX(begin, end);
475 auto startOfSlice = begin;
476 for (
decltype(numSlices) j = 0; j < numSlices; j++) {
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));
488 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
490 startOfSlice = endOfSlice;
494 void addParentNodesFromVerticalSlice(
const NodeListIterator& begin,
const NodeListIterator& end) {
495 if (BoundsTraits::TwoDimensional::value) {
496 sortNodesY(begin, end);
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));
514 const Node *ptr_first = &*firstChild;
515 const Node *ptr_end = ptr_first + childrenForNode;
517 createBranchNode(ptr_first, ptr_end);
518 firstChild = lastChild;
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());
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());
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)
541 visitor(node.getItem());
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)
549 visitor(node1.getItem(), node2.getItem());
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)
560 visitor(node.getBounds(), node.getItem());
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)
571 return visitor(node.getItem());
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)
578 return visitor(node1.getItem(), node2.getItem());
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)
588 return visitor(node.getBounds(), node.getItem());
592 template<
typename Visitor>
593 bool query(
const BoundsType& queryEnv,
597 assert(!node.isLeaf());
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)) {
608 if (!query(queryEnv, *child, visitor)) {
617 template<
typename Visitor>
618 bool queryPairs(
const Node& queryNode,
619 const Node& searchNode,
622 assert(!searchNode.isLeaf());
624 for (
auto* child = searchNode.beginChildren(); child < searchNode.endChildren(); ++child) {
625 if (child->isLeaf()) {
628 if (child > &queryNode && !child->isDeleted() && child->boundsIntersect(queryNode.getBounds())) {
629 if (!visitLeaves(visitor, queryNode, *child)) {
634 if (child->boundsIntersect(queryNode.getBounds())) {
635 if (!queryPairs(queryNode, *child, visitor)) {
645 bool remove(
const BoundsType& queryEnv,
647 const ItemType& item) {
649 assert(!node.isLeaf());
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) {
657 auto mutableChild =
const_cast<Node*
>(child);
658 mutableChild->removeItem();
662 bool removed = remove(queryEnv, *child, item);
673 size_t sliceCount(
size_t numNodes)
const {
674 double minLeafCount = std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(nodeCapacity));
676 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
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)));
684struct EnvelopeTraits {
685 using BoundsType = geom::Envelope;
686 using TwoDimensional = std::true_type;
688 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
689 return a.intersects(b);
692 static double size(
const BoundsType& a) {
696 static double distance(
const BoundsType& a,
const BoundsType& b) {
697 return a.distance(b);
700 static double maxDistance(
const BoundsType& a,
const BoundsType& b) {
701 return a.maxDistance(b);
704 static BoundsType empty() {
708 template<
typename ItemType>
709 static const BoundsType& fromItem(
const ItemType& i) {
710 return *(i->getEnvelopeInternal());
713 template<
typename ItemType>
714 static const BoundsType& fromItem(ItemType&& i) {
715 return *(i->getEnvelopeInternal());
718 static double getX(
const BoundsType& a) {
719 return a.getMinX() + a.getMaxX();
722 static double getY(
const BoundsType& a) {
723 return a.getMinY() + a.getMaxY();
726 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
727 a.expandToInclude(b);
730 static bool isNull(
const BoundsType& a) {
735struct IntervalTraits {
736 using BoundsType = Interval;
737 using TwoDimensional = std::false_type;
739 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
740 return a.intersects(&b);
743 static double size(
const BoundsType& a) {
747 static double getX(
const BoundsType& a) {
748 return a.getMin() + a.getMax();
751 static double getY(
const BoundsType& a) {
752 return a.getMin() + a.getMax();
755 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
756 a.expandToInclude(&b);
759 static bool isNull(
const BoundsType& a) {
766template<
typename ItemType,
typename BoundsTraits = EnvelopeTraits>
767class TemplateSTRtree :
public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
775template<
typename ItemType>
776class TemplateSTRtree<ItemType*, EnvelopeTraits> :
public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>,
public SpatialIndex {
778 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::TemplateSTRtreeImpl;
779 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::insert;
780 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::query;
781 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::remove;
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)));
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)));
796 bool remove(
const geom::Envelope* itemEnv,
void* item)
override {
797 return remove(*itemEnv,
static_cast<ItemType*
>(item));
800 void insert(
const geom::Envelope* itemEnv,
void* item)
override {
801 insert(*itemEnv, std::move(
static_cast<ItemType*
>(item)));
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