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

Question

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

Answer 1

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

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

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

Обновление

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

Answer 2

Площадь (R1 объединение R2) = Площадь (R1) + Площадь (R2) - Площадь (пересечение 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?) </p>

Answer 3

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