Как рассчитать общую площадь, покрытую перекрывающимися кругами в Java

Question

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

Скажем, у меня есть List из Circle с, у каждого Circle есть поляdouble longitude, double latitude и double radius.

List<Circles> circles;

class Circle {
    double longitude;
    double latitude;
    double radius;
}

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

Я хочу вычислитьобщая объединенная площадь этих Circle с (с учетом их перекрытия, конечно). Какой будет хороший алгоритм (или библиотечная функция, если она существует) для этой цели?

Answer 1

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

Make each circle its own cluster
Repeat (until convergence):
  For each cluster:
     For each other cluster:
        Merge clusters if any of their circles overlap

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

Наконец,Вы суммируете все кластеры.