Calculation of the area of ​​intersection of circles by the Monte Carlo method

Monte-Carlo This article was born as a logical continuation of Friday's post about the Bootstrap method , and especially the comments on it. Without defending the Bootstrap method, it is worth paying attention to Monte Carlo methods. Here I want to share my experience with Monte Carlo in one of my practical tasks, as well as the rationale for the legitimacy of this application.

So, my task was to calculate the area of ​​the figure, which is the intersection of circles, with subsequent implementation in JavaScript. The area under the graph is the integral. Integration by the Monte Carlo method is widely known, but, as many rightly note, its application requires some justification. I ask for details under cat.


Justification


The task of calculating the intersection area of ​​two circles is a trivial geometric problem (we know the coordinates of the centers of circles and their radii). The intersection area of ​​two circles is the sum of the areas of the corresponding segments of these circles. There are solutions for calculating the intersection area of ​​two, three, four circles in various special cases.

But the solutions of the general case for the intersection of even three circles are far from so trivial. In the search process, I even found research on calculating the intersection area of ​​N circles However, they are just as interesting as they are complex.

Here the Monte Carlo method comes onto the scene . Thanks to modern computer facilities, this method allows for a large number of statistical tests, based on the results of which a generalization is made.

So, the algorithm for calculating the area of ​​any figure using the Monte Carlo method is as follows:
  1. The figure fits into a rectangle. The coordinates of the sides of the rectangle are known, which means that its area is known.
  2. In a pseudo-random way, a large number of points are generated inside the rectangle. For each point, it is determined whether the point fell inside the original shape or not.
  3. As a result, the area of ​​the original figure is calculated on the basis of the usual proportion: the ratio of the number of points that fell into the figure to the total number of generated points is equal to the ratio of the area of ​​the figure to the area of ​​its bounding rectangle.

The last problem that needs to be solved is that somehow it is necessary to determine whether the point has fallen inside the original shape. In my case, this problem is solved quite simply, because my figure consists of circles, the coordinates of the centers and radii of which are known.

JavaScript task implementation


Circle drawing was done using the wonderful D3.js library . The algorithm for the initial mutual arrangement of circles is beyond the scope of this article; therefore, we will take the initial arrangement as a given.
We collect an array of intersections of pairs of circles
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});
        }
    });
});


We consider the area of ​​the figure
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;
      }
};


Результат

A pair of nails in the bootstrap method


If we talk specifically about the Bootstrap method, then my personal opinion is that the random generation of a dataset from an existing dataset in the general case cannot serve to evaluate regularities, since the generated information is not reliable. In general, the same, only with more intelligent (and often harsher) words, say many authors, for example, Orlov in his textbook on Econometrics .

Conclusion


Monte Carlo methods are quite viable and very useful in some cases, as, for example, in mine. The capabilities of modern computers, even ordinary desktop machines, make it possible to operate with similar statistical methods with a sufficiently large number of tests and, accordingly, obtain sufficient accuracy of the result. But with all this, of course, they are only a simplification of the model and cannot claim to be anything more.