Counting lattice points inside a triangle

Question

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

@DavidEisenstat Well, for one thing, Pick's theorem only works for integral triangles, so if one coordinate is a rational/irrational point, it breaks down... Of course, the OP did not specify what kind of triangle he/she is dealing with, but said tried Pick's theorem, so I suppose it's assumed to be an integral triangle? — Hyacinth, Jul 06 '21 at 04:17

score 1 · Answer 1 · edited Jun 20 '20 at 09:12

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)

score 1 · Answer 2 · edited Sep 16 '21 at 08:25

Number of Lattice Points inside a trianlge: Pick's Theorem

from operator import abs
def renj(pts):
    X=[]
    Y=[]
    for i in range(len(pts)):
        if i in [0,2,4]:                    #(0-x1, 1-y1) (2-x2,3-y2) (4-x3,5-y3)
            X.append(pts[i])
        else:   
            Y.append(pts[i])
    return [min(X), max(X), min(Y), max(Y)]             # returns the range for triangle.

def m(a,b):
    from math import e
    if b[0]-a[0]:
        return (b[1]-a[1])/(b[0]-a[0])
    return e

def test(a,b,z):                                        # creating function to check if z lies on line(ab)
    if m(a,b)==m(a,z):
        return 1
    return 0    

n=int(input())      
for i in range(n):
    points = list(map(int, input().split()))
    count = 0
    A=[points[0], points[1]]
    B=[points[2], points[3]]
    C=[points[4], points[5]]
    r = renj(points)
    for u in range(r[0], r[1]+1):
        for v in range(r[2], r[3]+1):
            Z=[u, v]
            if test(A,B,Z) or test(A,C,Z) or test(B, C, Z):
                count += 1
    aa=abs((A[0]*(B[1]-C[1])+B[0]*(C[1]-A[1])+C[0]*(A[1]-B[1]))/2)
    #print("are",aa)
    bb=count
    #print("b",bb)
    ii=(aa+1)-bb/2
    print(int(ii))

The solution is based on: Pick's Theorem

A + 1 = i + b/2

A: Area of triangle
i: Interior Points
b: Boundary points including vertices
Note: Valid for integer points. Suggestions are invited from Community.

snippet code

Input Holds for integer inputs.

1                      # Number of trianlges
2 4 8 2 10 6           # x1 y1 x2 y2 x3 y3

Output

12        #As, In triangle there are 12 Points

Counting lattice points inside a triangle

2 Answers2

Number of Lattice Points inside a trianlge: Pick's Theorem

Linked