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

Question

Недавно я столкнулся с проблемой, когда у меня было четыре круга (середина и радиус), и мне пришлось вычислить площадь объединения этих кругов.

Пример изображения:

Для двух кругов это довольно легко,

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

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

Answer 1

Найти все пересечения окружностей по внешнему периметру (например, B, D, F, H на следующей диаграмме). Соедините их вместе с центрами соответствующих кругов, чтобы сформировать многоугольник. Площадь объединения окружностей - это площадь многоугольника + площадь срезов круга, определяемая последовательными точками пересечения, и центр круга между ними. Вам также нужно будет учитывать любые отверстия.

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

alt text http://secretGeek.net/image/triangles_1667310.png

Answer 5

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

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

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

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

Где A ∪ B означает соединение B и A ∩ B означает пересекаться B (вы можете решить эту проблему с первого шага.

• Теперь продолжайте добавлять круги и продолжать работать вне а, rea добавляется как сумма/вычитание областей кругов и областей пересечений между кругами. Например, для 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 этих кругов, которые могут быть рассчитаны точно (нет идеи как это сделать, однако).

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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

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

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

Answer 8

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

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

Answer 9

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

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

шаги 2 и 3 могут быть осуществлен с помощью Standar d, легко найти алгоритмы из вычислительной геометрии.

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

Answer 10

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

Answer 11

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

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

Answer 12

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

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

Единственным недостатком для рисования пикселей является конечная точность решения. Но это настраивается путем простого рендеринга на большие или мелкие полотна, как того требует ситуация. Обратите также внимание на то, что anti-aliasing в коде 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); 

Answer 13

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

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

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

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