algorithm - 计算三角形内的格点

Question

我有一个大三角形的点，我们称它为 a、b、c。 (a = (x, y) 等等)。

现在我想统计这个三角形围成的区域内的积分点的个数，所以先看匹克定理。我考虑的第二种方法是生成以三角形的最大值、最小值为界的点列表，然后检查每个点是否位于三角形内。

我使用重心坐标方法来完成此操作。它有效，但我的三角形非常大，我的程序基本上是跨点的蛮力。我该如何改进这个算法？

我的代码可以在这里找到:https://bpaste.net/show/58433b6e389c

Answer 1

这个问题可以而且应该使用 Pick's theorem 来解决。 .阅读本文以全面了解它的工作原理，它适用于您能想到的任何多边形。因此，“Pick 说”如果您想计算多边形的面积，您可以使用公式 area = noOfInsidePoints + noOfBoundaryPoints/2 - 1。要计算任何多边形的面积，您可以使用以下代码，其中 pc 是表示多边形顶点的结构数组。

float computeArea()
{
    float area = 0;
    for(int i=1;i<=n;++i) // n is the total number of vertices
        area += (pc[i].x*pc[i+1].y - pc[i+1].x*pc[i].y );
    if(area < 0)
        area *= (-1);
}

计算出面积后，我们必须计算所有多边形边的点数。这可以使用以下方法完成:

int getBoundaryPoints()
{
    long left=0, right=0;
    int noPoints = 0;
    for(int i=1;i<=n;++i)
    {
        st = abst( pc[i].x - pc[i+1].x );
        right = abs( pc[i].y - pc[i+1].y );
        if(right == 0)
            right = left;
        if(left == 0)
            left = right;
        noPoints += gcd(left, right) +1;
    }
}

也有了这个计算，我们可以找到里面的点数

noPointsInside = (computeArea() - (getBoundaryPoints() - n)) / 2 + 1;

最终时间复杂度:O(N)最终内存复杂度:O(N)