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

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

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

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

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

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


area overlap geometry polygons
person Community    schedule 07.09.2009    source источник
comment
Я должен добавить, что многоугольники не могут полностью перекрываться, некоторые могут стоять отдельно. Есть ли алгоритм, который мог бы удовлетворить это тоже?   -  person    schedule 07.09.2009

Ответы (3)


arrow_upward
2
arrow_downward

Классическим способом вычисления такой площади является использование алгоритма развертки. Вы можете посмотреть вопрос Область перекрытия прямоугольников, чтобы получить описание алгоритма в более простом случае прямоугольников.

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

person Camille    schedule 08.09.2009

arrow_upward
0
arrow_downward

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

person duffymo    schedule 07.09.2009
comment
Проблема с этим подходом в том, что найти периметр не легче, чем найти территорию. - person Camille; 09.09.2009
comment
Внутренние узлы разделяются четырьмя многоугольниками, если все они четырехугольники. Узел периметра разделяется одним, двумя или тремя полигонами. Вы можете определить узлы периметра и начать прогулку в любой момент, перейдя к следующему узлу периметра. Интегрируйте по этому краю, а затем найдите следующий. - person duffymo; 09.09.2009
comment
Я не понимаю, почему внутренние узлы должны разделяться четырьмя полигонами. Возьмем, к примеру, два перекрывающихся прямоугольника (каждый из которых закрывает один угол другого). Вы также должны определить узлы периметра, которые не являются узлами исходных многоугольников. Конечно, вы можете определить границу объединения, но вам все равно придется прибегнуть к некоторому алгоритму развертки для этой задачи, отсюда и мой комментарий. - person Camille; 09.09.2009

arrow_upward
0
arrow_downward

Если вы можете представить полигоны в виде массивов 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. Наихудший случай для пространства - это когда пересечение всех многоугольников пусто (и, возможно, они редко расположены). Возможно, стоит сначала проверить случай пустого пересечения ... тогда, если пересечение пусто, «общая» область представляет собой просто сумму отдельных областей.

person MrDatabase    schedule 07.09.2009