Логические операции с прямоугольными многоугольниками
Аваст там товарищи программисты!
У меня такая проблема:
У меня есть два перекрывающихся прямоугольника, как показано на рисунке ниже.
Я хочу вычислить многоугольник, состоящий из точки ABCDEF.
Альтернативное рождественское описание: красная формочка для печенья отрезает часть черного печенья. Я хочу вычислить черную печеньку.
Каждый прямоугольник представляет собой структуру данных с 4-мя 2-мерными вершинами.
Каков наилучший алгоритм для этого?
Ответы 4
Это частный случай общего отсечения 2D-полигонов. Хорошее место для начала - алгоритм Вейлера-Атертона. В Википедии есть резюме и ссылки на исходную статью. Алгоритм, похоже, хорошо соответствует описанной вами структуре данных.
Обратите внимание, что вполне возможно, что у вас получится прямоугольник с отверстием в нем (если красный полностью находится внутри черного) или даже два прямоугольника (например, если красный выше и тоньше черного). Если вы уверены, что внутри черного прямоугольника только один угол, решение должно быть намного проще.
Красный прямоугольник может быть где угодно на черном. Однако, если он перекрывается, я просто игнорирую черный прямоугольник, так как он имеет более низкий приоритет.
Похоже, именно то, что мне действительно нужно.
Я нашел здесь кое-что, что могу использовать:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html
На самом деле я загрузил исходный код CGAL еще до того, как опубликовал этот вопрос, но я думаю, что посмотрю на него поближе.
Использование CGAL для этого похоже на охоту на воробьев с пушками.
Насколько точны координаты? Если прямоугольники довольно маленькие, проще всего нарисовать их на холсте, сначала черный прямоугольник, а затем красный. Оставшиеся черные пиксели на холсте - это оставшийся многоугольник.
Другой подход - разделить координатную сетку на группу прямоугольников на основе всех сторон прямоугольников (не считая неограниченных прямоугольников, у вас может быть сгенерировано до 9 прямоугольников, если у вас есть два исходных прямоугольника). Затем просто проверьте репрезентативную точку каждого из этих прямоугольников на принадлежность к конкретным многоугольникам, чтобы определить, какие прямоугольники находятся внутри, а какие нет.
+1 за подход разбивки на 9 частей. Это самый простой и быстрый ..
Просто поясняющее примечание: «Нарисовать их на холсте» можно двумя способами: либо на холсте из графического API, либо на простом двухмерном массиве.
Всегда ли многоугольники выровнены по оси, как показано?