Counting lattice points inside a triangle

问题:

I've points for a big triangle lets call it a, b, c. (a = (x, y) and so on).

Now I want to count the number of integral points inside the area enclosed by this triangle, so I first looked at Pick's theorem. The second approach that I considered was generating a list of points bounded by max, min of the triangle, and then checking if each point lies inside the triangle.

I used the Barycentric coordinates method to do this. It works however my triangle is pretty huge and my program is basically a brute force across points. How do I improve on this algorithm?

My code can be found here: https://bpaste.net/show/58433b6e389c

回答1:

This problem can and should be solved using Pick's theorem. Read the article to have a full understanding on how it works and it will work for any polygon you can think of. So, "Pick says" that if you want to compute the area of a polygon you have the formula area = noOfInsidePoints + noOfBoundaryPoints /2 - 1. To compute the area of any polygon you can use the following code, where pc is an array of structures representing the vertices of the polygon.

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);
}

Having the area computed, we have to count the number of point from all of the polygon edges. This can be done using the following:

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;
    }
}

Having this computed too, we can find the number of point inside

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

Final time complexity: O(N) Final memory complexity: O(N)