Перекрытие многоугольников на 2D-плоскости

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

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

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

редактировать

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

источник

2010-08-10 aepurniet

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

источник

2010-08-27 16:41:53 aepurniet

Я бы смотрел 2-d segment delaunay graphs. Смотри также Nef polygons. CGAL имеет множество заданных операций на polygons. Ответы на этот question также может иметь значение

Edit Если многоугольники не имели повернутые прямоугольники см R-Trees

источник

2010-08-10 11:52:24 deinst

Это немного более интенсивное, чем я искал. это также написано на каком-то академическом диалекте, что у меня проблемы с пониманием. я собираюсь отредактировать вопрос, надеюсь, больше людей кусают. – aepurniet

Я обновил его. CGAL имеет более общие процедуры обработки полигонов. Вероятно, вам лучше использовать запрограммированные подпрограммы, потому что в геометрии угловые случаи убьют вас. – deinst

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Point_set_2/Chapter_main.html показалось более точным с тем, что мне нужно делать, но оно работает только с множествами точек, не может найти ничего, что работает на прямоугольники или многоугольники. эта библиотека, безусловно, действительно крутая ссылка. – aepurniet

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

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

источник

2010-08-10 12:11:27 msteiger

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

Перекрытие многоугольников на 2D-плоскости

ответ

Смежные вопросы