Булевы операции над прямоугольными полигонами

Question

Аваст там, товарищи программисты!

У меня следующая проблема:

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

Я хочу выяснить, многоугольник, состоящий из точки ABCDEF.

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

Каждый прямоугольник представляет собой структуру данных с 4 2d-вершинами.

Каков наилучший алгоритм для достижения этой цели?

Answer 1

Это особый случай общего двухмерного отсечения полигонов. Хорошее место для начала - алгоритм Вейлера-Атертона. В Википедии есть резюме и ссылки на оригинальную статью . Кажется, что алгоритм соответствует структуре данных, которую вы описали, очень хорошо.

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

Answer 2

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

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

Answer 3

конструктивная геометрия твердого тела

Answer 4

Я нашел здесь кое-что, что мог бы использовать:

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

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