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

Ответ 1

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

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

Здесь все пути, которыми могут пересекаться прямоугольники:

Обновление

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

Ответ 2

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

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

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

Итак, это выглядит так:

• L является первоначально пустым связанным списком
• 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 - x0) относительно горизонтальной линии, проходящей через x0
• Первый треугольник: x0, x1, x2
• Второй треугольник: x0, x2, x3
• n-й треугольник равен x0, x (n + 1), x (n + 2)

Площадь треугольника определяется формулой Херона:

• a, b, c - длины ребер
• s = 0.5 * (a + b + c)
• area = sqrt (s * (s - a) * (s - b) * (s - c))

но будьте осторожны при вычислении s - a, s - b и s - c независимо, так как вы можете столкнуться с ошибкой округления (что, если c ~ a и b < a, например?)

Ответ 3

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