Гадкий баг в рутине сборки KD-Tree

В настоящее время я пытаюсь построить KD-дерево в 2-х измерениях (широта и долгота) для запроса ближайшей координаты. Я помещаю координаты (ID, Широта, Долгота) в вектор и передаю этот вектор в конструктор моего KD-дерева.

Но когда я установил точку останова до конца конструктора (после того, как рекурсивный вызов сборки вернулся) мой корневой элемент содержит только мусор в левом и правом указателях. Во время процедуры сборки кажется, что они довольно долго содержат правильные значения, но в какой-то момент они теряются … Кто-нибудь видит ошибку, которую я, очевидно, допустил в моей рекурсивной процедуре?

#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);
}
}

0

Решение

KDItem *item = &KDItem() не является допустимым способом выделения нового объекта. Этот KDItem будет существовать в стеке до тех пор, пока он не выйдет из области видимости (например, при возврате функции). Пытаться

(*item).left = new KDItem();

Обязательно delete объекты в вашем деструкторе. Кроме того, гораздо более идиоматично (и читабельно) писать item->left вместо (*item).left

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]