Расчет Cornerpoints и Ребра пересекающихся Recangles

Question

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

Принимая во внимание ряд прямоугольников, которые параллельны осям, определяется по формуле: х, у , ширина и высота.

Требуется является cornerpoints из новых форм, определяемый: х, у и 2 соседнего cornerpoints.

Требуется также являются краями, определяемых: 2 cornerpoints и направления(север, восток, юг, запад).

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

Алгоритм не должен быть очень оптимизирован и не является памятью проблемы.

Answer 1

Это можно решить, используя алгоритмы обрезки полигонов; например, предложенные Ватти или Мартинесом. Используя этот метод:

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

Существует, однако, один угловой корпус, если результирующая форма образует отверстие. Это, как правило, прослеживается в обратном направлении, как и все остальные формы:

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

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