summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGabda <gabda87@gmail.com>2019-05-28 13:26:36 +0200
committerNiels Martin Hansen <nielsm@indvikleren.dk>2019-10-08 08:53:19 +0200
commit652fb4065253685eb4c16eefb2ced070e8112d25 (patch)
treed84cf6bf164d5abf753d061299992c6e74a29adb
parent1e5029563cb68e53e41299a5d92e317566d7ba66 (diff)
downloadopenttd-652fb4065253685eb4c16eefb2ced070e8112d25.tar.xz
Codechange: Performance improvement in k-d tree FindNearest()
-rw-r--r--src/core/kdtree.hpp8
1 files changed, 5 insertions, 3 deletions
diff --git a/src/core/kdtree.hpp b/src/core/kdtree.hpp
index 59f3da810..c37ab8eea 100644
--- a/src/core/kdtree.hpp
+++ b/src/core/kdtree.hpp
@@ -240,7 +240,7 @@ class Kdtree {
NOT_REACHED(); // a.first == b.first: same element must not be inserted twice
}
/** Search a sub-tree for the element nearest to a given point */
- node_distance FindNearestRecursive(CoordT xy[2], size_t node_idx, int level) const
+ node_distance FindNearestRecursive(CoordT xy[2], size_t node_idx, int level, DistT limit = std::numeric_limits<DistT>::max()) const
{
/* Dimension index of current level */
int dim = level % 2;
@@ -261,11 +261,13 @@ class Kdtree {
best = SelectNearestNodeDistance(best, this->FindNearestRecursive(xy, next, level + 1));
}
+ limit = min(best.second, limit);
+
/* Check if the distance from current best is worse than distance from target to splitting line,
* if it is we also need to check the other side of the split. */
size_t opposite = (xy[dim] >= c) ? n.left : n.right; // reverse of above
- if (opposite != INVALID_NODE && best.second >= abs((int)xy[dim] - (int)c)) {
- node_distance other_candidate = this->FindNearestRecursive(xy, opposite, level + 1);
+ if (opposite != INVALID_NODE && limit >= abs((int)xy[dim] - (int)c)) {
+ node_distance other_candidate = this->FindNearestRecursive(xy, opposite, level + 1, limit);
best = SelectNearestNodeDistance(best, other_candidate);
}