Самый быстрый способ найти, если 3D-координата уже используется

Question

Используя C ++ (и Qt), мне нужно обработать большое количество трехмерных координат.

В частности, когда я получаю трехмерную координату (состоящую из 3-х двойных), мне нужно проверить в списке, была ли эта координата уже обработана. Если нет, то я обрабатываю его и добавляю в список (или контейнер).

Количество координат может стать очень большим, поэтому мне нужно сохранить обработанные координаты в контейнере, что обеспечит быструю проверку, если 3D-координата уже содержится в контейнере.

Я думал об использовании карты карты, сохраняя координату x, затем координату y, затем координату z, но это делает его довольно утомительным, так что я на самом деле надеюсь, что есть много лучший способ сделать это, что я не могу придумать.

Answer 1

Вы можете легко определить компаратор для одноуровневого std::map, так что поиск станет менее громоздким Нет причин бояться этого. Компаратор определяет порядок аргумента шаблона _Key карты. Затем его также можно использовать для мультикарты и наборов коллекций.

Пример:

#include <map>
#include <cassert>


struct Point {
  double x, y, z;
};

struct PointResult {
};

PointResult point_function( const Point& p ) { return PointResult(); }

// helper: binary function for comparison of two points
struct  point_compare {
  bool operator()( const Point& p1, const Point& p2 ) const {
    return p1.x < p2.x
      || ( p1.x == p2.x && ( p1.y < p2.y 
      || ( p1.y == p2.y && p1.z < p2.z ) 
      )
      );
  }
};

typedef std::map<Point, PointResult, point_compare> pointmap;

int _tmain(int argc, _TCHAR* argv[])
{

pointmap pm;

Point p1 = { 0.0, 0.0, 0.0 };
Point p2 = { 0.1, 1.0, 1.0 };

pm[ p1 ] = point_function( p1 );
pm[ p2 ] = point_function( p2 );
assert( pm.find( p2 ) != pm.end() );
    return 0;
}

Answer 2

Зачем беспокоиться? Какую «обработку» вы делаете? Если это не очень сложно, то, вероятно, быстрее просто снова выполнить расчет, а не тратить время на поиск информации на огромной карте или в хеш-таблице.

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

Я понимаю, что на самом деле это не ответ на ваш вопрос, это вопрос на ваш вопрос.

Answer 3

Вы можете использовать hash_set любого типа хэширования - например, превратить каждый кортеж в строку "(x, y, z)". hash_set делает быстрый поиск, но хорошо обрабатывает столкновения.

Answer 4

Если вы напишите вспомогательный класс с простым общедоступным интерфейсом, это значительно уменьшит практическую скуку деталей реализации, таких как использование map<map<map<>>>. Красота инкапсуляции!

Тем не менее, вы могли бы настроить хэш-карту, чтобы хорошо справиться с задачей. Просто объедините три пары, чтобы получить ключ к точке в целом. Если вас беспокоит множество коллизий между точками с симметричными координатами (например, (1, 2, 3) и (3, 2, 1) и т. Д.), Просто сделайте хеш-ключ асимметричным относительно x, y и координаты z, используя битовый сдвиг или что-то подобное.

Answer 5

Выберите константу, чтобы масштабировать координаты так, чтобы 1 единица описывала приемлемо маленькое поле, и все же целая часть наибольшего компонента по величине поместилась бы в 32-битное целое число; преобразовать компоненты X, Y и Z результата в целые числа и объединить их вместе. Используйте это как хеш-функцию для карты или хеш-таблицы (НЕ как индекс массива, вам нужно иметь дело с коллизиями).

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

Answer 6

Вы можете использовать std::set 3D-координат или отсортировать std::vector. И то, и другое даст вам логарифмическое время поиска. В любом случае вам нужно реализовать оператор сравнения меньше, чем для вашего класса координат 3D.

Answer 7

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

Answer 8

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

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

"но это делает его довольно утомительным для использования" --- обычно вы можете обойти это, typedefs или классы-оболочки (в этом случае рекомендуется использовать оболочки).

Если вам не нужно использовать координаты 3D каким-либо пространственно значимым способом ( такие вещи, как «дать мне все точки на расстоянии X от точки P»), то я предлагаю вам просто найдите способ хеширования каждой точки и используйте одну хэш-карту ... O (n) создание, O (1) доступ (проверка, если он был обработан), вы не можете сделать намного лучше, чем это.

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

Если вы получаете хорошо распределенные данные в известном диапазоне ... используйте octree .

Если у вас есть дистрибутив, который имеет тенденцию к кластеризации, то используйте k-d trees . Тебе понадобиться восстановить дерево k-d после ввода новых координат (не обязательно каждый раз, только когда это становится чрезмерно несбалансированным). Проще говоря, Kd-деревья похожи на Octrees, но с неравномерным делением.

Answer 9

Что-то в этом направлении может быть:

struct Coor {
    Coor(double x, double y, double z)
    : X(x), Y(y), Z(z) {}
    double X, Y, Z;
}

struct coords_thesame
{
  bool operator()(const Coor& c1, const Coor& c2) const {
    return c1.X == c2.X && c1.Y == c2.Y && c1.Z == c2.Z;
  }
};

std::hash_map<Coor, bool, hash<Coor>, coords_thesame> m_SeenCoordinates;

Не проверено, используйте на свой страх и риск:)