Область пересечения двух вращающихся прямоугольников

У меня есть два двумерных прямоугольника, определяемых как origin (x, y) a размер (высота, ширина) и угол поворота (0-360 °). Я могу гарантировать, что оба прямоугольника имеют одинаковый размер.

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

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

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

Я пишу эту программу в Objective-C в фреймворке Cocoa, для чего это стоит, поэтому, если кто-нибудь знает какие-либо ярлыки с помощью NSBezierPath или что-то, что вы также можете предложить, тоже.

Ответ 1

Простым алгоритмом, который даст приблизительный ответ, является выборка.

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

Ответ 2

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

Вы можете начать с статьи в Википедии по теме и провести там расследование.

Ответ 3

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

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

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

Ответ 4

Фактически вы можете вычислить точную область.

Сделайте один многоугольник из двух прямоугольников. См. этот вопрос (особенно этот ответ) или используйте gpc.
Найдите область этого многоугольника. См. здесь.

Общая область

area of rectangle 1 + area of rectangle 2 - area of aggregated polygon

Ответ 5

Возьмите каждый отрезок линии каждого прямоугольника и посмотрите, пересекаются ли они. Будет несколько возможностей:

Если ни одна из них не пересекается - общая область равна нулю - если все точки одного не находятся внутри другого. В этом случае общая область - это область меньшего размера.
a Если два последовательных ребра одного прямоугольника пересекаются с одним ребром другого прямоугольника, это образует треугольник. Вычислите его площадь.

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

@edit: у меня есть более общее решение.

Проверьте специальный случай в 1.

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

Ответ 6

Метод грубой силы:

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