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>
21 #include <geos/util.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>
56 template<
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 func(nodes[i].getItem());
308 bool remove(
const BoundsType& itemEnv,
const ItemType& item) {
309 if (root ==
nullptr) {
313 if (root->isLeaf()) {
314 if (!root->isDeleted() && root->getItem() == item) {
321 return remove(itemEnv, *root, item);
330 return root !=
nullptr;
343 std::lock_guard<std::mutex> lock(lock_);
353 numItems = nodes.size();
357 auto finalSize = treeSize(numItems);
358 nodes.reserve(finalSize);
361 auto begin = nodes.begin();
362 auto end = nodes.end();
364 while (std::distance(begin, end) > 1) {
365 createParentNodes(begin, end);
370 assert(finalSize == nodes.size());
372 root = &nodes.back();
385 void createLeafNode(ItemType&& item,
const BoundsType& env) {
386 nodes.emplace_back(std::forward<ItemType>(item), env);
389 void createLeafNode(
const ItemType& item,
const BoundsType& env) {
390 nodes.emplace_back(item, env);
393 void createBranchNode(
const Node *begin,
const Node *end) {
394 assert(nodes.size() < nodes.capacity());
395 nodes.emplace_back(begin, end);
400 size_t treeSize(
size_t numLeafNodes) {
401 size_t nodesInTree = numLeafNodes;
403 size_t nodesWithoutParents = numLeafNodes;
404 while (nodesWithoutParents > 1) {
405 auto numSlices = sliceCount(nodesWithoutParents);
406 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
408 size_t parentNodesAdded = 0;
409 for (
size_t j = 0; j < numSlices; j++) {
410 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
411 nodesWithoutParents -= nodesInSlice;
413 parentNodesAdded +=
static_cast<size_t>(std::ceil(
414 static_cast<double>(nodesInSlice) /
static_cast<double>(nodeCapacity)));
417 nodesInTree += parentNodesAdded;
418 nodesWithoutParents = parentNodesAdded;
424 void createParentNodes(
const NodeListIterator& begin,
const NodeListIterator& end) {
428 auto numChildren =
static_cast<std::size_t
>(std::distance(begin, end));
429 auto numSlices = sliceCount(numChildren);
430 std::size_t nodesPerSlice = sliceCapacity(numChildren, numSlices);
436 sortNodesX(begin, end);
438 auto startOfSlice = begin;
439 for (decltype(numSlices) j = 0; j < numSlices; j++) {
440 auto nodesRemaining =
static_cast<size_t>(std::distance(startOfSlice, end));
441 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
442 auto endOfSlice = std::next(startOfSlice,
static_cast<long>(nodesInSlice));
449 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
451 startOfSlice = endOfSlice;
455 void addParentNodesFromVerticalSlice(
const NodeListIterator& begin,
const NodeListIterator& end) {
456 if (BoundsTraits::TwoDimensional::value) {
457 sortNodesY(begin, end);
463 auto firstChild = begin;
464 while (firstChild != end) {
465 auto childrenRemaining =
static_cast<size_t>(std::distance(firstChild, end));
466 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
467 auto lastChild = std::next(firstChild,
static_cast<long>(childrenForNode));
475 const Node *ptr_first = &*firstChild;
476 const Node *ptr_end = ptr_first + childrenForNode;
478 createBranchNode(ptr_first, ptr_end);
479 firstChild = lastChild;
483 void sortNodesX(
const NodeListIterator& begin,
const NodeListIterator& end) {
484 std::sort(begin, end, [](
const Node &a,
const Node &b) {
485 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
489 void sortNodesY(
const NodeListIterator& begin,
const NodeListIterator& end) {
490 std::sort(begin, end, [](
const Node &a,
const Node &b) {
491 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
498 template<
typename Visitor,
499 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
500 bool visitLeaf(Visitor&& visitor,
const Node& node)
502 visitor(node.getItem());
508 #if !defined(_MSC_VER) || _MSC_VER >= 1910
509 template<
typename Visitor,
510 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
511 bool visitLeaf(Visitor&& visitor,
const Node& node)
513 visitor(node.getBounds(), node.getItem());
520 template<
typename Visitor,
521 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
522 bool visitLeaf(Visitor&& visitor,
const Node& node)
524 return visitor(node.getItem());
529 #if !defined(_MSC_VER) || _MSC_VER >= 1910
530 template<
typename Visitor,
531 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
532 bool visitLeaf(Visitor&& visitor,
const Node& node)
534 return visitor(node.getBounds(), node.getItem());
538 template<
typename Visitor>
539 void query(
const BoundsType& queryEnv,
543 assert(!node.isLeaf());
545 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
546 if (child->boundsIntersect(queryEnv)) {
547 if (child->isLeaf() && !child->isDeleted()) {
548 if (!visitLeaf(visitor, *child)) {
552 query(queryEnv, *child, visitor);
558 bool remove(
const BoundsType& queryEnv,
560 const ItemType& item) {
562 assert(!node.isLeaf());
564 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
565 if (child->boundsIntersect(queryEnv)) {
566 if (child->isLeaf()) {
567 if (!child->isDeleted() && child->getItem() == item) {
570 auto mutableChild =
const_cast<Node*
>(child);
571 mutableChild->removeItem();
575 bool removed = remove(queryEnv, *child, item);
586 size_t sliceCount(
size_t numNodes)
const {
587 double minLeafCount = std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(nodeCapacity));
589 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
592 static size_t sliceCapacity(
size_t numNodes,
size_t numSlices) {
593 return static_cast<size_t>(std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(numSlices)));
597 struct EnvelopeTraits {
598 using BoundsType = geom::Envelope;
599 using TwoDimensional = std::true_type;
601 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
602 return a.intersects(b);
605 static double size(
const BoundsType& a) {
609 static double distance(
const BoundsType& a,
const BoundsType& b) {
610 return a.distance(b);
613 static BoundsType empty() {
617 template<
typename ItemType>
618 static const BoundsType& fromItem(
const ItemType& i) {
619 return *(i->getEnvelopeInternal());
622 template<
typename ItemType>
623 static const BoundsType& fromItem(ItemType&& i) {
624 return *(i->getEnvelopeInternal());
627 static double getX(
const BoundsType& a) {
628 return a.getMinX() + a.getMaxX();
631 static double getY(
const BoundsType& a) {
632 return a.getMinY() + a.getMaxY();
635 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
636 a.expandToInclude(b);
639 static bool isNull(
const BoundsType& a) {
644 struct IntervalTraits {
645 using BoundsType = Interval;
646 using TwoDimensional = std::false_type;
648 static bool intersects(
const BoundsType& a,
const BoundsType& b) {
649 return a.intersects(&b);
652 static double size(
const BoundsType& a) {
656 static double getX(
const BoundsType& a) {
657 return a.getMin() + a.getMax();
660 static double getY(
const BoundsType& a) {
661 return a.getMin() + a.getMax();
664 static void expandToInclude(BoundsType& a,
const BoundsType& b) {
665 a.expandToInclude(&b);
668 static bool isNull(
const BoundsType& a) {
675 template<
typename ItemType,
typename BoundsTraits = EnvelopeTraits>
676 class TemplateSTRtree :
public TemplateSTRtreeImpl<ItemType, BoundsTraits> {
684 template<
typename ItemType>
685 class TemplateSTRtree<ItemType*, EnvelopeTraits> :
public TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>,
public SpatialIndex {
689 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::query;
690 using TemplateSTRtreeImpl<ItemType*, EnvelopeTraits>::remove;
693 void query(
const geom::Envelope* queryEnv, std::vector<void*>& results)
override {
694 query(*queryEnv, [&results](
const ItemType* x) {
695 results.push_back(
const_cast<void*
>(
static_cast<const void*
>(x)));
699 void query(
const geom::Envelope* queryEnv, ItemVisitor& visitor)
override {
700 query(*queryEnv, [&visitor](
const ItemType* x) {
701 visitor.visitItem(
const_cast<void*
>(
static_cast<const void*
>(x)));
705 bool remove(
const geom::Envelope* itemEnv,
void* item)
override {
706 return remove(*itemEnv,
static_cast<ItemType*
>(item));
709 void insert(
const geom::Envelope* itemEnv,
void* item)
override {
710 insert(*itemEnv, std::move(
static_cast<ItemType*
>(item)));
A function method which computes the distance between two ItemBoundables in an STRtree....
Definition: ItemDistance.h:34
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:342
std::pair< ItemType, ItemType > nearestNeighbour(TemplateSTRtreeImpl< ItemType, BoundsTraits > &other)
Definition: TemplateSTRtree.h:227
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
std::pair< ItemType, ItemType > nearestNeighbour()
Definition: TemplateSTRtree.h:208
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
const Node * getRoot()
Definition: TemplateSTRtree.h:334
bool built() const
Definition: TemplateSTRtree.h:329
void iterate(F &&func)
Definition: TemplateSTRtree.h:297
Items items()
Definition: TemplateSTRtree.h:287
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26