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

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

3 голосов
/ 26 марта 2012

Я хотел бы создать карту 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?

1 Ответ

1 голос
/ 26 марта 2012

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

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

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

...