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

Question

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

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

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

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

Answer 1

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

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

Answer 2

Вы можете легко использовать набор следующим образом:

#include <set>
#include <cassert>

const double epsilon(1e-8);

class Coordinate {
public:
Coordinate(double x, double y, double z) :
  x_(x), y_(y), z_(z) {}

private:
double x_;
double y_;
double z_;

friend bool operator<(const Coordinate& cl, const Coordinate& cr);
};

bool operator<(const Coordinate& cl, const Coordinate& cr) {
  if (cl.x_ < cr.x_ - epsilon) return true;
  if (cl.x_ > cr.x_ + epsilon) return false;

  if (cl.y_ < cr.y_ - epsilon) return true;
  if (cl.y_ > cr.y_ + epsilon) return false;

  if (cl.z_ < cr.z_ - epsilon) return true;

  return false;

}

typedef std::set<Coordinate> Coordinates;

// Not thread safe!
// Return true if real processing is done
bool Process(const Coordinate& coordinate) {
  static Coordinates usedCoordinates;

  // Already processed?
  if (usedCoordinates.find(coordinate) != usedCoordinates.end()) {
    return false;
  }

  usedCoordinates.insert(coordinate);

  // Here goes your processing code



  return true;

}

// Test it
int main() {
  assert(Process(Coordinate(1, 2, 3)));
  assert(Process(Coordinate(1, 3, 3)));
  assert(!Process(Coordinate(1, 3, 3)));
  assert(!Process(Coordinate(1+epsilon/2, 2, 3)));
}

Answer 3

Разделите ваше пространство на отдельные корзины. Может быть бесконечно глубокими квадратами или кубами. Сохраните ваши обработанные координаты в простом связанном списке, отсортированном, если хотите, в каждой корзине. Когда вы получите новую координату, прыгните в корзину и пройдитесь по списку в поисках новой точки.

Остерегайтесь сравнений с плавающей запятой. Вам нужно либо превратить значения в целые числа (скажем, умножить на 1000 и усечь), либо решить, насколько близко 2 значения следует считать равными.

Answer 4

Если у вас уже есть класс Coordinate, добавьте хеш-функцию и сохраните hash_set координат. Выглядело бы что-то вроде:

struct coord_eq
{
  bool operator()(const Coordinate &s1, const Coordinate &s2) const
  {
    return s1 == s2;
    // or: return s1.x() == s2.x() && s1.y() == s2.y() && s1.z() == s2.z();
  }
};

struct coord_hash
{
  size_t operator()(const Coordinate &s) const
  {
     union {double d, unsigned long ul} c[3];
     c[0].d = s.x();
     c[1].d = s.y();
     c[2].d = s.z();
     return static_cast<size_t> ((3 * c[0].ul) ^ (5 * c[1].ul) ^ (7 * c[2].ul));
  }
};

std::hash_map<Coordinate, coord_hash, coord_eq> existing_coords;

Answer 5

Использовать std :: set. Определите тип для 3d-координаты (или используйте boost :: tuple) с оператором <определено. При добавлении элементов вы можете добавить его в набор, и, если он был добавлен, выполнить обработку. Если он не был добавлен (потому что он там уже существует), не выполняйте обработку. </p>

Однако, если вы используете удвоения, помните, что ваш алгоритм потенциально может привести к непредсказуемому поведению. IE, (1.0, 1.0, 1.0) совпадает с (1.0, 1.0, 1.000000001)?

Answer 6

Ожидаете ли вы / требует точных совпадений? Это может быть трудно реализовать с двойными. Например, если вы обработали (1.0, 1.0, 1.0) и затем получили (0.9999999999999, 1.0, 1.0), считаете ли вы его тем же? Если это так, вам нужно будет либо применить какое-то приближение, либо определить границы ошибок.

Однако, чтобы ответить на сам вопрос: первый метод, который приходит на ум, - это создание одного индекса (либо строки, либо цепочки битов, в зависимости от того, насколько читаемыми вы хотите, чтобы все было). Например, создайте строку «(1.0,1.0,1.0)» и используйте ее как ключ к вашей карте. Это облегчит поиск карты, сохранит читабельность кода (а также позволит легко вывести содержимое карты для целей отладки) и обеспечит разумную производительность. Если вам требуется намного более высокая производительность, вы можете использовать алгоритм хеширования для численного объединения трех координат без использования строки.

Answer 7

Используйте любое уникальное преобразование ваших трехмерных координат и сохраняйте только список результатов.

Пример: md5 ('X, Y, Z') уникален, и вы можете сохранить только полученную строку.

Хеш - не идеальная идея, но вы понимаете концепцию. Найдите любое уникальное преобразование, и у вас оно есть.

/ Вея

Answer 8

Как насчет использования boost :: tuple для координат и сохранения кортежа в качестве индекса для карты?

(Возможно, из этого ответа вам также может понадобиться идея деления на эпсилон.)

Answer 9

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

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

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

Стоит также упомянуть, что, выполняя подобные операции с плавающими или двойными числами, вы должны быть очень осторожны с точностью - если (0, 0, 0,01) совпадает с (0, 0, 0.01000001)? Если это так, вам нужно взглянуть на функции сравнения, которые вы используете, независимо от структуры данных. Полагаю, это также зависит от источника ваших координат.

Answer 10

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

Итак, предполагая, что ваше пространство ограничено по размеру и вы знаете, какова максимальная точность, вы можете сформировать функцию, которая с учетом (x, y, z) преобразует их в уникальное число или строку - это может быть сделано только если вы знаете, что ваша точность ограничена (например, никакие два объекта не могут занимать один и тот же кубический сантиметр). Кодирование координаты позволяет использовать одну карту / хэш с O (1).

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