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

[lexkazakov]

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

[mynameco]

Чем то напоминает алгоритмы растеризации фигур.

[forewar]

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

Код расчета через сетку

// Генерация сетки с общим количеством ячеек = 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++;
                  }
              }
          }

Спасибо, возьму на заметку.

[SeptiM]

Есть еще много других методов численного интегрирования. Попробуйте прямоугольники.

[dimview]

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

[SeptiM]

А что если дополнительно сдвинуть сетку на маленький рандомный эпсилон?

[dimview]

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

[mynameco]

Есть правда один ньюанс, если методом сетки измерять сетку объектов с сопоставимыми размерами, то результаты будут «интересными»

[lexkazakov]

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

[cptgav]

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

Тогда методу Монте-Карло нет альтернатив.

[shushu]

Я думаю стОит добавить хаб Ненормальное программирование.

[dimview]

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

[Zoberg]

Не ручаюсь за результат, так как тестов не проводил, но, возможно, стоит рассмотреть вариант с созданием вспомогательного <canvas>, в котором бы рисовались точно такие же окружности, а дальше просто считалось количество непрозрачных пикселей?

К вечеру немного туплю, так что может кто подскажет вариант лучше :)

[barkalov]

Это, кстати, по сути то, что предложил lexkazakov — дискретное интегрирование по сетке.
Если сделать такое hardware-способом на видеокарте (WebGL?): нарисовать на 32-битной карте окружности, аккуртатно сдаунскейлить до 1х1 и выкинуть пиксель в CPU — получится адски эффективно.

[naething]

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

Можно и вот так: нетрудно заметить, что пересечение нескольких кругов будет представлять собой фигуру, граница которой будет состоять из кусков окружностей. Прямо как многоугольник, только вместо прямых ребер — дуги. То есть, можно придумать алгоритм, похожий на алгоритм пересечения многоугольников, но по-другому работающий с «ребрами». Затем уже полученную фигуру приблизить многоугольником и вычислить площадь. Точность будет лучше, но и реализация сложнее.

[Mrrl]

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

[dimview]

Есть хороший детский пример, как примерно посчитать пи подручными способами:

1. Берём чистый лист бумаги
2. Просим детей наставить на него N точек в произвольных местах
3. Кладём сверху аккуратными рядами одинаковые монеты так, чтобы они покрывали весь лист
4. Считаем, сколько точек не закрыты монетами (пусть будет K)

Тогда пи примерно равно 4 * (N — K) / N.

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

[mFoxRU]

Таких способов немало