17 #include <geos/index/strtree/TemplateSTRNode.h> 18 #include <geos/index/strtree/TemplateSTRNodePair.h> 27 template<
typename ItemType,
typename BoundsType,
typename ItemDistance>
28 class TemplateSTRtreeDistance {
29 using Node = TemplateSTRNode<ItemType, BoundsType>;
30 using NodePair = TemplateSTRNodePair<ItemType, BoundsType, ItemDistance>;
31 using ItemPair = std::pair<ItemType, ItemType>;
33 struct PairQueueCompare {
34 bool operator()(
const NodePair& a,
const NodePair& b) {
35 return a.getDistance() > b.getDistance();
39 using PairQueue = std::priority_queue<NodePair, std::vector<NodePair>, PairQueueCompare>;
42 explicit TemplateSTRtreeDistance(ItemDistance&
id) : m_id(id) {}
44 ItemPair nearestNeighbour(
const Node& root1,
const Node& root2) {
45 NodePair initPair(root1, root2, m_id);
46 return nearestNeighbour(initPair);
49 ItemPair nearestNeighbour(NodePair& initPair) {
50 return nearestNeighbour(initPair, DoubleInfinity);
55 ItemPair nearestNeighbour(NodePair& initPair,
double maxDistance) {
56 double distanceLowerBound = maxDistance;
57 std::unique_ptr<NodePair> minPair;
62 while (!priQ.empty() && distanceLowerBound > 0) {
63 NodePair pair = priQ.top();
65 double currentDistance = pair.getDistance();
74 if (minPair && currentDistance >= distanceLowerBound) {
85 if (pair.isLeaves()) {
86 distanceLowerBound = currentDistance;
90 minPair = detail::make_unique<NodePair>(pair);
98 expandToQueue(pair, priQ, distanceLowerBound);
103 throw util::GEOSException(
"Error computing nearest neighbor");
106 return minPair->getItems();
109 void expandToQueue(
const NodePair& pair, PairQueue& priQ,
double minDistance) {
110 const Node& node1 = pair.getFirst();
111 const Node& node2 = pair.getSecond();
113 bool isComp1 = node1.isComposite();
114 bool isComp2 = node2.isComposite();
121 if (isComp1 && isComp2) {
122 if (node1.getSize() > node2.getSize()) {
123 expand(node1, node2,
false, priQ, minDistance);
126 expand(node2, node1,
true, priQ, minDistance);
129 }
else if (isComp1) {
130 expand(node1, node2,
false, priQ, minDistance);
132 }
else if (isComp2) {
133 expand(node2, node1,
true, priQ, minDistance);
137 throw util::IllegalArgumentException(
"neither boundable is composite");
141 void expand(
const Node &nodeComposite,
const Node &nodeOther,
bool isFlipped, PairQueue& priQ,
142 double minDistance) {
143 for (
const auto *child = nodeComposite.beginChildren();
144 child < nodeComposite.endChildren(); ++child) {
145 NodePair sp = isFlipped ? NodePair(nodeOther, *child, m_id) : NodePair(*child, nodeOther, m_id);
148 if (minDistance == DoubleInfinity || sp.getDistance() < minDistance) {
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26