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

Question

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

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

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

Моя попытка пока:

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-дерево чрезвычайно распространено и не слишком сложно для реализации. Также актуальным является R-дерево, хотя я не реализовал это и не могу комментировать его сложность.