Skip to content
Tutorials Center
My learning

Topics

Lesson 210 of 225 ยท Advanced Topics

Pick's Theorem, Half-Plane Intersection and Bresenham

Count lattice points with Pick's theorem, find the region cut out by half-planes with polygon clipping and draw exact integer lines with Bresenham in Python.

Computational Geometry Basics gave you the cross product, orientation tests, the convex hull and the shoelace area. This lesson adds three more tools that show up in contests, graphics and interview rounds, and all three can be done with exact integer or fraction arithmetic, so no floating-point error sneaks in.

  • Pick's theorem counts the grid points inside and on a polygon from its area and its boundary.
  • Half-plane intersection finds the region where many linear inequalities hold at once, the geometric heart of linear programming in two variables.
  • Bresenham's line algorithm draws a straight line on a pixel grid using only integer additions.

Every example is checked against an independent brute-force method.

Pick's theorem

A lattice polygon has all vertices on integer coordinates. Pick's theorem says that for a simple (non-self-intersecting) lattice polygon:

TEXT
A = I + B/2 - 1

where A is the area, I the number of lattice points strictly inside, and B the number of lattice points on the boundary.

Why is this useful? Area comes from the shoelace formula (see geometry basics), and B is easy: along an edge from (x1, y1) to (x2, y2) there are gcd(|dx|, |dy|) unit steps, so the boundary count is the sum of those gcds over all edges. Solve for I:

TEXT
I = (2A - B + 2) / 2          with  2A = |shoelace sum|  (an integer)

So you can count interior grid points of a huge polygon in O(n log C) without visiting a single cell.

Python Pick's theorem versus brute-force counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pick's theorem also works in reverse: from I and B you recover the area, and if you only know B and A you can count the inner points. It fails for polygons with holes or non-lattice vertices.

Half-plane intersection

A half-plane is one side of a line: all points with a*x + b*y <= c. The intersection of many half-planes is a convex region (possibly empty or unbounded). Typical questions: is there any point satisfying all the constraints? What is its area? Which vertex minimizes a linear cost (the geometry behind two-variable linear programming)?

Clipping a polygon by one line

The simplest exact method clips a big starting polygon by each half-plane in turn, like trimming a sheet with a ruler. For each polygon edge p -> q, let s_p = a*px + b*py - c; a point is inside when s <= 0.

  • both ends inside: keep q;
  • p inside, q outside: keep the crossing point;
  • p outside, q inside: keep the crossing point and then q;
  • both outside: keep nothing.

The crossing point is p + t*(q - p) with t = s_p / (s_p - s_q). Using Fraction keeps everything exact. Each clip is O(size of current polygon), which is at most the number of constraints processed so far, so the total is O(n^2) for n half-planes. (The classic sort-by-angle with a deque variant gets O(n log n); the clipping method is simpler and fast enough up to a few thousand constraints.)

flowchart LR
  A["Start: big bounding box"] --> B["Clip by half-plane 1"]
  B --> C["Clip by half-plane 2"]
  C --> D["..."]
  D --> E["Convex polygon: the feasible region"]

Each half-plane can only shrink the region. If it ever becomes empty, the system is infeasible.

Python Half-plane intersection by clipping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the linear-programming consequence: a linear objective over a convex polygon is maximized at a vertex, so after clipping you only evaluate the vertices.

Counter-clockwise order matters for the membership test. The clipping keeps the vertex order of the starting square, which is counter-clockwise, so the output stays counter-clockwise too. A degenerate result (a segment or a point) has fewer than 3 distinct vertices.

Bresenham's line algorithm

To draw a line from (x0, y0) to (x1, y1) on a pixel grid, which pixels should be lit? A float approach computes y = y0 + slope * (x - x0) and rounds, but it needs floating point and division. Bresenham's algorithm (1962) uses an integer error term instead.

For the first octant (0 <= dy <= dx), step x by 1 each time. Track err = 2*dy - dx. At each step, plot (x, y); if err > 0, move up (y += 1) and reduce err by 2*dx; then add 2*dy. Each step is a couple of integer additions, which is why it was perfect for early hardware and is still used in embedded graphics. Handling the other octants means swapping roles of x and y and signs; the compact general version below keeps one combined error value.

Python General Bresenham, with ASCII art and checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop runs max(|dx|, |dy|) + 1 times with no division, no multiplication by non-powers of two and no floats. Variants draw circles (the midpoint circle algorithm uses the same error idea) and thick or anti-aliased lines.

Choosing the tool

Task Tool Time
Count interior lattice points of a lattice polygon Pick's theorem with shoelace and gcd O(n log C)
Does a set of linear constraints have a solution? Area of the region? half-plane intersection O(n^2) by clipping, O(n log n) with sorting
Optimize a linear function in two variables clip, then check the vertices same
Which pixels does a segment cover? Bresenham O(max(dx, dy)) integer steps

Common mistakes: applying Pick's theorem to a polygon with non-integer vertices or holes, forgetting that the boundary count uses gcd(|dx|, |dy|) per edge (it is 0 for a zero-length edge but gcd(0, 0) = 0), clipping with floats and then comparing with ==, and forgetting to bound the starting region when the true intersection is unbounded.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A lattice polygon has area 12.5 and 11 boundary points. How many lattice points are strictly inside?

    From A = I + B/2 - 1: I = 12.5 - 5.5 + 1 = 8. Check the formula: I = (2A - B + 2) / 2 = (25 - 11 + 2) / 2 = 8.
  2. 2. How many lattice points lie on the segment from (0, 0) to (6, 4), counting both ends?

    gcd(6, 4) = 2 unit steps, so the segment has 2 + 1 = 3 lattice points: (0,0), (3,2) and (6,4).
  3. 3. Why is the result of intersecting half-planes always convex?

    A half-plane is convex, and the intersection of any number of convex sets is convex.
  4. 4. What makes Bresenham's algorithm attractive?

    The error term is updated by integer steps, which was fast on old hardware and avoids rounding issues.

Summary

  • Pick's theorem: A = I + B/2 - 1 for lattice polygons; compute I = (2A - B + 2) / 2 with the shoelace sum and edge gcds.
  • Half-plane intersection by clipping a bounding box with each constraint gives an exact convex region in O(n^2); linear objectives are optimized at its vertices.
  • Use Fraction for exact crossing points, and keep the polygon in counter-clockwise order.
  • Bresenham's algorithm draws a line with integer error tracking in O(max(dx, dy)) steps and stays within half a pixel of the true line.

Next: Sweep Line