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

Question

Что такое алгоритм определения общей площади двух прямоугольников, которые пересекаются и могут поворачиваться с осевых координат?

Answer 1

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

• Отработать класс пересечения. То есть Сколько ребер имеет область пересечения? Это может быть любое значение от 0 до 8.
• Найти все вершины пересечения. Это будут все пересечения между краями прямоугольников и соответствующие углы самих прямоугольников. Работа с этим битом является самой сложной/утомительной.
• Определите площадь пересечения, разделив его на треугольники, если это необходимо.

Вот все способы прямоугольники могут пересекаться:

Update

У меня были кое-какие мысли, и лучший способ классифицировать пересечение проследить вокруг периметра каждый прямоугольник и подсчитывать количество раз, когда каждое ребро пересекает другое ребро. Вы получите вектор, например. для шестисторонней зоны пересечения: {1,1,1,1}, {0,1,1,1} и для 8: {2,2,2,2}, {2,2,2,2} , Два специальных случая, которые вам нужно проверить, - это когда один прямоугольник полностью перекрывает другой и когда края находятся в очереди. Вам понадобятся тщательные проверки, но это будет отправной точкой для функции, чтобы классифицировать пересечение.

Answer 2

Хорошо, у вас есть 3 возможности: 1. Прямоугольники не пересекаются 2. Один прямоугольник полностью находится внутри другого (или они совпадают) 3. В результате пересечения некоторый выпуклый многоугольник. Вы вычисляете область многоугольника, разбивая ее на треугольники (путем отрисовки сегментов от первой вершины к каждой другой, за исключением смежных один раз). Вы суммируете области. Вы можете использовать теорему Геродота, чтобы вычислить область треугольника, и вот где находится геометрия средней школы.

Answer 3

Площадь (R1 union R2) = Area (R1) + Area (R2) - Area (R1 intersection R2), поэтому вы можете вычислить область пересечения, чтобы иметь площадь союза.

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

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

Так это выглядит следующим образом:

• Ь первоначально пустое связанный список
• R1 имеет ребра e1, e2, e3, e4, R2 имеет ребра f1, f2, f3, f4. Вычислить точки пересечения ei и fj для всех i, j = 1,2,3,4. Добавьте их в список L.
• Для каждой вершины v из R1, если v находится внутри R2, добавьте ее в L.
• Для каждой вершины w R2, если w находится внутри R1, добавьте ее в L.

Выпуклая оболочка точек в L - это ваше пересечение. Поскольку каждая точка в L находится на границе пересечения, вы можете триангулировать ее и вычислить ее площадь. Легко:

• L = [x0, x1, ...]
• Сортировка точек в L в соответствии с углом (XI - х0) по отношению к горизонтальной линии, проходящей через точку х0
• первого треугольника является x0, x1, x2
• Второй треугольник x0, x2, x3
• п-й треугольник х0, х (п + 1), х (п + 2)

площадь треугольника по формуле Heron:

• а, Ь, с длинами ребер
• S = 0,5 * (а + B + C)
• площадь = SQRT (S * (S - а) * (S - B) * (s - с))

но остерегайтесь вычисления s - а, с - Ь и с - Ĉ independantly, так как вы можете столкнуться ошибку округления (что, если с ~ а и б < <, например)

?