Площадь пересечения n окружностей, каждая из которых имеет радиус 'r'

Question

Пробное утверждение: 'N' равных радиусов окружностей нанесены на график от (-) бесконечности до (+) бесконечности. Найдите общую площадь пересечения I.e всю область на графике, которая покрыта двумя или более кругами.

Answer 1

Во-первых, исправление: это не круги. Это эллипсы (круги являются частным случаем эллипсов, где a = b). Вы можете вычислить пересечение двух эллипсов, так что, учитывая N эллипсов, вам нужно проверить каждую пару, чтобы вся операция была O (n ² ) (умноженная на любую операцию пересечения).

Взгляните на Пересечение эллипсов и Площадь пересекающихся эллипсов .

Редактировать: пересечение окружностей является более простой проблемой, но следует тому же принципу. Взгляните на пересечение двух кругов и пересечение круг-круг .

Answer 2

Самый простой (не обязательно самый быстрый или "лучший") способ написания кода - найти ограничивающий прямоугольник, содержащий все круги, а затем использовать числовой стохастический метод для интегрирования.

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

Но чистый стохастический метод имеет красоту простоты реализации (но потенциально медленного).

Это приемлемо только в том случае, если вы рады получить «приблизительный» (но сколь угодно близкий к правильному) ответ.