площадь пересечения или объединения (4 видео)

Содержание

Расчет площади пересечения окружностей методом Монте-Карло
Обоснование
Реализация задачи на JavaScript
Пара гвоздей в метод Бутстрапа
Площадь пересечения или объединения
Пример
Общей площадью пересекающихся кругов
13 ответов
🎦 Видео

Видео:Пересечение множеств. Объединение множеств. 5 класс.Скачать

Расчет площади пересечения окружностей методом Монте-Карло

Эта статья родилась как логическое продолжение пятничного поста о методе Бутстрапа, а особенно, комментариев к нему. Не защищая метод Бутстрапа, стоит уделить внимание методам Монте-Карло. Здесь я хочу поделиться своим опытом применения Монте-Карло в одной из своих практических задач, а также обоснованием законности этого применения.

Итак, моя задача заключалась в необходимости вычисления площади фигуры, являющейся пересечением окружностей, с последующей реализацией на языке JavaScript. Площадь под графиком – это интеграл. Интегрирование методом Монте-Карло достаточно широко известно, но, как многие верно заметят, его применение требует некоторого обоснования. За подробностями прошу под кат.

Обоснование

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

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

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

Итак, алгоритм расчета площади любой фигуры методом Монте-Карло сводится к следующему:

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

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

Реализация задачи на JavaScript

Пара гвоздей в метод Бутстрапа

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

Видео:Пересечение и объединение множествСкачать

Площадь пересечения или объединения

Позволяет рассчитать площадь пересечения двух окружностей произвольных радиусов.

Используются достаточно простые формулы, которые элементарно доказываются.

Дополнительно есть калькулятор, который высчитывает координаты пересечения двух окружностей

Площадь пересечения двух окружностей состоит из двух сегментов FDG и FBG

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

Формулы сектора окружности

и длина хорды окружности

По известным сторонам треугольника AFС определяем высоту на сторону AC.

Удвоением этой высоты мы получаем длину хорды, после этого узнаем угол альфа по второй формуле.

По известным сторонам треугольника AFG узнаем его площадь. Вычитаем её из площади сектора окружности, ведь угол альфа нам уже известен.

И получаем площадь сегмента FBG

Подобным образом вычисляем FDG

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

— радиус первой окружности

— радиус второй окружности

— расстояние между центрами окружностей

Видео:Пересечение и объединение множеств. Алгебра, 8 классСкачать

Пример

Хотим узнать площадь пересечения двух окружностей радиусом в 1 и расстоянием между центрами 0.8079455

Пишем okr 1 1 0.8079455

Площадь двух пересекающихся окружностей равна = 1.5707963388681

Первая окружность радиус 4, вторая окружность радиус 2, расстоянием между центрами 3

Пишем okr 4 2 3

Площадь двух пересекающихся окружностей равна = 9.5701994729833

Первая окружность радиус 4, вторая окружность радиус 2, расстоянием между центрами 0

Видео:Объединение и пересечение числовых промежутков. 6 класс.Скачать

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

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

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

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

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

Видео:Видеоурок ПЕРЕСЕЧЕНИЕ И ОБЪЕДИНЕНИЕ МНОЖЕСТВСкачать

13 ответов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pbourke / геометрия / circlearea/).

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

выберите 2 круга (назовите их A и B) и вычислите общую площадь, используя следующую формулу:

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

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

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

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

здесь 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 отвечает. Еще одна ссылка для трех кругов -теорема Харуки. Там тоже есть бумага.

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

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

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

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

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

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

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

реализация много проще. Вышеуказанная проблема может быть решена менее чем 100 строк кода как это решение JSFiddle демонстрирует (в основном потому, что это концептуально намного проще и не имеет крайних случаев или исключений).
Он легко адаптируется к более общим проблемам. Он работает с любая форма, независимо от морфологии, до тех пор, пока она визуализируется с помощью библиотек 2D-чертежей (т. е. «все они!»)- круги, эллипсы, сплайны, полигоны, вы называете это. Черт, даже растровые изображения.
сложность решения для рисования пикселей составляет

O[n] по сравнению с

O[n*n] для математического решения. Это означает, что он будет работать лучше, как количество фигур увеличивается.

и говоря о производительности, вы часто будете получать аппаратное ускорение бесплатно, как и большинство современные 2D-библиотеки (например, холст HTML5, я считаю) будут загружать работу рендеринга в графические ускорители.

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