Which side of the line is inside

Draw a closed loop on a page without letting it cross itself. It divides the page into two pieces: the part inside and the part outside. Any two points inside can be joined without crossing the curve, any two outside likewise, and no point inside can be joined to any point outside at all.

That is the Jordan curve theorem. It is one of the most obvious statements in mathematics and one of the hardest elementary ones to prove, and the two facts are related: the eye settles the question so quickly that the mind is never asked it.

So the figures here are built to put the eye out of work.

Looking at that picture and answering by eye is not possible. Counting crossings along one ray is easy, and it settles the matter.

The rule, and why parity is the right thing to count #

Fire a ray from the point in any direction and count how many times it crosses the curve. If the count is odd the point is inside; if even, outside.

The reason is a walk. Start at the point and travel out along the ray. Each time the curve is crossed, the traveller passes from one side to the other. Far enough out, past everything, the traveller is certainly outside. So the traveller’s final state — outside — plus the number of switches determines the starting state, and only the parity of the number of switches matters.

Two points a few pixels apart, one inside and one outside, and nothing visible distinguishes them. That is not a defect of the drawing. It is what the theorem is protecting: the inside is a perfectly well-defined region even where it is thin, tangled and impossible to see.

The same rule where the eye can check it #

A rule that can only be applied where nothing else works is a rule nobody has any reason to trust. So here it is on a curve simple enough to check by eye: a single open corridor, with the marked point sitting in the gap rather than in the passage. The ray crosses twice, the rule says outside, and looking says outside.

That agreement is the control. It is worth being clear about what it does and does not establish. It does not verify the rule — one agreement on one easy case is nothing. What it does is rule out a whole class of failure in which the rule is subtly inverted, or counts the wrong thing, or works only for convex regions. Those failures would show up here, where the answer is independently known.

This site’s standing habit is that a search must be shown capable of reporting something other than what it reports. The equivalent for a classifier is that it must be shown agreeing with an answer obtained some other way, on a case where another way exists.

The count is not the answer; the parity is #

A reader entitled to be suspicious will ask whether the answer depends on which direction the ray was fired. It does not, and the figure both draws that and checks it: sixteen rays are drawn, and three hundred and sixty are tested, and every one of them agrees on the parity while disagreeing on the count.

The number of crossings is a property of the ray. Its parity is a property of the point. That distinction is what makes the rule a definition rather than a procedure, and it is the same distinction the winding number rests on — a quantity computed from an arbitrary choice that turns out not to depend on it.

Why the parity is independent of direction is worth a sentence, and it is the same argument as before turned sideways: rotating the ray continuously changes the crossings only by pairs, since a crossing can only appear or vanish when the ray becomes tangent to the curve, and at a tangency two crossings arrive or leave together.

Where the rule needs care #

There is one situation in which counting crossings goes wrong, and it is not exotic — it is the commonest bug in every implementation of this rule ever written.

If the ray passes exactly through a corner of the curve, the two edges meeting at that corner both get counted, or neither does, depending on how the test is written. When the curve continues in the same direction through the corner, the corner should count once; when it turns back, it should count twice or not at all. A test that treats every edge alike will get one of the two cases wrong.

The repair is a convention: count an edge only if the ray’s crossing parameter falls in its half-open range, including one endpoint and excluding the other. Then a corner belongs to exactly one of its two edges, and both cases come out right. Every figure on this page uses that convention, and the assertion that all three hundred and sixty directions agree is what would catch it if the convention were wrong — a ray through a corner would be one of the directions, and it would disagree.

A rule that works for almost every input is not a rule. The corner case here has measure zero among directions and turns up constantly in practice, because curves in the wild have their corners on the grid and so do the points being tested.

What the curve is, and what the plane is #

The theorem has two halves and only one of them is about the curve.

At least two pieces says the curve genuinely gets in the way: there are points that cannot be joined without crossing it. That half is the one the crossing rule proves directly — a point with odd parity and a point with even parity cannot be joined by a path avoiding the curve, because parity would have to change somewhere along the path and it can only change at a crossing.

At most two pieces says there is nothing else: every point of odd parity can reach every other, and likewise for even. That half gets no help at all from counting crossings. It is a connectedness claim, and connectedness is not something a parity test can see — a test that assigns each point a label says nothing about whether points sharing a label are joined.

The figure’s flood fill is aimed squarely at that second half, and it is the only computation on this page that could have come back with a surprise. Counting components on a fine grid is a genuinely different operation from classifying points: it asks about neighbours rather than about rays, and a curve that penned off a pocket of inside from the rest of the inside would show up as a third component and nothing else here would notice.

Classifying everything, and checking it against the area #

Applying the rule to a grid of points classifies the whole plane, and the picture that results is the inside emerging as a region without anyone having drawn it.

The figure checks the classification against something independent. The area of a polygon can be computed from its corners alone, by the shoelace formula, with no notion of inside or outside involved. Multiplying the count of inside sample points by the area of a cell gives an estimate of the same quantity. The two agree to within a few per cent, which is the sampling error, and the figure asserts that they do.

That is the check that matters, because it compares the crossing rule against a computation that shares no concept with it. A wrong crossing rule would classify a corridor as outside somewhere, and the sampled area would fall short.

The figure also runs a much finer sweep that nothing draws, and counts the connected pieces of the result by flooding. It finds exactly two. That is the Jordan curve theorem, verified on this curve rather than proved.

What the rule costs #

The crossing rule is also an algorithm, and its cost is worth a paragraph because the shape of the cost explains why it is the one everyone uses.

Classifying one point against a polygon of m edges takes m tests: one per edge, each a few arithmetic operations, with no data structure to build and nothing to sort. That is the whole implementation, and it is about six lines.

Classifying many points is where the arithmetic starts to hurt, and the figure that shades the plane is the honest illustration: four hundred and sixteen sample points against a polygon with dozens of edges, and then a much finer sweep behind the scenes that no reader sees. Doing better means preprocessing the polygon — sorting its edges, building a structure that answers queries without touching them all — and that is a subject of its own with its own cost model, next door at nearest-neighbour partitions of the plane and beyond them in the algorithms that make such partitions searchable.

What belongs here is the reason the naive method is correct, which is the parity argument, and the reason it is robust, which is that it consults no tolerance anywhere except in deciding whether a ray is parallel to an edge. A method whose only floating-point judgement is a parallelism test is a method that behaves the same on every machine.

Why the theorem is hard #

The claim has three parts and each is a separate difficulty: the complement has at least two pieces, it has at most two pieces, and the curve is the boundary of each.

For a polygon all three are provable by the argument above, and the proof is a page. The theorem is stated for any curve that is continuous and does not cross itself — which includes curves with no corners anywhere, curves of infinite length, curves whose boundary has positive area. For those the ray argument collapses immediately: a ray can meet such a curve in infinitely many points, so there is no count to take the parity of.

What the general proof needs instead is machinery — a way of assigning the winding number to curves too wild to count crossings on, and a compactness argument to get from local behaviour to global. Jordan’s own 1887 proof was considered incomplete for decades, and whether the criticism was fair is still argued about.

The pattern is one this site keeps meeting. Four colours suffice is easy to state, apparently obvious after ten minutes with a pencil, and required a computer. Obviousness is a fact about human vision, and it correlates with nothing.

The first failure: a curve that crosses itself #

Drop the no-self-crossing condition and inside stops being one question.

The pentagram’s centre is crossed an even number of times by any ray, so the crossing rule declares it outside. The curve goes round the centre twice, so the winding rule declares it inside — twice over. Both rules are correctly applied and they disagree, because they were only ever the same question for curves that do not cross themselves.

Which of the two is wanted is a design decision rather than a mathematical one, and it is the same kind of decision as choosing whether a graph’s edges may repeat — a question the seven bridges has to settle before it can be asked. Graphics systems have to choose, and both choices are standard: the even-odd rule and the nonzero rule fill a pentagram differently, one leaving the middle hollow and the other filling it. Neither is wrong. There is no fact of the matter to be wrong about.

The second failure: a curve on the wrong surface #

The theorem is about the plane, and it is false on other surfaces.

Run a closed curve down the middle of a Möbius band and cut along it. The result is not two bands; it is one longer band. The curve does not separate the surface, and no amount of care about crossings will make it do so.

The same happens on a torus: a curve running round the hole leaves a cylinder, which is connected. Both failures are detected by the same invariant — the curve is not the boundary of anything — and the general statement of when a curve separates a surface is a piece of algebraic topology rather than a picture. The plane’s flatness is doing more work in the original theorem than it appears to.

What the picture cannot show #

Every curve here is a polygon. Finitely many straight edges, corners on known coordinates, crossings countable by arithmetic. The theorem is about curves with none of those properties, and the case that makes it hard is exactly the case no figure can draw — a curve that is continuous, never crosses itself, and is too rough to have a tangent anywhere.

The two pieces are verified, not proved. The flood fill found exactly two components on one curve at one resolution, and a finer grid could in principle find a third that the coarse one bridged. Nothing here rules that out; what rules it out is the theorem.

And the inside is not drawn — it is inferred. Every shaded region on this page is the browser applying its own fill rule to the same polygon, which is a second implementation of the same idea rather than an independent witness. The independent witness is the area, and it is a number rather than a picture.

Where the ladder goes next #

The rung above this one is about what a curve in the plane can be like. A simple closed curve can have positive area, can fail to have a tangent anywhere, and can be so convoluted that the inside contains no disc of any size — and the theorem holds for every one of them, which is what makes it worth proving rather than looking at.

There is also the question of what a separating curve knows about the thing it separates. A closed curve in the plane bounds a region with an area, a perimeter and a shape; a closed curve on a knotted loop in space bounds nothing at all, and the three legal moves are about exactly which curves in space can be untangled. The move from two dimensions to three destroys the theorem entirely: a closed curve in space separates nothing, and it takes a closed surface to divide space into an inside and an outside.

Sideways, the same question on a surface becomes: which closed curves separate it, and what does the answer say about the surface? A sphere is separated by every closed curve; a torus is not; and the number of independent curves that fail to separate turns out to be twice the genus, which ties this directly to the Euler characteristic and to how surfaces are classified. The Jordan curve theorem, from that direction, is the statement that the plane and the sphere have genus nothing.