Comments 18
Для расчёта площадей метод Монте-Карло мне не нравится по одной железо-ориентированной причине: генерировать псевдослучайные числа — затратно. Куда меньше процессорных затрат уйдёт на генерацию сетки с достаточно мелким разбиением (читай, палетки) и вычисление площади по ней. Причем в таком случае можно гарантировано повышать точность результата путём уменьшения шага разбиения сетки.
+7
Чем то напоминает алгоритмы растеризации фигур.
+2
Должен согласиться с вашим замечанием. Расчет площади по сетке выходит существенно быстрее.
Спасибо, возьму на заметку.
Код расчета через сетку
// Генерация сетки с общим количеством ячеек = p
p_positive = 0;
var gridRow = Math.ceil(Math.sqrt(p));
// Разбить описывающий квадрат на gridRow ячеек по горизонтали и столько же по вертикали
var cellWidth = (x2_ - x1_)/gridRow;
var cellHeight = (y2_ - y1_)/gridRow;
// точку будем ставить в центр каждой ячейки
for (var y_counter=0; y_counter<gridRow; y_counter++) {
var yCur = y1_ + y_counter * cellHeight + cellHeight/2;
for (var x_counter=0; x_counter<gridRow; x_counter++) {
var xCur = x1_ + x_counter * cellWidth + cellWidth/2;
var yes = false;
for(var j=0; j<circles.length; j++) {
if(!yes && (
(circles[j].x-circles[j].r) <= xCur &&
(circles[j].x+circles[j].r) >= xCur &&
(circles[j].y-circles[j].r) <= yCur &&
(circles[j].y+circles[j].r) >= yCur )
){
yes = true;
p_positive++;
}
}
}
}
Код расчета через генерацию рандомных точек
// Генерация точек методом Монте-Карло
var p_positive = 0;
// генерируем p точек для определения площади фигуры
for(var i=0; i<p; i++){
var x_rand = Math.random()*(x2_-x1_)+x1_;
var y_rand = Math.random()*(y2_-y1_)+y1_;
var yes = false;
for(var j=0; j<circles.length; j++) {
if(!yes && (
(circles[j].x-circles[j].r) <= x_rand &&
(circles[j].x+circles[j].r) >= x_rand &&
(circles[j].y-circles[j].r) <= y_rand &&
(circles[j].y+circles[j].r) >= y_rand )
){
yes = true;
p_positive++;
}
}
}
Спасибо, возьму на заметку.
+2
Есть еще много других методов численного интегрирования. Попробуйте прямоугольники.
0
Гарантировать повышение точности результата путём уменьшения шага разбиения сетки я бы побоялся. Если у фигур есть повторяющиеся куски с периодом, кратным к шагу сетки, можно встретить интересные эффекты вроде муара.
+1
Есть правда один ньюанс, если методом сетки измерять сетку объектов с сопоставимыми размерами, то результаты будут «интересными»
+1
Согласен, но выкрутиться тоже можно. Шаг сетки можно либо уменьшить (или сильно уменьшить, если на это хватит вычислительных ресурсов) или можно сдвинуть сетку на маленький эпсилон и сравнить.
Метод Монте-Карло тоже может не лучшим образом показать себя в подобной ситуации. «Подобной» — я имею в виду с таким же количеством псевдослучайных точек, сколько будет в равномерной сетке.
Метод Монте-Карло тоже может не лучшим образом показать себя в подобной ситуации. «Подобной» — я имею в виду с таким же количеством псевдослучайных точек, сколько будет в равномерной сетке.
0
в многомерных пространствах есть небольшие проблемы с числом узлов подобной сетки.
Тогда методу Монте-Карло нет альтернатив.
Тогда методу Монте-Карло нет альтернатив.
0
Я думаю стОит добавить хаб Ненормальное программирование.
+3
Не ручаюсь за результат, так как тестов не проводил, но, возможно, стоит рассмотреть вариант с созданием вспомогательного
К вечеру немного туплю, так что может кто подскажет вариант лучше :)
<canvas>
, в котором бы рисовались точно такие же окружности, а дальше просто считалось количество непрозрачных пикселей?К вечеру немного туплю, так что может кто подскажет вариант лучше :)
+2
Это, кстати, по сути то, что предложил lexkazakov — дискретное интегрирование по сетке.
Если сделать такое hardware-способом на видеокарте (WebGL?): нарисовать на 32-битной карте окружности, аккуртатно сдаунскейлить до 1х1 и выкинуть пиксель в CPU — получится адски эффективно.
Если сделать такое hardware-способом на видеокарте (WebGL?): нарисовать на 32-битной карте окружности, аккуртатно сдаунскейлить до 1х1 и выкинуть пиксель в CPU — получится адски эффективно.
+1
Можно, например, с хорошей точностью приблизить каждую окружность выпуклым многоугольником и применить готовый алгоритм пересечения выпуклых многоугольников. Надо только заметить, что пересечение двух выпуклых многоугольников — снова выпуклый многоугольник.
Можно и вот так: нетрудно заметить, что пересечение нескольких кругов будет представлять собой фигуру, граница которой будет состоять из кусков окружностей. Прямо как многоугольник, только вместо прямых ребер — дуги. То есть, можно придумать алгоритм, похожий на алгоритм пересечения многоугольников, но по-другому работающий с «ребрами». Затем уже полученную фигуру приблизить многоугольником и вычислить площадь. Точность будет лучше, но и реализация сложнее.
Можно и вот так: нетрудно заметить, что пересечение нескольких кругов будет представлять собой фигуру, граница которой будет состоять из кусков окружностей. Прямо как многоугольник, только вместо прямых ребер — дуги. То есть, можно придумать алгоритм, похожий на алгоритм пересечения многоугольников, но по-другому работающий с «ребрами». Затем уже полученную фигуру приблизить многоугольником и вычислить площадь. Точность будет лучше, но и реализация сложнее.
0
Точное вычисление площади (как пересечения, так и объединения) — занимает меньше 70 строк на C#. Правда, алгоритм не очень устойчив в случае очень близких окружностей.
Основная идея — находим все точки пересечения каждой окружности с остальными, рассматриваем все дуги, проверяем, лежит ли дуга на границе фигуры (для этого можно взять любую точку на дуге, и проверить, лежат ли они внутри или вне остальных кругов), и если лежит — то добавляем площадь криволинейного треугольника с вершиной в начале координат, опирающегося на эту дугу, к общей площади.
Основная идея — находим все точки пересечения каждой окружности с остальными, рассматриваем все дуги, проверяем, лежит ли дуга на границе фигуры (для этого можно взять любую точку на дуге, и проверить, лежат ли они внутри или вне остальных кругов), и если лежит — то добавляем площадь криволинейного треугольника с вершиной в начале координат, опирающегося на эту дугу, к общей площади.
+3
Есть хороший детский пример, как примерно посчитать пи подручными способами:
Тогда пи примерно равно 4 * (N — K) / N.
Если копилки под рукой нет, можно бросать иголку на дощатый мол и считать, сколько раз она окажется полностью на одной доске.
- Берём чистый лист бумаги
- Просим детей наставить на него N точек в произвольных местах
- Кладём сверху аккуратными рядами одинаковые монеты так, чтобы они покрывали весь лист
- Считаем, сколько точек не закрыты монетами (пусть будет K)
Тогда пи примерно равно 4 * (N — K) / N.
Если копилки под рукой нет, можно бросать иголку на дощатый мол и считать, сколько раз она окажется полностью на одной доске.
0
Sign up to leave a comment.
Расчет площади пересечения окружностей методом Монте-Карло