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>
262 template<
typename Visitor>
263 void query(
const BoundsType& queryEnv, Visitor &&visitor) {
268 if (root && root->boundsIntersect(queryEnv)) {
269 if (root->isLeaf()) {
270 visitLeaf(visitor, *root);
272 query(queryEnv, *root, visitor);
278 void query(
const BoundsType& queryEnv, std::vector<ItemType>& results) {
279 query(queryEnv, [&results](
const ItemType& x) {
280 results.push_back(x);
298 auto n =
built() ? numItems : nodes.size();
299 for (
size_t i = 0; i < n; i++) {
300 if (!nodes[i].isDeleted()) {
301 func(nodes[i].getItem());
310 bool remove(
const BoundsType& itemEnv,
const ItemType& item) {
313 if (root ==
nullptr) {
317 if (root->isLeaf()) {
318 if (!root->isDeleted() && root->getItem() == item) {
325 return remove(itemEnv, *root, item);
334 return root !=
nullptr;
347 std::lock_guard<std::mutex> lock(lock_);
357 numItems = nodes.size();
361 auto finalSize = treeSize(numItems);
362 nodes.reserve(finalSize);
365 auto begin = nodes.begin();
366 auto number =
static_cast<size_t>(std::distance(begin, nodes.end()));
369 createParentNodes(begin, number);
370 std::advance(begin,
static_cast<long>(number));
371 number =
static_cast<size_t>(std::distance(begin, nodes.end()));
374 assert(finalSize == nodes.size());
376 root = &nodes.back();
389 void createLeafNode(ItemType&& item,
const BoundsType& env) {
390 nodes.emplace_back(std::forward<ItemType>(item), env);
393 void createLeafNode(
const ItemType& item,
const BoundsType& env) {
394 nodes.emplace_back(item, env);
397 void createBranchNode(
const Node *begin,
const Node *end) {
398 assert(nodes.size() < nodes.capacity());
399 nodes.emplace_back(begin, end);
404 size_t treeSize(
size_t numLeafNodes) {
405 size_t nodesInTree = numLeafNodes;
407 size_t nodesWithoutParents = numLeafNodes;
408 while (nodesWithoutParents > 1) {
409 auto numSlices = sliceCount(nodesWithoutParents);
410 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
412 size_t parentNodesAdded = 0;
413 for (
size_t j = 0; j < numSlices; j++) {
414 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
415 nodesWithoutParents -= nodesInSlice;
417 parentNodesAdded +=
static_cast<size_t>(std::ceil(
418 static_cast<double>(nodesInSlice) /
static_cast<double>(nodeCapacity)));
421 nodesInTree += parentNodesAdded;
422 nodesWithoutParents = parentNodesAdded;
428 void createParentNodes(
const NodeListIterator& begin,
size_t number) {
432 auto numSlices = sliceCount(number);
433 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
439 auto end = begin +
static_cast<long>(number);
440 sortNodesX(begin, end);
442 auto startOfSlice = begin;
443 for (
decltype(numSlices) j = 0; j < numSlices; j++) {
445 end = begin +
static_cast<long>(number);
446 auto nodesRemaining =
static_cast<size_t>(std::distance(startOfSlice, end));
447 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
448 auto endOfSlice = std::next(startOfSlice,
static_cast<long>(nodesInSlice));
455 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
457 startOfSlice = endOfSlice;
461 void addParentNodesFromVerticalSlice(
const NodeListIterator& begin,
const NodeListIterator& end) {
462 if (BoundsTraits::TwoDimensional::value) {
463 sortNodesY(begin, end);
469 auto firstChild = begin;
470 while (firstChild != end) {
471 auto childrenRemaining =
static_cast<size_t>(std::distance(firstChild, end));
472 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
473 auto lastChild = std::next(firstChild,
static_cast<long>(childrenForNode));
481 const Node *ptr_first = &*firstChild;
482 const Node *ptr_end = ptr_first + childrenForNode;
484 createBranchNode(ptr_first, ptr_end);
485 firstChild = lastChild;
489 void sortNodesX(
const NodeListIterator& begin,
const NodeListIterator& end) {
490 std::sort(begin, end, [](
const Node &a,
const Node &b) {
491 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
495 void sortNodesY(
const NodeListIterator& begin,
const NodeListIterator& end) {
496 std::sort(begin, end, [](
const Node &a,
const Node &b) {
497 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
504 template<
typename Visitor,
505 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
506 bool visitLeaf(Visitor&& visitor,
const Node& node)
508 visitor(node.getItem());
514#if !defined(_MSC_VER) || _MSC_VER >= 1910
515 template<
typename Visitor,
516 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
517 bool visitLeaf(Visitor&& visitor,
const Node& node)
519 visitor(node.getBounds(), node.getItem());
526 template<
typename Visitor,
527 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
528 bool visitLeaf(Visitor&& visitor,
const Node& node)
530 return visitor(node.getItem());
535#if !defined(_MSC_VER) || _MSC_VER >= 1910
536 template<
typename Visitor,
537 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
538 bool visitLeaf(Visitor&& visitor,
const Node& node)
540 return visitor(node.getBounds(), node.getItem());
544 template<
typename Visitor>
545 bool query(
const BoundsType& queryEnv,
549 assert(!node.isLeaf());
551 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
552 if (child->boundsIntersect(queryEnv)) {
553 if (child->isLeaf()) {
554 if (!child->isDeleted()) {
555 if (!visitLeaf(visitor, *child)) {
560 if (!query(queryEnv, *child, visitor)) {
569 bool remove(
const BoundsType& queryEnv,
571 const ItemType& item) {
573 assert(!node.isLeaf());
575 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
576 if (child->boundsIntersect(queryEnv)) {
577 if (child->isLeaf()) {
578 if (!child->isDeleted() && child->getItem() == item) {
581 auto mutableChild =
const_cast<Node*
>(child);
582 mutableChild->removeItem();
586 bool removed = remove(queryEnv, *child, item);
597 size_t sliceCount(
size_t numNodes)
const {
598 double minLeafCount = std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(nodeCapacity));
600 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
603 static size_t sliceCapacity(
size_t numNodes,
size_t numSlices) {
604 return static_cast<size_t>(std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(numSlices)));
608struct EnvelopeTraits {
609 using BoundsType = geom::Envelope;
610 using TwoDimensional = std::true_type;
612 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
613 return a.intersects(b);
616 static double size(
const BoundsType& a) {
620 static double distance(
const BoundsType& a,
const BoundsType& b) {
621 return a.distance(b);
624 static BoundsType empty() {
628 template<
typename ItemType>
629 static const BoundsType& fromItem(
const ItemType& i) {
630 return *(i->getEnvelopeInternal());
633 template<
typename ItemType>
634 static const BoundsType& fromItem(ItemType&& i) {
635 return *(i->getEnvelopeInternal());
638 static double getX(
const BoundsType& a) {
639 return a.getMinX() + a.getMaxX();
642 static double getY(
const BoundsType& a) {
643 return a.getMinY() + a.getMaxY();
646 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
647 a.expandToInclude(b);
650 static bool isNull(
const BoundsType& a) {
655struct IntervalTraits {
656 using BoundsType = Interval;
657 using TwoDimensional = std::false_type;
659 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
660 return a.intersects(&b);
663 static double size(
const BoundsType& a) {
667 static double getX(
const BoundsType& a) {
668 return a.getMin() + a.getMax();
671 static double getY(
const BoundsType& a) {
672 return a.getMin() + a.getMax();
675 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
676 a.expandToInclude(&b);
679 static bool isNull(
const BoundsType& a) {
686template<
typename ItemType,
typename BoundsTraits = EnvelopeTraits>
687class TemplateSTRtree :
public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
695template<
typename ItemType>
696class TemplateSTRtree<ItemType*, EnvelopeTraits> :
public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>,
public SpatialIndex {
698 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::TemplateSTRtreeImpl;
699 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::insert;
700 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::query;
701 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::remove;
704 void query(
const geom::Envelope* queryEnv, std::vector<void*>& results)
override {
705 query(*queryEnv, [&results](
const ItemType* x) {
706 results.push_back(
const_cast<void*
>(
static_cast<const void*
>(x)));
710 void query(
const geom::Envelope* queryEnv, ItemVisitor& visitor)
override {
711 query(*queryEnv, [&visitor](
const ItemType* x) {
712 visitor.visitItem(
const_cast<void*
>(
static_cast<const void*
>(x)));
716 bool remove(
const geom::Envelope* itemEnv,
void* item)
override {
717 return remove(*itemEnv,
static_cast<ItemType*
>(item));
720 void insert(
const geom::Envelope* itemEnv,
void* item)
override {
721 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:346
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:333
const Node * getRoot()
Definition TemplateSTRtree.h:338
void iterate(F &&func)
Definition TemplateSTRtree.h:297
Items items()
Definition TemplateSTRtree.h:287
Basic namespace for all GEOS functionalities.
Definition geos.h:39