Пересечение над объединением для прямоугольников с различной ориентацией

Question

Мне нужно быстро реализовать алгоритм, чтобы найти пересечение по объединению (IoU) между двумя прямоугольниками с различной ориентацией в 2-мерном пространстве. Я не мог найти учебники или примеры кодов, чтобы научить, как реализовать такой алгоритм.

Может ли кто-нибудь предоставить соответствующие ресурсы?

Answer 1

В качестве альтернативы очень хорошему решению MBo / O'Rourke, вы можете использовать метод стреловидности.

Для удобства предположим, что один из полигонов выровнен по оси. Затем есть два «события», когда линия достигает верхней и нижней сторон выровненного прямоугольника, и четыре события, когда линия достигает вершин другого (в зависимости от ориентации существует 8 возможных перестановок вершин).

Пересечение прямоугольников происходит в пределах вертикальных диапазонов, определяемых этими событиями (выполняется слияние двух наборов событий), и существует до двух шести пересечений, которые необходимо вычислить между наклонными сторонами и горизонтали. Для каждой строки события легко определить интервалы X, охватываемые обоими прямоугольниками, и найти их пересечение или объединение. А области между двумя линиями событий - это трапеции.

Чтобы справиться с прямоугольниками в общем положении, вы можете

• поверните оба многоугольника, чтобы выровнять один из них,

• работа с повернутой системой координат,

• в любом случае выполнить развертку с горизонтальной линией, не перемещая многоугольники; но тогда есть 8 событий вместо 6 и до 8 вычислений пересечений.

Answer 2

Вы можете использовать алгоритм О'Рурка для вычисления пересечения двух выпуклых многоугольников. Код C и Java доступен на странице книги " Вычислительная геометрия в C "

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

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

Чтобы получить площадь объединения, мы можем вычислить (спасибо Ив Даусту за подсказку)

Area(Union) = Area(P) + Area(Q) - Area(Intersection)