Computational Geometry

By the end of this lesson you will be able to decide, using nothing but integer multiplication, whether a point turns left or right of a line (the cross product), whether two segments touch (segmentsIntersect), whether ANY pair among n segments touches (a sweep line with a status set), how to wrap a fence around a cloud of points two different ways (grahamScan and jarvisMarch), and how to find the two closest points in O(n lg n) with divide and conquer. Every procedure runs on a picture you can step through, and you can feed each one your own points.

0. Points, segments and why we avoid division

Imagine pins stuck in a corkboard and pieces of string pulled tight between pairs of pins. A point is one pin, given by two whole numbers (x, y) — how far right and how far up from the bottom-left corner. A line segment is one taut string between two pins (its endpoints). Computational geometry asks questions about pins and strings: do two strings cross? what is the shortest rubber band around all pins? which two pins are closest?

Every picture in this lesson puts x to the right and y upward on the page. Every coordinate is a whole number. That is deliberate: the tests below use only addition, subtraction and multiplication of integers, so answers are exact. The obvious school method — compute the slope y₂−y₁ over x₂−x₁ — needs division, which turns into rounded decimals in a computer, breaks when a segment is vertical (division by zero), and can give the wrong answer when two points are only barely apart. Careful geometry code avoids it, and so do we.

Two assumptions come with this lesson. (1) Points given to the hull procedures are treated as a set, so duplicate points are merged first (the players say so when it happens). (2) anySegmentsIntersect assumes no segment is vertical — the custom-input box rejects vertical segments — and the picture also runs a brute-force check at the end so you can see the sweep agree with it.

In Dart we store a point as a tiny class Pt with integer fields x and y. It has value equality (two Pt(3,4) are equal), which makes sets and maps of points easy. Squared distance dist2 is used everywhere instead of the real distance, because the square root is the only non-integer step and comparing squares gives the same order.

Why integers and not slopes? Here is the failure in code: a vertical segment has no slope, and two different slopes can round to the same double. The cross-product test (introduced next) uses no division and tells them apart.

1a. Cross product and `direction`(p_i, p_j, p_k)

You are driving. You go from town p_i to town p_j, and there you must decide about town p_k: does the road bend left, bend right, or does p_k lie straight ahead (or straight behind) on the same road? The cross product answers this with one subtraction of two products — no angles, no slopes.

Make p_i the origin: the arrow to p_k is (p_k−p_i) and the arrow to p_j is (p_j−p_i). Their cross product is a single number, the (signed) area of the parallelogram the two arrows span: (x_k−x_i)(y_j−y_i) − (x_j−x_i)(y_k−y_i). We call this direction. Its sign is the whole answer:

> 0 → p_k is clockwise from p_j about p_i: walking p_i→p_j→p_k turns right.
< 0 → counterclockwise: the walk turns left.
= 0 → the three points are collinear (on one straight line; two of them may even coincide).
Swapping p_j and p_k flips the sign — the Dart file checks this on thousands of random triples.

The pictures walk through the pseudocode: first the two arrows from p_i, then the crosswise multiplication, then the verdict taken from the sign:

The next three pictures show the sign as a map. Fix the directed line from p_i to p_j, then test extra points one at a time: every point on the left side gives a negative direction, on the right side a positive one, exactly on the line zero. The last one accepts your own p_i, p_j and up to six test points.

Running time: two subtractions per coordinate, two multiplications, one subtraction: Θ(1) — about 9 arithmetic operations, no loops. Correctness idea: the cross product of two vectors equals |a||b| sin θ, where θ is the counterclockwise angle from the first vector to the second; direction computes it with the vectors in the order (p_k−p_i) then (p_j−p_i), so a positive value means sin θ > 0 for the angle from p_k to p_j — p_k lies clockwise of p_j. Overflow: with |coordinates| ≤ 10⁹ the result still fits a 64-bit Dart int (checked against BigInt in the verify file); on the web, Dart int is a JavaScript number, so keep coordinates below about 3·10⁷ there.

Dart implementation (points are Pt objects; direction uses no arrays, so there are no indices to worry about):

The maths as code. The cross product of two arrows, direction written through it, the meaning of its sign, the "area of the parallelogram" and "|a||b| sin θ" facts, and the swap-flips-the-sign rule are all computed and compared here:

Overflow bound as code. With |coordinates| ≤ C every difference is ≤ 2C, every product ≤ 4C² and the result ≤ 8C²; the code finds the largest C for which that fits a 64-bit int and checks direction against BigInt:

Input size → what's feasible. one direction is Θ(1) (about 9 operations): Q = 10⁷ calls ≈ 10⁸ steps → fine in one second; coordinates up to 10⁹ are exact in a native 64-bit int, but up to only about 3·10⁷ on the web (JavaScript numbers).

1b. `onSegment`(p_i, p_j, p_k)

A string hangs between two pins, and a third pin p_k is already known to be on the same straight line. Is p_k between the two pins, or out in the empty stretch of the line beyond an end? Put the string inside the smallest upright box that holds it (its bounding box) — if the pin is on the line AND inside the box, it is on the string.

Notice the precondition: onSegment only makes sense when p_k is collinear with p_i and p_j (direction = 0). It never checks that itself — segmentsIntersect calls it only after direction returned 0. Only the bounding box is tested, which is a shortcut that is correct because the point is already on the line.

Pitfall: onSegment never checks collinearity. Take p_i = (1,1), p_j = (7,4) and p_k = (5,1): p_k is inside the bounding box (1 ≤ 5 ≤ 7 and 1 ≤ 1 ≤ 4) so onSegment says TRUE, yet direction is not 0 and the point is nowhere near the string. Always ask direction = 0 first.

Running time: four comparisons — Θ(1). Correctness idea: on a line, "between the endpoints" is the same as "between the endpoints in x and in y". For a vertical segment the x-test is trivially true (both x's are equal) and the y-test does the work, which is the second example above; for a horizontal segment it is the other way round.

Key point: a point is on a segment exactly when it is on the segment's line (direction = 0) and inside its bounding box (onSegment). Neither test alone is enough.

Dart implementation (min and max come from dart:math):

The pitfall above in code: the bounding-box test alone accepts a point that is not on the string; combine it with direction = 0. A lattice-point enumeration (pi + t·(dx/g, dy/g)) serves as the independent reference:

Input size → what's feasible. Θ(1) per call (4 comparisons): 10⁷ calls ≈ 4·10⁷ steps → fine.

1c. `segmentsIntersect`(p₁, p₂, p₃, p₄)

Two strings lie on a table. They cross if, looking along string A, the two ends of string B are on opposite sides of it, and, looking along string B, the two ends of string A are on opposite sides of it (both conditions — one alone only says the lines cross somewhere, maybe far past a string's end). The awkward cases are the ones where an end of one string lands exactly on the other: then "opposite sides" fails, so the procedure falls back to onSegment.

The four direction values d₁..d₄ say which side each endpoint is on (or 0 for "exactly on the line"). Line 5 is the clean crossing test; lines 7–13 handle each endpoint lying on the other segment.

A single "straddle" test is not enough, and neither is testing only the bounding boxes. Collinear segments that do not overlap (the second example) have every d equal to 0, so line 5 fails and only the four onSegment checks decide — all four fail, so line 15 returns FALSE.

Running time: four DIRECTIONs plus at most four ON-SEGMENTs: Θ(1). Correctness idea (the case analysis): if the endpoints straddle each other properly, the segments cross (line 6). If not, an intersection can still exist only when some endpoint lies on the other segment — that endpoint has d = 0 and must pass onSegment (lines 7–14). Otherwise they are disjoint (line 15). The Dart file compares this procedure with an independent exact parametric solver on 40,000 random segment pairs (small coordinates on purpose, so touching and collinear cases are frequent).

Key point: two segments meet in exactly two ways: they properly cross (each straddles the other's line, lines 5–6) or an endpoint with d = 0 lies inside the other segment (lines 7–14). Every other input is FALSE.

Dart implementation:

Which return row fires for a given input (6, 8, 10, 12, 14 or 15) — the same case analysis as the pseudocode, as a function:

Input size → what's feasible. Θ(1) per pair: 10⁶ pairs ≈ 6·10⁷ steps → fine. Testing all pairs of n = 10⁴ segments is n²/2 = 5·10⁷ calls (fine), but n = 10⁵ is 5·10⁹ calls → use the sweep of section 2.

2. `anySegmentsIntersect`(S): the sweep line

Testing all pairs of n strings costs about n²/2 checks. Instead, sweep a vertical sweep line across the table from left to right, like a scanner bar. At any moment it cuts through a few strings; list them bottom-to-top — that ordered list is the status T. Two strings can only cross if at some moment they are neighbours in that list, so we only ever compare neighbours: when a string appears (its left end), compare it with its new neighbours above and below; when a string disappears (its right end), its former neighbours become adjacent, so compare them.

The sweep stops at event points: the 2n segment endpoints sorted left to right (ties: left endpoints before right endpoints, then lower y first). The status is a sorted set that supports insert, delete, find-the-neighbour-above and find-the-neighbour-below; a red-black tree (or any balanced search tree) makes each of them cost O(lg n). In the pictures the letters give segment names, the green segments are those currently in T, grey ones are finished, the highlighted one is the segment of the current event, and yellow marks the neighbour being tested.

Pitfall: do not compare a new segment with every segment in T — that is the O(n²) all-pairs method in disguise. Only the neighbours directly above and below can be the first to meet it. Also remember the stop rule: the procedure returns at the first intersection it sees, so the order of T is trustworthy only until then.

Running time: sorting the 2n endpoints is O(n lg n); the loop runs 2n times and each iteration does O(1) tree operations of O(lg n) plus at most two O(1) segmentsIntersect calls: O(n lg n) in total. Correctness idea: look at the leftmost intersection point q. Just before the sweep line reaches q, the two segments that meet there have become neighbours in T (nothing can lie between them or the intersection would not be the leftmost), and the event that made them neighbours (an insert or a delete) tested them — so the procedure returns TRUE at or before q. If no intersection exists, every test returns FALSE, and it correctly reaches the final return false (row 15). The procedure only says whether an intersection exists; reporting all k of them needs Bentley–Ottmann (Expert question).

Key point: the sweep replaces “test all n²/2 pairs” by “test only pairs that become adjacent in T”. At most two new adjacent pairs appear per event, and 2n events give O(n) tests plus O(n lg n) for the ordered set.

Dart implementation. The status T is a SplayTreeMap (a balanced search tree from dart:collection) keyed by segment index, whose order is "height at the current sweep position": compareAt compares two segments' heights exactly by cross-multiplication instead of division, ties are broken by slope just before (DELETE) or just after (INSERT) the sweep line, then by index. firstKeyAfter and lastKeyBefore give the neighbour above and the neighbour below, so every insert, delete and neighbour lookup costs O(lg n) and the whole run is O(n lg n):

The cost claim as code: an instrumented copy of the sweep counts events and segmentsIntersect tests (2n events, at most 2 tests per insert and 1 per delete, so ≤ 3n tests against n(n−1)/2 pairs):

Input size → what's feasible. n = 10⁵ segments → 2n = 2·10⁵ events × lg n ≈ 17 = 3.4·10⁶ tree steps → fine (all pairs would be 5·10⁹). Keep |coordinates| ≤ 10⁵: the exact height comparison multiplies values up to 6·10¹⁰ by 2·10⁵, which would overflow 64 bits near 10⁹.

3a. `grahamScan`(Q)

Hammer a nail into every point and stretch a rubber band around all the nails; let go and it snaps to the smallest convex shape enclosing them — the convex hull of the point set. Only the outermost nails touch the band. grahamScan builds that band by walking round the nails in angle order, keeping a stack (a pile where you only touch the top) of "nails on the band so far", and undoing a step (popping) whenever the newest nail would make the band bend the wrong way.

Step by step: (1) pick p₀, the lowest point (leftmost if tied) — it is certainly on the hull; (2) sort all other points by the angle they make around p₀, counterclockwise, using direction as the comparator (no trigonometry!); if several points have the same angle keep only the farthest — the nearer ones lie on the segment to it, never at a corner; (3) push p₀ and the first two sorted points r[0], r[1]; (4) for each next sorted point r[i], while the top two stack points and the new point do not make a left turn (direction ≥ 0), pop the top; then push the new point. What remains is the hull in counterclockwise order.

Why "nonleft" pops collinear points too: if the top point sits exactly on the segment from below-it to the new point, it is not a corner, so the hull should not list it. Using "> 0" instead would keep such points (see the debugging question).

Pitfall: sort the points around p₀ with the direction comparator, not with atan2: angles are floating point, so nearly-equal angles can tie or swap and the scan silently produces a wrong hull. Points with exactly the same angle from p₀ (direction = 0) must be ordered by distance, and only the farthest is kept (row 3 of the pseudocode).

Running time (cost table):

Rows	Work	Cost
1	one pass to find p₀	Θ(n)
2	sort by polar angle (comparator = one `direction`)	Θ(n lg n)
3	one pass dropping the nearer of equal-angle points	Θ(n)
7	the initial stack of three points	Θ(1)
8–11	every point is pushed once (≤ m pushes) and popped at most once (≤ m − 2 pops), so the while loop's total work over the whole for loop is linear (amortized)	Θ(n)
Total		O(n lg n), dominated by the sort

Correctness idea (loop invariant): at the start of each iteration of the for loop, the stack from bottom to top holds exactly the vertices of the convex hull of p₀ and r[0..i−1], in counterclockwise order. Popping removes any top vertex that the new point would swallow (a right turn or straight line), so the invariant is restored with r[i] on top. Degenerate case: if after the same-angle filter fewer than two sorted points remain (all points collinear with p₀), the procedure returns an empty list — the hull is only a segment, not a polygon.

Dart implementation. The pseudocode and the Dart code use the same names: the pivot is p0, the sorted points are r[0], r[1], …, so the loop is for (var i = 2; i < r.length; i++) and the three initial pushes are [p0, r[0], r[1]]. The Dart code also merges duplicate points first (toSet) and returns [] for fewer than three distinct points.

Rows 2–3 as code: the direction comparator, the tempting atan2 comparator that fails on nearly equal angles, a comparison counter (≈ n lg n), and the "keep the farthest on a ray" filter:

The loop invariant and the amortized cost as code: scanSorted is the scan loop (rows 7–11 of the pseudocode) with a hook that checks, at the start of every iteration, that the stack is exactly the hull of the points seen so far, and counters that confirm pushes ≤ m + 1 and pops ≤ pushes − 3:

Input size → what's feasible. n = 2·10⁵ → n lg n ≈ 3.5·10⁶ comparisons, whatever the hull looks like; n = 10⁶ still ≈ 2·10⁷ → fine. The scan uses an explicit stack, so no recursion-depth limit.

3b. `jarvisMarch`(Q)

Jarvis's march is gift wrapping. Tie the string to the lowest nail, then swing a stick round like a compass needle: the first nail the stick touches while turning counterclockwise is the next corner. Tie there and repeat, until you are back at the start. Each corner costs one look at every nail, so the price is (number of corners) × (number of nails).

The 14 rows in the panels below are this lesson's own listing of the gift-wrapping idea, verified in the Dart file against brute force and against grahamScan.

How one corner is found (rows 5–9): guess that next is any other point; then look at every point q — if q is on the right of the arrow cur→next (direction > 0), the guess was not extreme enough, so q becomes the new guess; if q is exactly on that line, keep the farther one (so points in the middle of a hull edge are skipped, like grahamScan does). After the loop, every point is on the left of (or on) cur→next, which is the definition of a hull edge.

Running time (cost table):

Points n	Hull corners h	`jarvisMarch` ≈ n·h	`grahamScan` ≈ n·lg n	Faster
1000	4	4,000	≈ 10,000	Jarvis
1000	10	10,000	≈ 10,000	tie
1000	1000 (all on a circle)	1,000,000	≈ 10,000	Graham

Each of the h rounds scans n points with O(1) work each, so the total is O(nh) — output-sensitive: cheap when the hull is small, O(n²) worst case (Kirkpatrick–Seidel and Chan get O(n lg h)). Correctness idea: the point chosen in a round has every other point on its left, so cur→next is a hull edge; starting from a hull vertex (the lowest point) and always taking the next edge counterclockwise walks the hull exactly once. All-collinear input returns just the two endpoints.

Key point: jarvisMarch does one full scan of all n points per hull corner, so its cost depends on the answer size h: fast when the hull is small, O(n²) when every point is a corner. grahamScan's cost depends only on n.

Dart implementation (points stay in a normal 0-indexed List):

The O(nh) claim as code: an instrumented copy counts the direction tests (exactly h·(n−1)) and compares them with grahamScan's n lg n:

Why n lg n is optimal for large hulls (the lower bound in the cheat sheet), as code: sort numbers by hulling the points (a, a²):

Input size → what's feasible. n = 10⁶ points with h ≤ 20 → n·h = 2·10⁷ → fine; h = n = 10⁴ → 10⁸ (borderline); h = n = 10⁵ → 10¹⁰ (too slow) → use grahamScan.

4. Finding the closest pair of points

Air-traffic control has n aircraft and wants the two that are closest, to warn them. Checking all pairs is about n²/2 distances. Divide and conquer: split the sky along a vertical line into a left half and a right half, solve each half recursively, and let δ be the smaller of the two answers. The only pair still missing is one plane on each side — and such a pair can only beat δ if both planes are within δ of the dividing line, in a narrow strip. The surprising fact: sorting the strip by height, each plane needs to be compared with only the next 7 planes above it.

The 14 rows in the panels are this lesson's own listing of the divide-and-conquer idea. It uses the "presort" trick: x (the points sorted by x) and y (sorted by y) are built once, and the recursion splits both arrays in linear time, never re-sorting.

Running time (recurrence as a table): each call does O(size) work outside its two recursive calls (splitting X and Y, building the strip, at most 7 comparisons per strip point), so T(n) = 2T(n/2) + O(n).

Level	Calls	Size of each	Work at this level
0	1	16	≈ 16
1	2	8	≈ 16
2	4	4	≈ 16
3	8	2–3 (base case ≤ 3)	≈ 16
lg n levels × n per level			Θ(n lg n) (plus O(n lg n) for the two initial sorts)

Correctness idea — why only 7: if a closer cross pair (p_L, p_R) with distance < δ exists, both lie in a δ × 2δ rectangle around the line. All points in one half are at least δ apart, so at most 4 fit in each δ×δ square, so the rectangle holds at most 8 points (coincident points on the line can push this to 8). p_R therefore appears among the 7 points after p_L in the y-sorted strip. Why bottom out at ≤ 3: a call with 1 point has no pair, and 2 or 3 points are quickest by brute force.

Key point: the 2δ strip looks scary but is cheap: sorted by y, each strip point needs comparing with only the next 7, because a δ×2δ box cannot hold more than 8 points that are pairwise at least δ apart.

Dart implementation. Two recursion-helpers give the classic "wrapper + recursive function" shape. closestPair builds X and Y once; closestRec is the recursive step. Splitting Y into YL and YR needs to know which points went left; because Pt has value equality (duplicates are indistinguishable) we count how many copies of each point are in XL. The result is a Dart record (squaredDistance, pointA, pointB):

The recurrence T(n) = 2T(n/2) + O(n) as code: the recursive cost function, its closed form n⌈lg n⌉ − 2^{⌈lg n⌉} + n (exactly n lg n for powers of 2), and the slower re-sorting variant that costs a factor lg n more:

The "only 7" bound as code: an exhaustive search shows a δ×δ square holds at most 4 points that are pairwise ≥ δ apart, so the δ×2δ window holds at most 8:

Input size → what's feasible. n = 2·10⁵ → n lg n ≈ 3.5·10⁶ distance tests → fine; all n²/2 = 2·10¹⁰ pairs is too slow; for n ≤ 3000 even the brute force (4.5·10⁶ pairs) is fine.

Quiz

Interview questions

Cheat sheet

Procedure	Time	Space	Handles collinear / touching?	When to use
direction (cross product)	Θ(1)	O(1)	Yes: 0 means collinear	Every orientation / turn / side-of-line test; exact with integers
onSegment	Θ(1)	O(1)	Only valid for a point already collinear	Second half of the touching test
`segmentsIntersect`	Θ(1)	O(1)	Yes, including endpoint touching and overlap	Is this pair of segments crossing?
`anySegmentsIntersect`	O(n lg n) with a balanced tree	O(n)	Assumes no vertical segments; ties handled by the event order	Do ANY two of n segments meet? (not all k)
`grahamScan`	O(n lg n)	O(n)	Pops collinear points; all-collinear input gives an empty list	General hull; predictable time
`jarvisMarch`	O(nh)	O(h)	Takes the farthest of collinear points	Hull expected to have very few corners
Closest pair (divide and conquer)	O(n lg n)	O(n)	Coincident points give distance 0	Nearest neighbours, collision detection
Convex hull lower bound	Ω(n lg n) in the comparison model (sorting reduces to hull), so `grahamScan` is optimal when h is large

Computational Geometry

0. Points, segments and why we avoid division

1a. Cross product and direction(pi, pj, pk)

1b. onSegment(pi, pj, pk)

1c. segmentsIntersect(p1, p2, p3, p4)

2. anySegmentsIntersect(S): the sweep line

3a. grahamScan(Q)

3b. jarvisMarch(Q)