计算用圆圈重叠的多个方块的面积分数

 

这是一个基于我有编程问题的几何问题。 基本上，我有一个充满经度和纬度点的MySQL数据库，相距1公里，相当于每个点周围居住平方公里的人口。 然后，我想知道每个由任意大小的圆圈占据的每个网格的相对分数，因此我可以计算出在给定圆周内大概有多少人生活。

下面是一个问题形式的实际例子（距离不成比例）：

图

我有兴趣知道居住在X点半径范围内的人群。我的数据库发现它对A点和B点的输入足够接近X点。 这个例子中的点A类似于40.7458，-74.0375，点B类似于40.7458，-74.0292。 从A和B到它的网格边缘的每条绿线代表0.5公里，因此A和B周围的灰色圆圈分别代表1平方公里。

X点位于40.744，-74.032附近，半径（紫色）为0.05公里。

现在我可以使用地理三角函数轻松计算显示的红线。 所以我知道线AX约为.504公里，距离线BX约为.309公里，因为无论对我来说如何。

因此，我的问题是：计算网格A的分数和网格B在X周围刻划的紫色圆圈的比例是多少？

最终，我将采取人口总数，并乘以这一部分。 所以在这种情况下，1平方公里周围的网格对应9561人，而B周围的网格是10763人。 因此，如果我知道（只是假设）围绕X的半径覆盖了A面积的1％和B面积的3％，我可以对覆盖的总人口进行合理的回归估计通过将A和B群体乘以它们各自的分数并且将它们相加来循环。

我只用上面的两个方块来完成它，但取决于半径的大小（可以是任意的），可能会有一大堆可能的方块，就像这样，使它成为一个更普遍的问题：

图1

在某些情况下，很容易发现所讨论的方格是100％被半径包围的，原则上相当容易（例如，如果AX之间的距离小于X周围的半径，我知道我不会没有必要做更多的数学）。

现在，很容易找出哪些点在圆的范围内。 但我有点卡在弄清楚他们相应区域的分数是多少。

感谢您的帮助。

通过足够的分类（下面简图），所有的计算都可以简化为原始计算，即提供图像中描述的橙色区域的角度区域的计算

当y0 > 0 ，如上所示，无论x0是正还是负，橙色区域都可以精确计算为sqrt(r^2 - y^2) x0到x1减去矩形区域(x1 - x0) * (y1 - y0). 该积分具有众所周知的闭合表达式，因此不需要使用任何数值算法来计算它。

圆形和正方形之间的其他交叉点可以缩小为矩形和直角形状的组合，如上面橙色的绘制。 例如，在下面的图片中由水平和垂直橙色射线定界的交叉点可以通过将红色矩形的面积加上两个角形状（蓝色和绿色）相加来表示。

蓝色区域是直接应用上面确定的原始情况（其中下方的矩形折叠为无）。绿色区域也可以以相同的方式测量，一旦负的y坐标被其绝对值替换（另一个y是0 ）。

应用这些想法可以列举所有情况。 基本上，人们应该考虑这样一种情况，即正方形的一个，两个，三个或四个角位于该圆内，而其余的（如果有的话）落在该圆外。 枚举本身就是一个问题，但至少在理论上可以通过考虑相对少量的“典型”配置来解决。

对于上面列举的每种情况，都必须计算一些矩形和角度区域的分解，并按上述三色示例中所示的方式累加（或减去）部分。 每个部分的面积将缩小到矩形或原始角度区域。

为了将这种攻击转化为一种有效的算法，必须做大量的工作。 更深入的分析可以阐明如何最大限度地减少要考虑的“典型”配置的数量。 如果不是，我认为要考虑的组合数量，无论多大，都应该可以控制。

我想最终我想出了一个很好的近似解决方案。 以下是它在PHP中的外观： 

//$p is an array of latitude, longitude, value, and distance from the centerpoint 
//$cx,$cy are the lat/lon of the center point, $cr is the radius of the circle
//$pdist is the distance from each node to its edge (in this case, .5 km, since it is a 1km x 1km grid)

function sum_circle($p, $cx, $cy, $cr, $pdist) {
    $total = 0; //initialize the total
    $hyp = sqrt(($pdist*$pdist)+($pdist*$pdist)); //hypotenuse of distance

    for($i=0; $i<count($p); $i++) { //cycle over all points
        $px = $p[$i][0];    //x value of point
        $py = $p[$i][1];    //y value of point
        $pv = $p[$i][2];    //associated value of point (e.g. population)
        $dist = $p[$i][3];  //calculated distance of point coordinate to centerpoint

        //first, the easy case — items that are well outside the maximum distance
        if($dist>$cr+$hyp) { //if the distance is greater than circle radius plus the hypoteneuse
            $per = 0; //then use 0% of its associated value
        } else if($dist+$hyp<=$cr) { //other easy case - completely inside circle (distance + hypotenuse <= radius)
            $per = 1; //then use 100% of its associated value
        } else { //the edge cases
            $mx = ($cx-$px); $my = ($cy-$py); //calculate the angle of the difference
            $theta = abs(rad2deg(atan2($my,$mx)));
            $theta = abs((($theta + 89) % 90 + 90) % 90 - 89); //reduce it to a positive degree between 0 and 90
            $tf = abs(1-($theta/45)); //this basically makes it so that if the angle is close to 45, it returns 0, 
                                      //if it is close to 0 or 90, it returns 1
            $hyp_adjust = ($hyp*(1-$tf)+($pdist*$tf)); //now we create a mixed value that is weighted by whether the
                                                        //hypotenuse or the distance between cells should be used                                                   

            $per = ($cr-$dist+$hyp_adjust)/100; //lastly, we use the above numbers to estimate what percentage of 
                                                //the square associated with the centerpoint is covered
            if($per>1) $per = 1; //normalize for over 100% or under 0%
            if($per<0) $per = 0; 
        }
        $total+=$per*$pv;   //add the value multiplied by the percentage to the total
    }  
    return $total;
}

这似乎工作，并且非常快（即使它在边缘情况下使用了一些触发器）。 基本逻辑是，在计算边缘情况时，两种极端可能性是圆半径要么完全垂直于网格，要么恰好与其成45度角。 因此，它大致确定了它所处的极端之间的位置，然后用它来大致确定网格平方的百分比。 它在我的测试中给出了合理的结果。

对于我正在使用的正方形和圆形的大小，这似乎足够了？

我在Processing.js中编写了一个小应用程序，试图帮助我解决这个问题。 在不解释所有的情况下，您可以通过查看此屏幕截图来了解算法是如何“思考”的：

我的小例子 基本上，如果圈子是黄色的，这意味着它已经计算出它是100％，如果它是红色，它已经快速筛选为100％。 其他案例是边缘案例。 点之下的数字（范围从0到1）是使用上述方法计算的覆盖率百分比（百分比），而下面的数字是上述代码中使用的计算出的θ值。

为了我的目的，我认为这个近似是可行的。

如果你的问题承认了一个近似的答案，那么你可以使用另一种技术，这对编程来说更简单。 这个问题的整个想法减少到计算一个正方形和一个圆的交点的面积。 我没有在我的其他答案中解释这一点，但找到可能拦截这个圈子的方格应该不成问题，否则，请告诉我们。

计算相交区域的概念非常简单。 随机产生足够的点在方格中，并检查它们中有多少个属于该圆。 圆圈中点的数量与方块中随机点的总数之间的比率将为您提供交点相对于方块面积的比例。

现在，考虑到你必须对圆周围的所有方块重复相同的程序（例如，圆心的距离与圆的中心距离与圆的半径差别不大），你可以重新使用随机点，将它们从一个正方形到另一个。

如果这种方法不适合你的问题，我不想详细说明，所以让我指出生成均匀分布在方块中的随机点相当容易。 您只需要为x坐标生成随机数，并且独立地为y生成随机数。 然后只考虑所有对(x, y) 。 然后，对于每个(x, y)验证是否(x - a)^2 + (y - b)^2 <= r^2 ，其中(a, b)代表圆的中心， r代表半径。

链接地址: http://www.djcxy.com/p/14877.html

上一篇: Calculating the fraction of the area of multiple squares overlapped by a circle

下一篇: methods to avoid fluctuating signal strength in trilateration