From 652fb4065253685eb4c16eefb2ced070e8112d25 Mon Sep 17 00:00:00 2001 From: Gabda Date: Tue, 28 May 2019 13:26:36 +0200 Subject: Codechange: Performance improvement in k-d tree FindNearest() --- src/core/kdtree.hpp | 8 +++++--- 1 file 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::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); } -- cgit v1.2.3-70-g09d2