Перекрывающиеся полигоны на 2D-плоскости

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

я смотрел на bst-деревья (и quad-деревья), но они, кажется, не работают слишком хорошо, когда полигоны сильно перекрываются.

какие-нибудь хорошие идеи, которые я должен проверить, прежде чем я начну свой собственный бред?

изменить

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


java algorithm data-structures polygon
person aepurniet    schedule 10.08.2010    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я бы посмотрел на двумерные сегментные графики Делоне . Посмотрите также на полигоны Nef. В CGAL есть множество операций с множествами над полигонами. Ответы на этот вопрос также могут быть полезны

Редактировать Если ваши полигоны представляют собой прямоугольники без поворота, см. R-Trees

person deinst    schedule 10.08.2010
comment
это немного более интенсивно, чем я искал. это также написано на каком-то академическом диалекте, который я с трудом понимаю. Я собираюсь отредактировать вопрос, надеюсь, больше людей укусит. - person aepurniet; 10.08.2010
comment
Я обновил его. CGAL имеет более общие процедуры обработки полигонов. Вам, вероятно, лучше использовать предварительно запрограммированные процедуры, потому что в геометрии угловые случаи вас убьют. - person deinst; 10.08.2010
comment
cgal.org/Manual/latest/doc_html/cgal_manual/Point_set_2/ казался более точным с тем, что мне нужно сделать, но он работает только с наборами точек, не смог найти ничего, что работало бы с прямоугольниками или многоугольниками. эта библиотека, безусловно, действительно классная ссылка. - person aepurniet; 10.08.2010
comment
Вам нужно будет написать некоторый код для интерфейса. Графики сегментов дают вам набор ячеек, и каждая ячейка не пересекает границу полигона, и легко перечислить ячейки в заданном прямоугольнике. Вам нужно будет сопоставлять ячейки с полигонами по мере построения. Посмотрите также на общие операции с полигонами, на которые я ссылался. - person deinst; 10.08.2010
comment
Я думал, что ячейки строятся из набора точек и не могут быть созданы сами по себе? - person aepurniet; 10.08.2010

arrow_upward
0
arrow_downward

Зачем ты это сам пишешь? Java предлагает сложные тесты пересечения. Вы можете преобразовать свои структуры данных многоугольника и свой прямоугольник в Java.awt.geom.Area, а затем вызвать метод Area.intersect(), который сделает всю математику за вас.

Он также заботится обо всех редко встречающихся (но все же важных) особых случаях, которые действительно неприятно отлавливать.

person msteiger    schedule 10.08.2010
comment
ну, вы предлагаете алгоритм O (n), который является решением, но определенно не лучшим; или очень хороший, если, скажем, это нужно делать 60 раз в секунду для 10к полигонов. Я не хочу сам писать тесты пересечения, мне просто нужно выяснить, в какой структуре данных хранить полигоны, чтобы эффективно выполнять тесты. - person aepurniet; 10.08.2010

arrow_upward
0
arrow_downward

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

person aepurniet    schedule 27.08.2010