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

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). У кого-нибудь есть предложения по решению этой конкретной проблемы?

Большое спасибо! АСВП.

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

Карта <> не будет работать. Ассоциативные контейнеры C ++ работают на основе равенства ключей, а сравнение чисел с плавающей точкой на равенство не работает вообще.

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

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

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

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

Answer 6

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

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

В качестве примера рассмотрим единичную сферу, которая принимает параметры u, v (0 ... 2PI) и (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), которые позволят вам создать два треугольника. Поскольку я притворяюсь, что это общий случай, а не особый случай, вам придется делать такие вещи, как проверка, являются ли вершины дублирующимися, и объединение их, проверка вырожденных треугольников и удаление их.