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

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

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

Обоснование

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

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

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

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

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

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

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

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

Собираем массив пересечений пар окружностей

var nodes = d3.selectAll("circle.node");

var squares = [];
var intersections = [];

nodes.each(function(node){
   // считаем радиус и площадь окружности
   var r = this.r.baseVal.value;
   var s = 3.14159*r*r;
   squares.push({node: node, square: s, r: r});

   // ищем пересечения пар окружностей
    nodes.each(function(node2){
        // расстояние между центрами и сумма радиусов
        var center_dist = Math.sqrt(Math.pow(node.x-node2.x, 2)+(Math.pow(node.y-node2.y, 2)));
        var radius_sum = r + this.r.baseVal.value;
        if(center_dist <= radius_sum && node.index != node2.index){
            // окружности пересекаются. проверить, что это пересечение найдено впервые
            node.r = r;
            node2.r = this.r.baseVal.value;
            if(isNewIntersection(intersections, node, node2)) 
                  intersections.push({node1: node, node2: node2, center_dist: center_dist});
        }
    });
});

Считаем площадь фигуры

var areaCalculator = {
  intersections: [], // массив пересечений, устанавливается снаружи
  frame: {}, // рамка вокруг фигуры
  circles: [], // массив окружностей
  figureArea: 0, // искомая площадь фигуры
  monteCarlo:
      function(p){
          // получаем массив окружностей из пересечения
          var circles = [];
          var x1_, y1_, x2_, y2_; // координаты сторон прямоугольника
          var inCirclesArr = function(node){
              for(var j=0; j<circles.length; j++){
                  if(circles[j].index==node.index){
                      return true;
                  }
              }
              return false;
          };
          for(var i=0; i<this.intersections.length; i++){
              if(!inCirclesArr(this.intersections[i].node1)){
                  circles.push(this.intersections[i].node1);
              }
              if(!inCirclesArr(this.intersections[i].node2)){
                  circles.push(this.intersections[i].node2);
              }
          }

          this.circles = circles;

          circles.sort(function(a,b){
              return a.x-a.r > b.x-b.r ? 1 : -1;
          });
          x1_ = circles[0].x-circles[0].r;

          circles.sort(function(a,b){
              return a.x+a.r < b.x+b.r ? 1 : -1;
          });
          x2_ = circles[0].x+circles[0].r;

          circles.sort(function(a,b){
              return a.y-a.r > b.y-b.r ? 1 : -1;
          });
          y1_ = circles[0].y-circles[0].r;

          circles.sort(function(a,b){
              return a.y+a.r < b.y+b.r ? 1 : -1;
          });
          y2_ = circles[0].y+circles[0].r;

          this.frame.x1 = x1_;
          this.frame.x2 = x2_;
          this.frame.y1 = y1_;
          this.frame.y2 = y2_;
          this.frame.area = (x2_-x1_)*(y2_-y1_);
          
          // рисуем прямоугольник
          paintRect(this.frame);          

          // p - количество генерируемых точек. В примере использовалось 100.000, чего хватило для приемлемой точности
          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++;
                  }
              }
          }

          // площадь фигуры = площадь прямоугольника*кол-во точек внутри фигуры / общее кол-во точек
          this.figureArea = this.frame.area*p_positive/p;
      }
};

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

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

Заключение

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