Lattice Points inside a Non-Lattice Polygon

For polygons with integer vertices, Pick's theorem relates area to interior and boundary lattice counts. For arbitrary (real) vertices you need another tool.

This lesson follows CP-Algorithms — Lattice points: reduce the polygon to signed edge floor-sums, then evaluate

Σ_{x = 0}^{n−1}  ⌊k x + b⌋

in O(log n) via a Euclidean-style reduction.

Prerequisite flavor: Basic Geometry (edges / orientation).

Polygon → edges

Process each edge A → B and add the number of lattice points strictly under that edge, with a sign from orientation (same idea as trapezoid / shoelace area).

Vertical edges contribute 0 to this horizontal-strip view (handle separately if you need points on the edge).

Line through an edge

Edge from (x₁, y₁) to (x₂, y₂) with x₂ ≠ x₁:

y = k x + b
k = (y₂ − y₁) / (x₂ − x₁)
b = (y₁ x₂ − x₁ y₂) / (x₂ − x₁)

Shift so the left endpoint sits at a convenient origin:

x = x' + ⌈x₁⌉
b' = b + k · ⌈x₁⌉

Then work with x₁' = 0, x₂' = x₂ − ⌈x₁⌉, and n = ⌊x₂'⌋.

Convention in the core sum: do not count x = n or y = 0 inside the recursion (add boundary cases by hand if the problem needs them). Assume k' ≥ 0, b' ≥ 0 (reflect / shift if not).

Goal:

Σ_{x' = 0}^{n − 1}  ⌊k' x' + b'⌋

Evaluating the floor sum

Case A — k ≥ 1 or b ≥ 1

Count the integer strip under ⌊k⌋·x + ⌊b⌋ in closed form:

Σ_{x=0}^{n−1} (⌊k⌋·x + ⌊b⌋) = (⌊k⌋·(n−1) + 2⌊b⌋) · n / 2

Remainder points satisfy

0 < y ≤ (k − ⌊k⌋)·x + (b − ⌊b⌋)

so set k' = {k}, b' = {b} — both in [0, 1).

Case B — k < 1 and b < 1

Let t = k n + b. If ⌊t⌋ = 0, return 0.

Otherwise flip axes: new origin at (n, ⌊t⌋), x' down, y' left. The count equals another floor-sum with slope 1/k and length ⌊t⌋ — back to Case A. This is the reciprocity step (cousin of Euclid / Dedekind sums).

Complexity

Each Case-A step removes a constant fraction of the points when ⌊k⌋ / k is bounded away from 0; reciprocity shrinks the “n” parameter like a Euclidean algorithm. Overall O(log n) arithmetic steps (plus the cost of rational / careful floating ops).

Implementation

Core routine: points with 0 ≤ x < n and 0 < y ≤ ⌊k x + b⌋.

// Fraction: rational with floor(), +, -, *, /, comparisons
long long count_lattices(Fraction k, Fraction b, long long n) {
    auto fk = k.floor();
    auto fb = b.floor();
    long long cnt = 0;
    if (k >= 1 || b >= 1) {
        cnt += (fk * (n - 1) + 2 * fb) * n / 2;
        k -= fk;
        b -= fb;
    }
    auto t = k * n + b;
    auto ft = t.floor();
    if (ft >= 1) {
        cnt += count_lattices(1 / k, (t - ft) / k, ft);
    }
    return cnt;
}

Numerics: prefer exact rationals. If numerators/denominators start ≤ C and you cancel GCDs, recursive values stay around C². With doubles, treat values within ε² of an integer as that integer when flooring (ε = input accuracy).

🧪 Floor-sum demo (exact Fraction, C++)

Check: floor-sum ideas

Quiz

Lattice floor-sums

1 / 4

Pick’s theorem applies directly when…

Pick an answer to see if you are right.

Practice drills

Activity: Naive floor sum

Input: integers kn kd bn bd n meaning k=kn/kd, b=bn/bd. Print Σ_{x=0}^{n-1} floor(k·x+b) (exact rationals; n small).

Further reading

• CP-Algorithms — Lattice points
• Pick’s theorem for the lattice-vertex special case
• Dedekind sums / lattice-point enumeration under lines (number-theory view of the same reciprocity)

Cheat sheet

Idea	Takeaway
Polygon	Signed sum of per-edge floor counts
Edge	y = kx + b, shift to x'≥0
Core	Σ ⌊kx+b⌋ for x=0..n−1
Peel	Add strip (⌊k⌋(n−1)+2⌊b⌋)n/2
Flip	Recurse with 1/k and n' = ⌊kn+b⌋
Time	O(log n) steps
Numerics	Exact Fraction, or doubles with ε² floor