0

現在、最も近い座標を照会するために、2 次元 (緯度と経度) で KD ツリーを構築しようとしています。座標 (ID、緯度、経度) をベクターにプッシュし、このベクターを KD ツリーのコンストラクターに渡します。

しかし、コンストラクターの最後にブレークポイントを設定すると (再帰ビルド呼び出しが返された後) 、ルート項目の left-pointers と right-pointers にゴミが含まれます。ビルドルーチン中に、かなり長い間正しい値が含まれているように見えますが、ある時点で失われます...再帰ルーチンで明らかに犯した間違いに誰かが気づきますか?

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

1 に答える 1

2

KDItem *item = &KDItem() is not a valid way to allocate a new object. This KDItem will exist on the stack until it goes out of scope (at function return, for example). Try 

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

Be sure to delete the objects in your destructor. Also, it's much more idiomatic (and readable) to write item->left instead of (*item).left

于 2013-07-29T15:51:02.710 に答える