Какова наилучшая структура данных для представления узлов в трехмерном пространстве?

Question

... и спасибо за чтение ...

Я все еще учусь веревки, так что будьте снисходительными ... ;-)

Я пишу функцию, которая зацепляется твердого вещества в пространстве. Сетка производится с помощью объектов класса «Node», и каждый узел представлен:

int id 
double p 
double r 

Первоначально я думал, что карта будет путь: с картой я могу сделать ассоциацию между ключ «id» и второй ключ (указатель на объект узла).

Что-то вроде этого:

int nodeId; 
Node *node; 
std::map<int, Node *> NodeMap; 

Затем, когда я создаю узлы я просто называю «новый» оператор. Например, в цикле я сделать что-то вроде этого:

node = new Node(i); // the node constructor sets the id to the value of i. 

и добавить новый узел к карте:

NodeMap[i] = node; 

Но .... я понял, что мне нужно будет сделать поиск на карте не по первому ключу (id), а по параметрам p и r (координаты узла).

Другими словами, мне понадобится то, что возвращает идентификатор узла, заданный значениями p и r. Карта является идеальным контейнером, если поиск выполняется с использованием целого первого ключа (id). Есть ли у кого-нибудь предложение о том, как решить эту проблему?

Спасибо большое! AsvP.

Answer 1

A карта <> не будет работать. Консолидирующие контейнеры C++ работают на основе ключевого равенства, а сравнение чисел с плавающей запятой для равенства не работает вообще хорошо.

Похоже, вам нужно найти узел, заданный x и y. Лучший способ будет зависеть от того, что вы пытаетесь выполнить. Вы пытаетесь найти ближайший узел, учитывая координаты, или вы собираетесь вычислять координаты, которые очень близки к узлу, а затем вам нужно найти узел?

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

(Разумеется, если узлы находятся в какой-то предсказуемой сетке, вы должны быть в состоянии предоставить некоторые средства для вычисления напрямую, например round x и y до ближайшего целого, если у вас есть целые точки решетки.)

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

Answer 2

Как и любой «что я должен использовать, чтобы представить эту структуру» вопрос это действительно зависит от , как вы хотите, чтобы взаимодействовать с ним

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

Что-то удерживать объекты, которые нужно визуализировать, общая структура - это Binary space Partitioning Tree, которая позволяет эффективно отбирать объекты, которые определенно не видны или не закрыты другими.

Редактировать; Я пропустил, что вы индексировали по плавающей запятой. Обычно это плохая идея (поскольку точность, требуемая на большинстве стандартных карт, вызовет проблемы, связанные с нестабильностью поведения с плавающей точкой). Если вы не действительно такое поведение

В этом случае вам нужно иметь какой-то способ его обработки, такие как:

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

Answer 3

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

Answer 4

Что вы на самом деле пытаетесь сделать?

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

В качестве примера рассмотрит единичную сферу, которая принимает параметры и, v (0 ... 2ПИ) и (0 ... PI) и превращают их в координаты, выполнив:

x = sin(u)*cos(v); 
y = sin(u)*sin(v); 
z = cos(u); 

Это может используется для создания сетки путем изменения u и v в соответствующих диапазонах и слияния любых дублированных вершин. например возьмем u = 0, u = 0,1, v = 0 и v = 0,1, и вы можете создать четыре вершины V (u, v), которые позволят вам создать два треугольника. Поскольку я притворяюсь, что это общий случай, а не особый случай, вам придется делать такие вещи, как проверять дубликаты и объединять их, проверять вырожденные треугольники и удалять их.

Answer 5

Не связано с проблемой поиска, но с вашим созданием Nodes с использованием new. Если карта владеет Узлов, как представляется, сделать в вашем случае, вы можете sinply сказать:

map <int, Node> mymap;  // map of Nodes, not pointers to Nodes 
... 
myMap[i] = Node(whatever); 

Это позволит значительно упростить управление памятью. В C++ вы должны избегать явного распределения динамической памяти с new, где это возможно.

Answer 6

Jherico поражает гвоздь на голове. Я использую два параметра для создания 3D-сетки. Эти два параметра представляют собой цилиндрические координаты. Один из них - угол, а второй - z вдоль оси. Радиус - это константа, как и его пример сферы. Я могу создать сетку, но мне нужно ее обновить, а функция, которая выполняет обновление, не принимает идентификатор в качестве входного аргумента. Он использует «исходное положение», используя параметры p и r.