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

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

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

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

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

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

Источник

6 ответов

Решение

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

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

Источник

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

Вы могли бы начать со статьи в Википедии на эту тему, а затем заняться расследованиями.

Источник

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

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

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

Источник

Вы можете вычислить точную площадь.

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

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

    area of rectangle 1 + area of rectangle 2 - area of aggregated polygon
Источник

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

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

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

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

  3. Если два ребра одного пересекаются с двумя ребрами другого, то у вас будет четырехугольник. Вычислить как в 2b.

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

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

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

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

Источник

Путь грубой силы:

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

,

Источник
Другие вопросы по тегам