Counting lattice points inside a triangle

Question

I have points for a large triangle that lets you call it a, b, c. (a = (x, y), etc.).

Now I want to count the number of integer points inside the area surrounded by this triangle, so I first looked at Peak's theorem. The second approach, which I considered, spawns a list of points bounded by the max, min of the triangle, and then checking whether each point is inside the triangle.

I used the barycentric coordinate method for this. It works, however my triangle is quite huge, and my program is mostly brute force at different points. How to improve this algorithm?

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

Answer 1

This problem can and should be solved using the Select Theorem . Read the article to get a complete picture of how it works, and it will work for any polygon you can think of. So, Pick says that if you want to calculate the area of ​​a polygon, you have a formula area = noOfInsidePoints + noOfBoundaryPoints /2 - 1. To calculate the area of ​​any polygon, you can use the following code, where pcis the 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);
}

When calculating the area, we must calculate the number of points from all the edges of the polygon. 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;
    }
}

With this value, we can find the number of points inside

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

: O (N) : O (N)