Эффективная структура данных для хранения трехмерных точек

Я ищу эффективные структуры данных для хранения трехмерных точек (x, y, z). Эффект сохранения в точках в структуре данных должен генерировать более эффективную структуру памяти и более быстрый поиск определенного набора координат. Трехмерные точки сопоставляются с определенным идентификатором, поэтому он должен иметь возможность отслеживать каждый набор координат, который я ищу для любой доступной реализации.

x, y, z дает декартовы координаты каждого узла.

id x y z

1 14.566132 34.873772 7.857000

2 16.022520 33.760513 7.047000

3 17.542000 32.604973 6.885001

4 19.163984 32.022469 5.913000

5 20.448090 30.822802 4.860000

6 21.897903 28.881084 3.402000

7 18.461960 30.289471 8.586000

8 19.420759 28.730757 9.558000

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

Заранее спасибо!


c++ 3d data-structures cgal binary-search-tree
person Yoko    schedule 05.03.2016    source источник
comment
Какие варианты вы рассматривали до сих пор?   -  person Oliver Charlesworth    schedule 05.03.2016
comment
Рассмотрим октодерево en.wikipedia.org/wiki/Octree и en.wikipedia.org/wiki/R-tree, но не нашел хорошей реализации для хранения 3D-координат   -  person Yoko    schedule 06.03.2016
comment
Вы должны указать, что для вас важно. Читаемость кода (простой массив структуры), автоматическая векторизация (структура массивов) или, может быть, хорошее время вставки/поиска (octree?). Например, в вычислениях N-тел октодерево является лучшим подходом для того, чтобы быть O (nlog n).   -  person Hopobcn    schedule 06.03.2016
comment
1 миллион троек с плавающей запятой далеко не огромен.   -  person o9000    schedule 06.03.2016
comment
Маловероятно, что структура с более эффективным использованием памяти, чем последовательный список, ускорит поиск. Как правило, есть компромисс. Если вам нужен более быстрый поиск, вам, вероятно, потребуется больше памяти. Если вы хотите использовать меньше памяти, вам придется страдать от более медленного времени поиска.   -  person Jim Mischel    schedule 07.03.2016

Ответы (3)


arrow_upward
2
arrow_downward

более эффективная структура памяти

Эффективнее памяти, чем что? Список? Для этого вам понадобится компрессия.

более быстрый поиск определенного набора координат

Если вы хотите найти k ближайших точек по набору координат, хорошо подойдет шаровое дерево. вариант.

Если вы хотите выполнить поиск в томе, квадродерево (или octree) работает лучше.

person o9000    schedule 06.03.2016
comment
Да, более эффективно использовать память, чем хранить все в списке struct columns { double x; двойной у; двойной г; }; int main(){ std::vector‹coordinate› список; координата а = координаты (2.123123,2.1231,3.112); список .push_pack(a); } - person Yoko; 06.03.2016

arrow_upward
2
arrow_downward

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

Если вам нужно найти координаты рядом с тестовой координатой, тогда используйте balltree или octree или что-то в этом роде, но это не похоже на то, что вам нужно.

person Aiken Drum    schedule 06.03.2016
comment
При хэшировании они должны быть равны по крупицам. Если значения поиска являются результатом операций с плавающей запятой, это может быть неверно из-за потери точности. Если это так, хеш-функция должна учитывать максимальную ошибку и отбрасывать младшие значащие биты перед фактическим хэшированием. Но я думаю, что ОП немного смущен тем, что ему нужно. - person o9000; 06.03.2016
comment
Я знаю, поэтому я квалифицировал свой ответ только для точных совпадений. В случае поиска совпадений в пределах определенного эпсилон удаление битов из нижней части объединит только некоторых соседей (примерно восьмую часть в случае трехмерных координат). Это сложнее визуализировать с помощью числа с плавающей запятой, но учтите побитовую разницу между ближайшими целочисленными соседями 255 и 256. Я бы не рекомендовал этого. Поиск на основе эпсилон требует другой структуры данных. - person Aiken Drum; 06.03.2016

arrow_upward
0
arrow_downward

Вы можете использовать struct:

struct coordinate
{
   double x;
   double y;
   double z;
} points[1000000];
person Rajeev Singh    schedule 05.03.2016
comment
Одно небольшое уточнение: учитывая, что у него всего 7 значащих цифр, он может захотеть использовать float вместо double. Это нередкий выбор для 3D-приложений... - person H. Guijt; 05.03.2016
comment
Вам решать, сколько точного значения вы хотите сохранить! - person Rajeev Singh; 05.03.2016
comment
Вот только структура Ищу структуру данных для хранения 3д координат. В этой структуре мне придется искать определенный набор координат, а это не то, что я ищу. - person Yoko; 06.03.2016