Computational Geometry

Computational Geometry | Algoryva

Intuition

Which side am I on?

Imagine walking from a fence post A to a post B. Some trees are on your left, some on your right, and a few stand exactly on the line between the posts. Almost every geometry problem reduces to asking this question quickly and correctly, for many points.

Computers can answer it exactly with arithmetic on the coordinates alone. No angles, no distances, no square roots: just a product and a difference. That is what keeps geometry code correct when the numbers are large.

The concept

The cross product as a side test

For three points O, A and B, the cross product is (A − O) × (B − O) = (A.x − O.x)(B.y − O.y) − (A.y − O.y)(B.x − O.x). Its sign tells you the side of the directed line from O to A on which B lies. Its size is twice the area of the triangle O, A, B.

Positive: B is strictly left of the direction O → A (a counterclockwise turn).
Negative: B is strictly right of it (a clockwise turn).
Zero: O, A and B are collinear.
With O = (0,0), A = (4,0): B = (2,1) gives 4 × 1 − 0 × 2 = 4, so it is left. B = (2,0) gives 0, so it is on the line.
All of this is integer arithmetic. The value is exact, unlike an angle computed with atan2.

First, the naive way

Test every triangle

A point is a corner of the convex hull (the smallest convex polygon containing every point) exactly when it is not inside the hull of the other points. A simple way to test that: check whether the point lies inside some triangle formed by three of the others. If it does, it is not a corner.

This is correct, and the code is short, but it examines every triple of other points for every point. With n points that is about n⁴ triangle tests, so 100 points already means roughly 10⁸ operations. The version above also assumes at least one non-degenerate triangle exists; the monotone chain below has no such assumption.

python

from itertools import combinations

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def inside_triangle(a, b, c, p):
    d1, d2, d3 = cross(a, b, p), cross(b, c, p), cross(c, a, p)
    return not ((d1 > 0 or d2 > 0 or d3 > 0) and (d1 < 0 or d2 < 0 or d3 < 0))

def corners_naive(points):
    pts = sorted(set(points))
    count = 0
    for p in pts:
        others = [q for q in pts if q != p]
        covered = ((a, b, c, p)  a, b, c  (others, )  (a, b, c) != )
          covered:
            count += 
     count

(([(, ), (, ), (, ), (, ), (, )]))   
(([(, ), (, ), (, ), (, ), (, )]))

Cost: O(n⁴): every point against every triple of the others.

The observation

Sort, then walk around the hull with a stack

Sort the points by x, then by y. The lower hull is the chain you get walking from the leftmost point to the rightmost, always turning left. Keep a stack of the current chain. When a new point makes a turn that is not a strict left turn (cross ≤ 0), the top point cannot be a corner, so pop it. Do the same from right to left for the upper hull.

Removing points with cross = 0 is what drops points that sit on an edge. Keeping them would count edge points as corners, and the answer would be wrong.

See it move

Monotone chain on nine points

Watch the stack (the chain) grow with each point. Each grey edge that gets removed is a turn that was not a left turn. The final chain, read counterclockwise, is the hull, and the points left out are either inside it or on one of its edges.

Worked by hand

A triangle, traced by hand

Take the triangle with corners A = (0,0), B = (4,0) and C = (0,3). The cross product at A, from B to C, is 4 × 3 − 0 × 0 = 12, so the triangle's area is 12 / 2 = 6.

The shoelace formula gives the same result one edge at a time: sum x₁y₂ − x₂y₁ over the edges A→B, B→C, C→A. Those terms are 0, 12 and 0, so twice the area is 12.

Pick's theorem links area to lattice points. For a simple polygon with I interior and B boundary lattice points, twice the area is 2I + B − 2. This triangle has B = 8 boundary points (4 on AB, 1 on BC, 3 on CA, counting one endpoint of each edge once) and I = 3, so 2I + B − 2 = 6 + 8 − 2 = 12, matching the shoelace result.

Quantity	Value	How
twice the area	12	shoelace, or the cross product at A
interior points I	3	(1,1), (2,1), (1,2)
boundary points B	8	sum of gcd(\|dx\|, \|dy\|) over the edges
check	12	2I + B − 2

Implementation

Cross product, area and the hull in Python

The plan: a cross function that gives the sign, the shoelace sum with absolute value, and Andrew's monotone chain. Python integers never overflow, so these run exactly on any coordinates.

Plan in plain steps

pseudocode

cross(o, a, b) = (a−o) × (b−o)
shoelace: sum x_i·y_{i+1} − x_{i+1}·y_i over the edges, then abs
hull: sort; build lower and upper chains with a stack, popping on cross ≤ 0; join them without repeating the ends

python

def cross(o, a, b):
    return (a[] - o[]) * (b[] - o[]) - (a[] - o[]) * (b[] - o[])

 (poly):
    n = (poly)
    s = 
     i  (n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + ) % n]
        s += x1 * y2 - x2 * y1
     (s)

 (points):
    pts = ((points))
     (pts) <= :
         pts
    lower, upper = [], []
     p  pts:
         (lower) >=   (lower[-], lower[-], p) <= :
            lower.()
        lower.(p)
     p  (pts):
         (upper) >=   (upper[-], upper[-], p) <= :
            upper.()
        upper.(p)
     lower[:-] + upper[:-]

(((, ), (, ), (, )))   
(((, ), (, ), (, )))   
(([(, ), (, ), (, )]))   
((([(, ), (, ), (, ), (, ), (, ), (, ), (, ), (, ), (, )])))   
(([(, ), (, ), (, ), (, )]))

Complexity

What the operations cost

The hull's O(n log n) bound comes from sorting, not from the stack. Without the sort, no method this simple can find the hull.

cross product

time O(1)space O(1)

a fixed number of multiplications and subtractions.

shoelace area

time O(n)space O(1)

one term per edge, each computed once.

convex hull (monotone chain)

time O(n log n)space O(n)

sorting dominates; the stack pass is linear because each point is pushed and popped at most once.

all-pairs segment test

time O(n²)space O(1)

every pair is checked once. Faster sweep-line methods exist, but they are not needed for a few hundred segments.

Edge cases

Cases that break geometry code

Collinear pointsWith cross ≤ 0 they are popped, so only the two ends of the line are corners. With cross < 0 they would be counted and the answer is wrong.
Duplicate pointsDeduplicate with set() first. The problem statement says whether repeats count once; here they do.
One or two distinct pointsThe hull is the point itself, or the segment with two corners. Return early, before building chains.
Large coordinatesValues near 10⁹ make cross products near 10¹⁸ or more. Python handles this exactly; in C++ or Java use 64-bit integers, and compute the products before subtracting.
Orientation of the polygonThe shoelace sum is positive for counterclockwise polygons and negative for clockwise ones. Take the absolute value before reporting an area.

Common mistakes

Comparing angles with atan2 to sort or to test turns.
Use the cross product. Floating-point angles cannot always separate two directions that differ by a tiny amount, and integer tests are exact.
Keeping collinear points on the hull by using < 0 instead of ≤ 0.
Pop on cross ≤ 0. The hull has corners, not edge points.
Counting a boundary point as strictly inside.
“Strictly inside” excludes edges and corners. Test the boundary separately, as the brute-force check in this lesson does.
Reporting a negative area for a clockwise polygon.
Take the absolute value of the shoelace sum.
Forgetting that the polygon closes back to its first corner.
Use index (i + 1) % n so the last edge is included.

Recognize it in a contest

Recognising a geometry problem

Use the cross product for any side, turn or containment test, because it stays exact.

Reach for it when the problem says or implies

The input is a list of points or segments, and the question is about shape: area, perimeter, corners, containment, or whether shapes touch.
The problem asks whether a point is left, right or on a line, or about turning direction.
Coordinates are integers, and an exact answer is required (a count, a yes or no, or an integer area).

Look elsewhere when

If every point lies on one line, the problem is one-dimensional: sort and take the ends.
If the answer is a real length such as a perimeter, the result is irrational, so the output needs a stated precision. Exact integer methods then no longer apply.

Worked problem

Worked problem: corners of a hull

The problem

Given n points, possibly with repeats, count the corners of their convex hull. Points on an edge or inside the hull are not corners.

Deduplicate the points. Repeated copies of one point must count once.
Run the monotone chain. The number of corners is the length of the lower chain minus one, plus the length of the upper chain minus one. Each chain includes both extreme points, so each is shortened by one.
Check the degenerate cases: one point gives 1, and a set of collinear points gives 2 (the two ends).

python

def hull_corners(points):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return len(pts)
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
         (upper) >=   (upper[-], upper[-], p) <= :
            upper.()
        upper.(p)
     ((lower) - ) + ((upper) - )

Wrap-up

Remember this

The cross product answers side, turn and collinearity questions exactly, with integers only.
Area (shoelace) and lattice counting (Pick's theorem) are linked, so each one checks the other.
The convex hull is a sort followed by a stack walk; popping on ≤ 0 keeps only real corners.
Exactness is the point: avoid floating-point angles, and be explicit about collinear, duplicate and degenerate inputs.

Cheat sheet

Side test: cross(O, A, B) > 0 left, < 0 right, = 0 on the line; magnitude = twice the triangle area
Shoelace: twice the area = |Σ (x_i·y_{i+1} − x_{i+1}·y_i)|, O(n)
Pick's theorem: twice the area = 2I + B − 2, so I = (2A − B + 2) / 2
Hull: monotone chain: sort, two stack passes, pop on cross ≤ 0, O(n log n)
Segments: they touch if the signs cross, or an endpoint lies on the other segment

Top traps to avoid

Comparing angles with atan2 to sort or to test turns.
Keeping collinear points on the hull by using < 0 instead of ≤ 0.
Counting a boundary point as strictly inside.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the cross product of O = (0,0), A = (4,0) and B = (2,1), and what does its sign say?
2.What is twice the area of the triangle (0,0), (4,0), (0,3)?
3.Why does the monotone chain pop a point when the cross product is ≤ 0, rather than < 0?
4.A polygon has I = 3 interior and B = 8 boundary lattice points. What is twice its area by Pick's theorem?
5.For n ≤ 500 segments, what is a sensible first approach to deciding whether any two share a point?
6.Why is an exact integer cross product preferred over comparing atan2 angles?
7.What does print(1*1 - 0*0) print? This is the cross product of vectors (1, 0) and (0, 1).
8.What is the area of the triangle (0,0), (4,0), (0,3)? Print abs(4*3 - 0*0) // 2.
9.What is the squared distance between (1, 2) and (4, 6)?
10.What sign does the cross product of two vectors have when the second turns left (counter-clockwise) from the first?
11.What is the running time of the monotone-chain convex hull on n points?
12.Why compare squared distances instead of distances?
13.Are the points (0,0), (1,1), (2,2) collinear? Print their cross product value.
14.What does a zero cross product mean for three points?
15.How many integer points lie strictly between (0,0) and (4,2) on the segment? Print math.gcd(4, 2) - 1.

Computational Geometry

After this lesson you will be able to

Builds on

Unlocks

Which side am I on?

The cross product as a side test

Test every triangle

Sort, then walk around the hull with a stack

Monotone chain on nine points

A triangle, traced by hand

Cross product, area and the hull in Python

What the operations cost

Cases that break geometry code

Common mistakes

Recognising a geometry problem

Worked problem: corners of a hull

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core44 problems

Application16 problems

Reading the code