CODEWITHSUNDEEP
c++treeknnbounding-boxkdtree
OUTWEST
OUTWEST

Reputation: 11

KDTree buildBalancedTree infinite recursion issue

I tried to speed up my KD tree by implementing balancing and bounding boxes, but now it can't even build the tree, and I don't understand why.

Input Example Here's how I provide the input:

n and dim = {3, 2} points: {0, 0} {3, 3} {3, 0}

Issue When I attempt to build the tree, the function seems to go into infinite recursion, and the program hangs. I suspect the problem lies in my buildBalancedTree function.

Code Here's the implementation of the buildBalancedTree function:

std::unique_ptr<KDTree::Node> KDTree::buildBalancedTree(
std::vector<Point>& points, 
int depth,
std::vector<long double> min_bound, 
std::vector<long double> max_bound) {

if (points.empty()) {
    return nullptr;
}

int axis = depth % points[0].point.size();

std::sort(points.begin(), points.end(), [axis](const Point& a, const Point& b) {
    return a.point[axis] < b.point[axis];
});

size_t medianIndex = points.size() / 2;
Point medianPoint = points[medianIndex];

// Update bounds for left and right subtrees
std::vector<long double> left_max = max_bound;
left_max[axis] = medianPoint.point[axis];

std::vector<long double> right_min = min_bound;
right_min[axis] = medianPoint.point[axis];

auto node = std::make_unique<Node>(std::move(medianPoint), min_bound, max_bound);

node->left = buildBalancedTree(
    points, depth + 1, min_bound, left_max
);
node->right = buildBalancedTree(
    points, depth + 1, right_min, max_bound
);

return node;
}

My Thoughts I believe the infinite recursion happens because I am passing the same points vector to both the left and right subtree builds. However, I am not sure how to correctly partition the points vector for the subtrees.

How can I fix this issue? If necessary, I can provide the full code of my program.

Upvotes: 0

Views: 45

Answers (0)

Related Questions