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

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

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

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

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

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

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

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

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

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

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

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

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

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

• синие точки-центры окружностей.
• красные точки-это пересечения границ круга.
• красные точки С белый интерьер являются ли пересечения границ круга не содержится ни в каких других круги.

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

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

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

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

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

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

alt текст http://secretGeek.net/image/triangles_1667310.png

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

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

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

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

(это справедливо для любой формы, будь то круг или иначе)

area(A∪B) = area(A) + area(B) - area(A∩B)

здесь A ∪ B означает союз B и A ∩ B означает пересечение B (вы можете решить это с первого шага.

• теперь продолжайте добавлять круги и продолжайте разрабатывать область, добавленную как сумма / вычитание областей кругов и областей пересечения между кругами. Например, для 3 кругов (назовем дополнительный круг C) мы разрабатываем область, используя эту формулу:

(это то же самое, что и выше, где A есть был заменен на A∪B)

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

здесь area(A∪B) мы только что разобрались, и area((A∪B)∩C) можно найти:

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

где снова вы можете найти область(A∩B∩C) сверху.

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

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

вероятно, есть лучший способ сделать это кстати - сложность значительно возрастает (возможно, экспоненциально, но я не уверен) для каждого добавленного дополнительного круга.

Я работал над проблемой моделирования перекрывающихся звездных полей, пытаясь оценить истинное количество звезд из фактических областей диска в плотных полях, где более крупные яркие звезды могут маскировать более слабые. Я тоже надеялся, что смогу сделать это с помощью строгого формального анализа, но не смог найти алгоритм для этой задачи. Я решил ее, создав Звездные поля на синем фоне в виде зеленых дисков, диаметр которых определялся вероятностным алгоритмом. Простая процедура может соедините их, чтобы увидеть, есть ли перекрытие (превращение звездной пары в желтый); затем количество пикселей цветов генерирует наблюдаемую область для сравнения с теоретической областью. Это затем генерирует кривую вероятности для истинных подсчетов. Грубая сила может быть, но это, кажется, работает нормально.
http://www.2from.com/images/simulated_star_field.gif

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

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

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

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

учитывая верхнюю и нижнюю границу, вы можете лучше настроить подход Монте-Карло, но ничего на ум приходит конкретика. Другой вариант (опять же в зависимости от вашего приложения) заключается в растеризации кругов и подсчете пикселей. Это в основном подход Монте-Карло с фиксированным распределением.

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

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

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

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

подход пиксельной живописи (как предложено @Loadmaster) превосходит математическое решение различными способами:

1. реализация много проще. Вышеуказанная проблема может быть решена менее чем 100 строк кода как это решение JSFiddle демонстрирует (в основном потому, что это концептуально намного проще, и не имеет крайних случаев или исключений для решения).
2. Он легко адаптируется к более общим проблемам. Он работает с любая форма, независимо от морфологии, до тех пор, пока она визуализируется с помощью библиотек 2D-чертежей (т. е. "все из них!")- круги, эллипсы, сплайны, полигоны, вы называете это. Черт, даже растровые изображения.
3. сложность решения пиксельной живописи составляет ~O[n], по сравнению с ~O[n*n] для математического решения. Это означает, что он будет работать лучше, как количество фигур увеличивается.
4. и говоря о производительности, вы часто получаете аппаратное ускорение бесплатно, как и большинство современные 2D-библиотеки (например, холст HTML5, я считаю) разгрузят работу рендеринга для графических ускорителей.

единственным недостатком пиксельной живописи является конечная точность решения. Но это можно настроить, просто переведя на большие или меньшие полотна, как того требует ситуация. Заметьте, тоже что анти-алиасинг в 2D-коде рендеринга (часто включенном по умолчанию) будет получаться точность лучше, чем на уровне пикселей. Так, например, рендеринг фигуры 100х100 в холст тех же размеров должен, я думаю, дать точность порядка 1 / (100 х 100 х 255) = .000039% ... что, вероятно," достаточно хорошо " для всех, кроме самых сложных проблем.

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>

// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);