Как найти общюю площадь n окружностей (Python3.1)

Модификация метода полос для дуг окружностей

Для всех пар окружностей, если окружности пересекаются, запомним y-координаты точек пересечения.

Для всех окружностей отыщем их верхнюю и нижнюю точки и добавим их y-координаты в предыдущий массив.

Из массива окружностей составим массив левых и правых полуокружностей (дуг).

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

Дуга или пересекает полосу целиком или не пересекается с ней вовсе. Оставим только дуги, пересекающие полосу. Каждая такая дуга пересекается с прямой y = (y_i + y_i+1) / 2 в одной точке и все эти точки различны. Отсортируем дуги по x-координатам точек пересечения.

Положим счётчик равным нулю. Перебирём дуги. Для левых дуг увеличиваем счётчик на единицу, для правых уменьшаем. Из всех дуг оставим только левые, перед которыми счётчик был нулевым и правые, после которых счётчик стал нулевым. Остальные дуги убираем.

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

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

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

Сложность алгоритма в худшем случае N³logN. В худшем случае получится N² полос. Обработка одной полосы требует NlogN операций (сортировка).

Думаю что до тысячи попарно пересекающихся окружностей обработать можно. Если окружности (почти) не пересекаются, то сложность упадет до N²logN.

Оптимальный алгоритм ещё примерно на порядок N быстрее. Но там сложно, а этот можно собрать из относительно простых шагов.