javascript - 确定圆使用的网格

Question

我想确定一个(或多个)圆圈占据一个网格单元格的比例。因此，例如，下方左上角的网格单元将具有较小的值 (~0.1)，而中心网格单元 (7,7) 的值为 1，因为它完全被圆圈占据。

目前，我正在使用 canvas.context2d.getImageData 执行此操作，方法是对单元格的内容进行采样以确定存在的内容。这可行，但方式太慢了。这是这个方法:

var boxRadius = 6;
var boxSize = boxRadius * 2 + 1;

var cellWidth = gridWidth / boxSize;
var cellHeight = gridHeight / boxSize;  
var scanInterval = 10;
var scanCount = 10;
  for (var x = viewcenterpoint.x - (gridWidth / 2); x <= viewcenterpoint.x + (gridWidth / 2) -1; x += cellWidth) {        
        for (var y = viewcenterpoint.y - (gridHeight / 2) ; y <= viewcenterpoint.y + (gridHeight / 2) -1; y += cellHeight) {
            var cellthreatlevel = 0.0;

            for (var cellx = x; cellx < x + cellWidth; cellx += scanInterval){
                for (var celly = y; celly < y + cellHeight; celly += scanInterval){
                    var pixeldata = context.getImageData(cellx, celly, 1, 1).data;
                    cellthreatlevel += ((pixeldata[0] + pixeldata[1] + pixeldata[2])/765 * -1) + 1;//255; //grey tone
                    scancount += 1;
               }  
            } 

            cellthreatlevel = cellthreatlevel / scanCount; //mean
        }
    }    

getImageData 调用是问题的根源 - 它太慢了。

鉴于我有一个圆数组，每个圆都有它们的 x、y 和半径，我该如何计算呢？如果可能的话，我希望每个值都是小数部分(0 到 1 之间)。

网格是静态的，但圆圈可以在其中移动。我很乐意对值(value)进行粗略估计，它不需要 100% 准确。

Answer 1

您可以使用蒙特卡罗方法 来获得近似解。这是一种基于概率的方法，您可以在其中生成随机样本以估计某个值。在这种情况下，给定圆心坐标、圆半径和网格单元的边界，可以通过生成K个随机样本(所有包含在网格单元内)，并验证也在圆内的样本的比例。您生成的样本越多，结果就越准确。

请记住:要验证给定样本 P 是否在圆心 C 和半径 R 的圆内，您所要做的就是检查等式 sqrt((Px-Cx)^2 + (Py-Cy)^2) <= R 是否为真