17.16 Integer Geometry

Problem

Many computational geometry problems use coordinates that are naturally integers:

grid maps
pixels
game worlds
GIS tiles
CAD layouts
competitive programming datasets

In these settings, floating-point arithmetic often introduces unnecessary complexity.

A segment intersection test that should be exact may fail because of rounding. A convex hull algorithm may classify collinear points incorrectly. A polygon area computation may lose precision even though every input coordinate is an integer.

Integer geometry avoids many of these issues by performing calculations exactly.

Solution

Whenever the problem permits, perform geometric predicates using integer arithmetic.

The most important geometric operations:

orientation
area
distance comparison
segment intersection
point-on-segment tests

can all be implemented without floating-point arithmetic.

The central idea is simple:

compare values directly
avoid division
avoid square roots
avoid trigonometric functions

As long as intermediate calculations do not overflow, the results are exact.

Exact Orientation

The orientation predicate is naturally integer-valued.

Given:

A = (x1, y1)
B = (x2, y2)
C = (x3, y3)

compute:

def orientation(a, b, c):
    return (
        (b.x - a.x) * (c.y - a.y)
        -
        (b.y - a.y) * (c.x - a.x)
    )

The result is:

positive   -> left turn
negative   -> right turn
zero       -> collinear

No epsilon is needed.

No rounding occurs.

This exactness is one reason many geometry libraries prefer integer coordinates when possible.

Exact Polygon Area

Recall the shoelace formula:

def area2(points):
    result = 0

    n = len(points)

    for i in range(n):
        j = (i + 1) % n

        result += (
            points[i].x * points[j].y
            -
            points[j].x * points[i].y
        )

    return result

The returned value equals:

2 × signed area

If all coordinates are integers:

area2

is also an integer.

The actual area may be:

integer

or:

integer + 1/2

For example:

triangle:
(0,0)
(3,0)
(0,1)

Produces:

area2 = 3

Actual area:

3/2

Many algorithms never need to divide by two.

Keeping the doubled area preserves exact arithmetic.

Comparing Distances

Suppose two distances must be compared.

Avoid:

sqrt(dx * dx + dy * dy)

Instead compare:

dx * dx + dy * dy

directly.

Implementation:

def distance_squared(a, b):
    dx = a.x - b.x
    dy = a.y - b.y

    return dx * dx + dy * dy

Then:

if distance_squared(a, b) < distance_squared(c, d):
    ...

This is exact for integer coordinates.

No square roots are required.

Segment Intersection

Integer geometry works particularly well for segment intersection.

The algorithm from Section 17.3 uses:

orientation
bounding-box checks

both of which can be computed exactly.

def segments_intersect(a, b, c, d):
    ...

No floating-point arithmetic is necessary.

As a result:

touching endpoints
collinear overlaps
shared vertices

can be handled reliably.

Rational Coordinates

Some constructions produce non-integer coordinates.

Example:

line intersections
polygon clipping
Voronoi vertices

Instead of immediately converting to floating point, store coordinates as rational numbers.

Python example:

from fractions import Fraction

x = Fraction(1, 3)
y = Fraction(7, 5)

Arithmetic remains exact:

Fraction(1, 3) + Fraction(1, 6)

produces:

1/2

exactly.

This approach is slower than integer arithmetic but avoids rounding errors.

Pick's Theorem

Integer geometry provides remarkable results that do not exist in general floating-point geometry.

One example is Pick's Theorem.

For a simple polygon whose vertices lie on integer lattice points:

Area
=
I + B/2 - 1

where:

I = interior lattice points
B = boundary lattice points

Example:

rectangle:
(0,0)
(4,0)
(4,3)
(0,3)

Interior lattice points:

6

Boundary lattice points:

14

Therefore:

6 + 14/2 - 1
=
12

which matches:

4 × 3
=
12

Pick's Theorem appears in combinatorial geometry and programming contests.

Counting Boundary Lattice Points

For an edge:

(x1, y1)
(x2, y2)

the number of lattice points on the edge is:

gcd(
    |x2 - x1|,
    |y2 - y1|
)

Implementation:

from math import gcd

def boundary_points(a, b):
    return gcd(
        abs(a.x - b.x),
        abs(a.y - b.y)
    )

Summing over all polygon edges yields the boundary count needed by Pick's Theorem.

Coordinate Compression

Integer geometry often appears with large coordinates.

Example:

1,000,000,000
5,000,000,000
9,000,000,000

Only the ordering matters.

Coordinate compression replaces them with:

0
1
2

while preserving relative order.

def compress(values):
    values = sorted(set(values))

    return {
        value: index
        for index, value in enumerate(values)
    }

Compressed coordinates are widely used in:

segment trees
Fenwick trees
sweep-line algorithms
rectangle union
range queries

Overflow Concerns

Integer arithmetic is exact only if values fit the numeric type.

Suppose:

coordinates ≈ 10^9

Then:

x × y ≈ 10^18

A 32-bit integer cannot store this value.

A signed 64-bit integer can:

2^63 - 1
≈ 9.22 × 10^18

But even 64-bit integers can overflow for larger coordinates.

Language behavior differs:

Language	Integer Behavior
Python	Arbitrary precision
Java	Fixed-width
Go	Fixed-width
C++	Fixed-width
Rust	Fixed-width

Always estimate the largest possible intermediate value.

Exact Convex Hulls

Convex hull algorithms become particularly clean with integer coordinates.

The monotonic chain algorithm uses:

orientation
sorting

only.

Both operations are exact.

while orientation(
    hull[-2],
    hull[-1],
    point
) <= 0:
    hull.pop()

No epsilon tuning is required.

This makes integer convex hull implementations extremely reliable.

Integer Line Representation

A line:

Ax + By + C = 0

can be represented exactly using integer coefficients.

Given points:

(x1,y1)
(x2,y2)

construct:

A = y2 - y1
B = x1 - x2
C = -(Ax1 + By1)

Normalize:

divide by gcd(A,B,C)

This representation is useful for:

line comparison
parallelism
incidence tests

without floating-point arithmetic.

Common Pitfalls

Assuming Integer Means Safe

Overflow can still occur.

Converting to Float Too Early

Keep values exact as long as possible.

Using Square Roots for Comparisons

Squared distances are sufficient.

Ignoring Rational Results

Line intersections often produce fractions even when inputs are integers.

Mixing Coordinate Systems

Compressed coordinates should not be used directly for geometric measurements.

They preserve order, not distance.

Complexity Analysis

Integer arithmetic usually has the same asymptotic complexity as floating-point arithmetic:

orientation      O(1)
area             O(n)
convex hull      O(n log n)
segment test     O(1)

The primary difference is reliability, not asymptotic performance.

Arbitrary-precision arithmetic may increase constant factors, but the algorithmic structure remains unchanged.

Discussion

Integer geometry occupies an important niche in computational geometry because it provides exact predicates with relatively little effort. Many classical geometric algorithms become simpler when coordinates are integral. Orientation tests become exact. Polygon areas become exact up to a factor of two. Distance comparisons avoid square roots. Segment intersections avoid epsilon thresholds.

For grid-based and discrete geometric problems, integer arithmetic should usually be the default choice. Floating-point arithmetic is most valuable when the problem itself contains inherently non-integral quantities. Even then, preserving exact predicates whenever possible often leads to more robust and maintainable geometric software.