Pick's Theorem

For a simple polygon whose vertices are lattice points:

$A=I+\frac{B}{2}-1,$

where $I$ is the number of interior lattice points and $B$ the number of lattice points on the boundary.

Computing the three quantities

Area — shoelace, exactly:

long long twiceArea = 0;
for (int i = 0; i < n; i++) twiceArea += cross(p[i], p[(i+1) % n]);
twiceArea = llabs(twiceArea);

Boundary points — each edge from $a$ to $b$ contributes $\gcd (|\Delta x|,|\Delta y|)$ lattice points, counting one endpoint per edge:

long long B = 0;
for (int i = 0; i < n; i++) {
    P d = p[(i+1) % n] - p[i];
    B += __gcd(llabs(d.x), llabs(d.y));
}

Interior points — rearrange Pick:
$I=A-\frac{B}{2}+1=\frac{2A-B+2}{2}.$

long long I = (twiceArea - B + 2) / 2;               // always an integer

Everything is exact integer arithmetic — no floating point anywhere.

Why the edge count is a gcd

The lattice points strictly between $(0,0)$ and $(\Delta x,\Delta y)$ are at multiples of the primitive vector $\left(\frac{\Delta x}{g},\frac{\Delta y}{g}\right)$ with $g=\gcd$. There are $g-1$ of them, plus one endpoint, giving $g$ per edge when counted consistently around the polygon.

What it is for

Problem	Use
Count lattice points inside a polygon	$I=A-B/2+1$
Count lattice points on the boundary	the gcd sum
Count all lattice points in a polygon	$I+B$
Verify a polygon’s area from lattice counts	Pick’s formula
Lattice points in a triangle	Pick, or a direct gcd argument
Lattice points under a line (floor sums)	a different technique — see below

What it does not do

• 3D has no analogue. Reeve tetrahedra have the same lattice-point counts but different volumes, so no Pick-style formula exists in three dimensions.
• Non-lattice vertices break it entirely.
• Self-intersecting polygons break it (the “area” is not well defined).
• Polygons with holes: $A=I+\frac{B}{2}-1+h$ where $h$ is the number of holes (using the Euler characteristic correction).

The related counting problem: lattice points under a line

Pick’s theorem does not handle “count ${\sum }_{i=0}^{n-1}\lfloor \frac{ai+b}{m}\rfloor$”. That is the floor sum / Euclidean-like algorithm:

long long floorSum(long long n, long long m, long long a, long long b) {
    long long ans = 0;
    if (a >= m) { ans += (n - 1) * n / 2 * (a / m); a %= m; }
    if (b >= m) { ans += n * (b / m); b %= m; }
    long long yMax = (a * n + b) / m;
    if (yMax == 0) return ans;
    ans += yMax * (n - (m * yMax - b + a - 1) / a);
    ans += floorSum(yMax, a, m, (a - (m * yMax - b) % a) % a);
    return ans;
}

$O(\log )$ by a Euclidean-style recursion — the standard tool for counting lattice points under a line, and a good companion to Pick’s theorem.

Worked example

The triangle $(0,0),(4,0),(0,3)$:

• $2A=12$, so $A=6$;
• boundary: $\gcd (4,0)+\gcd (4,3)+\gcd (0,3)=4+1+3=8$;
• $I=6-4+1=3$.

The interior points are $(1,1),(2,1),(1,2)$ — three, as predicted.

See also: Polygon Area · General Number Theory · Euclidean Algorithm