Если ваша задача была только для пар окружностей, вы будете использовать известный результат о областях пересечения окружности-круга .Здесь дается формула для парной области между любыми двумя окружностями, основанная на стандартной параметризации всех задействованных окружностей.Но когда n становится большим, формулы для этих областей широко не известны.Там может быть умный способ использовать рекурсию для вычисления формул для пересечения двух окружностей (n=2), пересечение двух асимметричных форм линз (n=3), пересечение двух экземпляров любой формы является пересечениемдве асимметричные формы линз (n=4) и т. д.Если вы можете получить формулы для этих областей, вы всегда можете использовать включение-исключение , чтобы выяснить пересечение.Ключевым моментом является то, что пересечение n экземпляров предыдущей фигуры действительно является пересечением n-1 экземпляров пересечений предыдущей фигуры.Но, как сказал вышеупомянутый комментатор, этот вопрос действительно принадлежит Math Overflow.
Практическое пособие
Для тех, кто читает, кто интересуется практическим способом решения этой проблемыИнтеграция Монте-Карло - отличный выбор.Все, что вам нужно сделать, это вычислить большой прямоугольник, который ограничивает все круги, а затем равномерно нарисовать точки в этом прямоугольнике.Для каждого круга проверьте, находится ли точка внутри или снаружи.Если это когда-либо внутри, тогда увеличьте счетчик и прекратите делать больше проверок.В конце пропорция этого счетчика к общему количеству нарисованных точек, умноженному на площадь прямоугольника, даст площадь.
Если мы предположим, что для каждой n -положительной области пересечения нам понадобитсячтобы сделать n различных O(1) шагов (при условии, что мы получим аналитическую формулу, в которую мы можем просто вставить радиусы и центральные данные прямо, что может быть оптимистичным), тогда этот аналитический метод все еще O(n^2).
Монте-Карло хуже, O(Mn), где M - это количество точек, которые мы рисуем, если мы сделаем пессимистическое предположение, что мы должны проверять все круги n для каждой точки.Для умеренных n, хотя M не обязательно должно быть слишком большим, оно определенно не будет близко к n.Однако мы получаем дополнительное преимущество, которое наша функция автоматически обобщает на случай смешанных радиусов (для которых общее решение намного сложнее).С точки зрения практикующего врача, аналитическое решение здесь не очень полезно, если только круги почти не перекрываются, а ограничивающий прямоугольник содержит большое количество пустого пространства.