Объединенная область перекрывающихся кругов

Вот алгоритм, который должно быть легко реализовать на практике и который можно настроить для получения сколь угодно малой ошибки:

1. Аппроксимируйте каждый круг правильным многоугольником с центром в той же точке
2. Вычислить многоугольник, который является объединением аппроксимированных окружностей
3. Вычислить площадь объединенного многоугольника

Шаги 2 и 3 могут быть выполнены с использованием стандартных простых алгоритмов вычислительной геометрии.

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

В зависимости от того, какую проблему вы пытаетесь решить, может быть достаточно получить верхнюю и нижнюю границы. Верхняя граница проста, просто сумма всех кругов. Для нижней границы вы можете выбрать один радиус, чтобы ни один из кругов не перекрывался. Чтобы лучше найти самый большой радиус (вплоть до фактического) для каждого круга, чтобы он не перекрывался. Также должно быть довольно тривиально удалить любые полностью перекрывающиеся круги (все такие круги удовлетворяют | P_a - P_b | <= r_a), где P_a - центр круга A, P_b - центр круга B, а r_a - радиус A ), что улучшает как верхнюю, так и нижнюю границу. Вы также можете получить лучшую верхнюю границу, если будете использовать формулу пар для произвольных пар, а не просто сумму всех кругов. Может быть хороший способ выбрать «лучшее»

Если вам нужен дискретный (в отличие от непрерывного) ответ, вы можете сделать что-то похожее на алгоритм рисования пикселей.

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

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

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

Мне нравится подход к случаю двух пересекающихся кругов - вот как я бы использовал небольшую вариацию того же подхода для более сложного примера.

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

Разница в том, что я начинаю со связывания центров (так что есть вершина между центрами кругов, а не между местами их пересечения). Я думаю, это позволяет лучше обобщить.

(на практике , возможно, стоит использовать метод Монте-Карло)

_{(источник: secretGeek.net )}

Я уверен, что есть умный алгоритм, но вот он глупый, чтобы не искать его;

• поместите ограничивающую рамку вокруг кругов;
• генерируйте случайные точки внутри ограничивающего прямоугольника;
• выяснить, находится ли случайная точка внутри одного из кругов;
• вычислить площадь простым сложением и делением (пропорция_ точек_внутри * площадь_ограничивающего_бокса).

Конечно, это глупо, но:

• вы можете получить настолько точный ответ, насколько захотите, просто наберите больше точек;
• он будет работать для любых фигур, для которых вы можете вычислить различие внутри / снаружи;
• он будет красиво распараллеливаться, так что вы можете использовать все свои ядер.

Хм, очень интересная проблема. Мой подход, вероятно, будет примерно таким:

• Разработать способ определения областей пересечения между произвольным количеством кругов, т.е. если у меня есть 3 круга, мне нужно уметь работать узнать, что такое пересечение этих кругов. Метод «Монте-Карло» был бы хорошим способом приблизиться к этому ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
• Устранение любых круги, которые полностью содержатся в другом большом круге (посмотрите на радиус и модуль расстояния между центрами двух кругов), я не считаю обязательным.
• Выберите 2 круга (назовите их A и B) и определите общая площадь по этой формуле:

(это верно для любой формы,

Я нашел эту ссылку, которая может быть полезна. Хотя, похоже, нет однозначного ответа. Google отвечает . Еще одна ссылка для трех окружностей - это теорема Харуки . Там же есть статья.

Для решения, отличного от предыдущего, вы можете произвести оценку с произвольной точностью с помощью квадродерева.

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

Каждая ячейка имеет одно из состояний: пустая, полная, частичная

Алгоритм заключается в «рисовании» круги в дереве квадрантов, начиная с низкого разрешения (например, 4 ячейки помечены как пустые). Каждая ячейка либо:

• внутри хотя бы одного круга, затем пометьте ячейку как полную,
• вне всех кругов, отметьте ячейку как пустую,
• иначе отметьте ячейку как частичную.

Когда это будет сделано , вы можете вычислить оценку площади: полные ячейки дают нижнюю границу, пустые ячейки дают верхнюю границу, частичные ячейки дают максимальную ошибку площади.

Если ошибка слишком велика для вас, вы уточняете частичные ячейки, пока вы не получите нужную точность.

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

I have been working on a problem of simulating overlapping star fields, attempting to estimate the true star counts from the actual disk areas in dense fields, where the larger bright stars can mask fainter ones. I too had hoped to be able to do this by rigorous formal analysis, but was unable to find an algorithm for the task. I solved it by generating the star fields on a blue background as green disks, whose diameter was determined by a probability algorithm. A simple routine can pair them to see if there's an overlap (turning the star pair yellow); then a pixel count of the colours generates the observed area to compare to the theoretical area. This then generates a probability curve for the true counts. Brute force maybe, but it seems to work OK.

_{(source: 2from.com)}

Существуют эффективные решения этой проблемы, используя то, что известно как диаграммы мощности. Это действительно тяжелая математика, хотя и не то, что я хотел бы решить от руки. Для «Легкого» решения посмотрите алгоритмы развертки линии. Основной принцип вот то, что вы разделяете фигуру на полоски, где вычисление области в каждой полосе относительно проста.

Итак, на рисунке, содержащем все круги, с тем, что ничто не протер, нарисуйте горизонтальную линию в каждом положении, которая либо на верхней части круга, нижней части круга или пересечения 2 кругов. Обратите внимание, что внутри этих полос все районы, которые вам нужно рассчитать, выглядит так же: «трапеция» с двумя сторонами заменена круговыми сегментами. Поэтому, если вы можете отработать, как рассчитать такую ​​форму, вы просто делаете это для всех индивидуальных форм и добавляете их вместе. Сложность этого наивного подхода - это o (n ^ 3), где n - количество кругов на рисунке. Благодаря некоторой умной структуре данных, вы можете улучшить этот метод развертки линии для O (N ^ 2 * log (n)), но если вам действительно не нужно, это, вероятно, не стоит проблем.