CODEWITHSUNDEEP
algorithmmath
user3651139
user3651139

Reputation: 113

Algorithm to Calculate the Number of Lattice Points in a Polygon

I'm trying to find the number of lattice points that strictly lie inside the boundary. I know Pick's theorem is 

A = i + b/2 - 1

where A = the area of the polygon, i is the number of lattice points that lie inside the polygon, and b is the number of lattice points on the perimeter of the polygon.

I can easily find the area using the Shoelace formula, but I'm not sure how to get the points on the boundary.

I'm not really sure where to look for resource on this, so I'd appreciate links too.

Upvotes: 11

Views: 3664

Answers (2)

Rexcirus
Rexcirus

Reputation: 2897

To expand Nemo's answer, for each side AB of the polygon the number of lattice points is equal to

gcd(x2 - x1, y2 - y1)+1

where A=(x1, y1), B=(x2, y2).

Upvotes: 0

Nemo
Nemo

Reputation: 71525

What a pretty question...

Since you are talking about Pick's Theorem, I will assume all of the vertices have integer coordinates.

Your question reduces to determining how many lattice points lie on the line segment from (x1, y1) to (x2, y2). Since the answer stays the same under translation by an integer, this reduces to determining how many lattice points lie on the line segment from (0, 0) to (x, y) for arbitrary x and y.

If x=0 or y=0, the answer is 1D and trivial (i.e. x+1 or y+1).

Otherwise, the answer is gcd(x,y) + 1. You prove this by showing (a) that any lattice point between (0,0) and (x,y) must be a multiple of the "least" lattice point; and (b) that any lattice point must have coordinates that are factors of (x,y).

Finally, be careful not to double-count the vertices as you walk around the polygon.

Upvotes: 12

Related Questions