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

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

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

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

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

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

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

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

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

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

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

Используйте любое уникальное преобразование ваших 3D-координат и сохраните только список результатов.

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

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

/ Вей

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

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

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

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

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

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

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

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;

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

Предполагая, что у вас уже есть класс 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;

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

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

Вы можете легко определить компаратор для одноуровневого 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;
}

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

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

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

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

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

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

#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)));
}

Вы можете использовать std::set с трехмерными координатами или отсортированный std::vector. Оба предоставят вам логарифмический поиск времени. В любом случае вам необходимо реализовать оператор сравнения «меньше чем» для вашего класса трехмерных координат.

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

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

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

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

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

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

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

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

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

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