Pull to refresh

Comments 18

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

Расчет площади фигуры разными способами

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



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

Тогда методу Монте-Карло нет альтернатив.
Поддерживаю. Я бы в него что-нибудь запостил со стыка прикладной статистики и программирования, что в существующие хабы не укладывается.
Не ручаюсь за результат, так как тестов не проводил, но, возможно, стоит рассмотреть вариант с созданием вспомогательного <canvas>, в котором бы рисовались точно такие же окружности, а дальше просто считалось количество непрозрачных пикселей?

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

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

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

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


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

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

Articles