我目前正在尝试构建二维(纬度和经度)的 KD 树以查询最近的坐标。我将坐标(ID、纬度、经度)推送到一个 vector 中,并将该 vector 传递到我的 KD-Tree 的构造函数中。
但是当我在构造函数的末尾设置断点时(递归构建调用返回后)我的根项在其左指针和右指针中只包含垃圾。在构建例程中,它们似乎包含了相当长一段时间的正确值,但在某些时候它们丢失了......有没有人看到我在递归例程中明显犯的错误?
#include "stdafx.h"
#include "KDTree.h"
KDTree::KDTree(void)
{
}
KDTree::KDTree(vector<Coordinate*> c)
{
coordinates = c;
root = &KDItem();
build(root, 0, 0, c.size() - 1);
}
KDTree::~KDTree(void)
{
}
void KDTree::build(KDItem* item, int depth, int startIndex, int stopIndex)
{
int coordinateCount = stopIndex - startIndex + 1;
if (coordinateCount == 1)
{
(*item).left = NULL;
(*item).right = NULL;
(*item).value = NULL;
(*item).leaf = coordinates[startIndex];
return;
}
(*item).left = &KDItem();
(*item).right = &KDItem();
int medianIndex = 0;
float median = 0;
if (depth % 2 == 0)
{
sort(coordinates.begin() + startIndex, coordinates.begin() + stopIndex + 1, Coordinate::sortByLatitude);
Coordinate::findLatitudeMedian(&coordinates, startIndex, stopIndex, &median, &medianIndex);
}
else
{
sort(coordinates.begin() + startIndex, coordinates.begin() + stopIndex + 1, Coordinate::sortByLongitude);
Coordinate::findLongitudeMedian(&coordinates, startIndex, stopIndex, &median, &medianIndex);
}
(*item).value = median;
build((*item).left, depth+1,startIndex, medianIndex-1);
build((*item).right, depth+1,medianIndex,stopIndex);
}
int KDTree::findNearestNodeIndex(float latitude, float longitude)
{
KDItem* item = findNearestItem(latitude, longitude, root);
return (*(*item).leaf).Index();
}
KDItem* KDTree::findNearestItem(float firstVal, float secondVal, KDItem* item)
{
if ((*item).value == NULL) return item;
if (firstVal < (*item).value)
{
return findNearestItem(secondVal, firstVal, (*item).left);
}
else
{
return findNearestItem(secondVal, firstVal, (*item).right);
}
}
最佳答案
KDItem *item = &KDItem()
不是分配新对象的有效方法。这个 KDItem 将存在于堆栈中,直到它超出范围(例如,在函数返回时)。尝试
(*item).left = new KDItem();
请务必删除
析构函数中的对象。此外,编写 item->left
而不是 (*item).left
关于c++ - KD-Tree 构建例程中的严重错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17928350/