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

Question

Я ищу способ рассчитать общие области, покрытые несколькими перекрывающимися многоугольниками. Многоугольники имеют прямоугольную форму, если это помогает облегчить ситуацию.

Так, например:

 
    BBBBB 
    BBBBB 
AAA---BB 
AAA---BB 
AAAAAA 
AA--AA 
AA--AA 
    LL 
    LL 
    LLLLLL 
    LLLLLL 

Я хотел бы найти общую область покрытия А, В и L, который будет равно: В = 5x4 = 20 + А = 6х5 = 30 + L = 4x2 + 6x2 = 20 = 70 минус перекрывающихся областей: - 10 = 60 (общая площадь, покрытая всех многоугольников)

мне нужно, чтобы иметь возможность удовлетворить для ситуаций, когда 3 или более многоугольников занимают ту же самую область , Есть ли подходящий алгоритм для этого, который может принимать массивы массивов координат x/y в качестве входных данных? (образец исходного кода Java был бы очень желанным).

Answer 1

Классическим способом вычисления такой области является использование алгоритма развертки. Вы можете взглянуть на вопрос Area of overlapping rectangles, чтобы получить описание алгоритма в более простом случае прямоугольников.

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

Answer 2

Другой способ сделать это - вычислить область с использованием контурного интеграла. Пройдите по периметру области и вычислите площадь с помощью теоремы Грина и числовой квадратуры. Очень просто.

Answer 3

Если вы можете представить полигоны как массивы 2D int или bool (A [i] [j] == 1, если ijth слот содержится в многоугольнике, 0 в противном случае), вы можете создать объединение многоугольников на более крупный 2D-ограничивающий массив.

Алгоритм что-то вроде этого:

// get your polygons, each represented by a 2D array as described above 

// create a "bounding" array B that can contain all polygons (watch out for 
// sparsely spaced polygons in which case B could be large) 

// populate B s.t. B[i][j] == 1 if ijth slot is contained in 
// the union of all polygons 

// count all slots in B where B[i][j] == 1 (this will be the "common" area) 

Думая о времени выполнения и требования к пространству: нужно пройти через каждый слот каждого многоугольника. Необходимо пересечь каждый слот ограничивающего массива B. Наихудший случай для пространства - это когда пересечение всех многоугольников пуст (и, возможно, они расположены с небольшим интервалом). Возможно, стоит сначала проверить пустой случай пересечения ... тогда, если пересечение пусто, «общая» область - это просто сумма отдельных областей.