Использование «приблизительной» STL-карты

Question

Я хотел бы создать карту STL, чтобы узнать, достаточно ли близко к другому элементу в трехмерном пространстве. До сих пор мой «менее-функтор» работал достаточно хорошо, вставленный по следующей ссылке.

Теперь эта проблема не совсем проблема «ближайшего соседа». Скорее это проблема «есть ли сосед на некотором расстоянии».

В моем примере показано только одно измерение. Я прояснил размеры Y/Z для ясности.

My attempt so far:

class ApproximateLessFunctor { 
public: 
    ApproximateLessFunctor(float fudgeFactor) : 
    mFudgeFactor(fudgeFactor) {}; 

    bool operator()(float a, float b) const { 
    return (a < (b - mFudgeFactor)); 
    } 

    float mFudgeFactor; 
}; 

typedef map<float, int, ApproximateLessFunctor> XAxisMap; 

class XAxis { 
public: 
    XAxisMap vMap; 

    XAxis(ApproximateLessFunctor functor, float x, int v) 
    : vMap(functor) 
    { 
    vMap.insert(make_pair(x, v)); 
    } 
}; 

В редких случаях, и я имею в виду на самом деле редкоземельной подсистеме карты не найти соответствующую запись, когда позиции совпадают.

Есть ли что-то, что я могу сделать лучше, чтобы реализовать это, все еще используя контейнеры STL?

Answer 1

Теперь эта проблема не совсем проблема «ближайшего соседа». Скорее это проблема «есть ли сосед на некотором расстоянии».

Последний формулируется довольно просто с точки зрения первого. Найдите ближайшего соседа, затем определите, достаточно ли он. Это похоже на разумный путь, чтобы рассмотреть количество доступных вам структур данных для этой задачи.

А именно, kd-tree чрезвычайно распространен и не слишком сложно реализовать. Также актуальным является R-tree, хотя я его не реализовал и не могу прокомментировать его трудности.