Площадь Союза из n кругов (код MATLAB)

Question

Я пытаюсь рассчитать площадь объединения n окружностей в плоскости, когда известно, что все круги имеют одинаковые радиусы и их центры также известны (из всех n кругов). Я пытался следовать методу теории множеств (принцип исключения включения), где мы знаем формулу объединения n множеств. Я просто использовал оператор Ar(), который дает область, т. Е. Ar (A) дает мне площадь A. Сначала я попытался выяснить, с какой окружностью пересекается другой круг (ы) с помощью D < 2R (D = расстояние между центрами двух окружностей), тогда I пытался вычислить площадь пересечения между ними попарно и, следовательно, найти область объединения. Но я застрял за n> 4. Может ли кто-нибудь предоставить soln к этому (необходим soln методом теории множеств). Заранее спасибо

Answer 1

Если ваша проблема была только для пар кругов, вы будете использовать известный результат о Circle-Circle intersection areas. Здесь дается формула для попарной области между любыми двумя кругами, основанная на стандартной параметризации всех задействованных кругов. Но по мере того, как n становится большим, формулы для этих областей не известны. Может быть умный способ использовать рекурсию для вычисления формул для пересечения двух окружностей (n=2), пересечения двух асимметричных форм линз (n=3), пересечение двух экземпляров любой формы - это пересечение двух асимметричных форм линз (n=4), и так далее. Если вы можете получить формулы для этих областей, вы всегда можете использовать inclusion-exclusion для определения пересечения. Ключевым понятием является то, что пересечение n экземпляров предыдущей формы действительно является пересечением n-1 экземпляров пересечений предыдущей формы. Но, как сказал выше комментатор, этот вопрос действительно принадлежит Math Overflow.

Практическая Помимо

Для тех, кто читает, кто интересуется практическим способом решения этой проблемы, интеграция Монте-Карло является отличным выбором. Все, что вам нужно сделать, это вычислить большой прямоугольник, который ограничивает все круги, а затем равномерно рисует точки в этом прямоугольнике. Для каждого круга проверьте, находится ли точка внутри или снаружи. Если он когда-либо внутри, то увеличивайте счетчик и выходите из проверки. В конце, доля этого счетчика к общему количеству набранных точек, умноженная на площадь прямоугольника, даст площадь.

Если мы предположим, что для каждого n -wise области пересечения, мы должны сделать n различные O(1) шаги (предполагается, что мы получим аналитическую формулу, мы можем просто заткнуть радиусами и центра обработки данных прямо в, что может быть оптимистичным), то этот аналитический метод по-прежнему O(n^2).

Монте-Карло хуже, O(Mn) где M это количество точек мы извлекли, если мы делаем пессимистическое предположение, что мы должны проверить против всех n кругов для каждой точки. Для умеренного n, в то время как M не должен быть трудноразрешимым, он определенно не будет близок к n. Однако мы получаем дополнительное преимущество, которое наша функция автоматически обобщает на случай смешанных радиусов (для которых общее решение намного сложнее). С точки зрения практиков, аналитическое решение здесь не очень полезно, если круги не пересекаются, а ограничивающий прямоугольник содержит большое количество пустого пространства.