Как вернуть все точки в BoundingVolume

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

Есть ли у сообщества идеи? Я рад использовать другие библиотеки, если это необходимо, меня привлекает jmonkey из-за поддержки сообщества и формы BoundingCapsule.

Редактировать: я подумал о том, чтобы перебрать все свои точки и использовать .contains, к сожалению, пространство содержит сотни тысяч точек и относительно крошечные капсулы. Наверняка должна быть какая-то умная математика, которую мне не хватает.


java algorithm 3d jmonkeyengine
person Arjun Sol    schedule 29.10.2012    source источник
comment
С математической точки зрения внутри объема бесконечно много точек. Я не знаком конкретно с jmonkeyengine, но похоже, что вам нужно немного уточнить свой вопрос, чтобы получить полезные ответы.   -  person Code-Apprentice    schedule 30.10.2012
comment
Вы имеете в виду, что у вас есть набор объектов Point, и вы хотите вернуть все те объекты, которые находятся внутри ограничивающего объема?   -  person chm    schedule 30.10.2012
comment
Возможно, некоторые пояснения: у меня есть предопределенный набор объектов Point, я хотел бы поместить ограничивающий объем (предпочтительно капсулу) в этот набор и вернуть все точки внутри объема.   -  person Arjun Sol    schedule 30.10.2012

Ответы (1)


arrow_upward
0
arrow_downward

Если вам нужно сделать это только один раз, то нет ничего лучше, чем сверять каждую точку с ограничивающим объемом.

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

В зависимости от ваших потребностей вы можете использовать сетку, quadtree, a Дерево Kd или R-tree для ускорения вашего пространственные запросы. Приведенный выше список не является исчерпывающим списком структур ускорения, но он включает в себя некоторые из наиболее часто используемых опций.

person comingstorm    schedule 29.10.2012
comment
Хорошо, я думаю, что нашел обходной путь. Я могу запросить все точки в полях x y z, например. выберите * из таблицы точек, где x ‹ капсула.maxX и x › капсула.minX и т. д. Это даст мне все точки в пределах рамки вокруг капсулы. Я могу перебрать их и проверить на наличие капсулы. - person Arjun Sol; 02.11.2012
comment
Поскольку вы обращаетесь к ним из базы данных, вы должны знать, что некоторые базы данных предоставляют пространственный индекс, предназначенный для такого рода запросов. Попробуйте изучить Postgres в качестве примера с открытым исходным кодом. - person comingstorm; 02.11.2012
comment
Действительно, я думал о переходе на mongodb, к сожалению, он поддерживает только 2D-индекс. - person Arjun Sol; 02.11.2012