A curve of pixels needs two kinds of touching

Which side of the line is inside began this sequence by checking the Jordan curve theorem on a computer: a closed curve with no self-crossings, a fine grid of sample points, a flood fill that counted the pieces of the complement and found exactly two. The essays that followed took the theorem into wild curves, into higher dimensions and finally, with Alexander’s horned sphere, into the place where its strong form fails. All of them worked in the continuous plane and treated the grid as an approximation.

This essay takes the grid seriously. On a screen, a curve is not an approximation to anything; it is a set of pixels, and the questions the theorem answers — is the curve in one piece, does it leave two — become questions about which pixels count as neighbours. There are two natural answers, and the surprise is that neither works on its own. The theorem holds on a square grid only if the curve and the rest of the plane are given different notions of touching, and it holds with a single notion only on a grid whose cells never meet at a point.

Four ways to say which pixels touch #

A pixel has four neighbours that share an edge with it and four more that share only a corner. A set of pixels is connected under a given rule if any two of its pixels can be joined by a chain of neighbours inside the set. The rule matters only at corners: two pixels meeting diagonally are adjacent under the eight-neighbour rule and not under the four-neighbour one.

The figure’s twelve pixels form a diamond, a ring of pixels each touching the next only at a corner. Under the eight-neighbour rule they form one closed chain, the obvious digital circle. Under the four-neighbour rule they are twelve separate pixels with nothing joining them. The complement — the thirteen pixels inside the diamond and everything outside it — behaves the other way round. Under the four-neighbour rule, the inside is sealed off: no chain of edge-neighbours crosses the diamond, so the complement has two pieces. Under the eight-neighbour rule, the inside leaks out through every gap between diagonal pixels, and the complement is one piece.

So the four panels give four verdicts. Eight neighbours for both: a closed curve with no inside. Four neighbours for both: an inside fenced in by twelve disconnected dots. Four for the curve and eight for the rest: neither a curve nor a separation. Only eight for the curve and four for the rest gives what the theorem says — one curve, two pieces. The reverse mixture, four for the curve and eight for the rest, fails on this particular shape only because the diamond is not a curve under four neighbours; a ring of edge-neighbours, tested under that mixture, behaves correctly.

The census of a small window #

One shape could be a coincidence, so the next figure tries every shape that fits.

A simple closed curve of pixels, in the definition Azriel Rosenfeld gave in the 1970s, is a connected set in which every pixel has exactly two neighbours in the set — the digital version of a loop that never crosses itself and never doubles back. The window is 4 pixels by 5, so there are $2^{20} - 1 = 1{,}048{,}575$ non-empty sets of pixels in it, and an empty border round the window stands for the infinite outside. Each set is tested for being a simple closed curve under each rule, and then its complement is broken into pieces under each rule.

Forty sets are simple closed curves of corner-neighbours. With the rest of the plane using edge-neighbours, all forty leave exactly two pieces. With the rest also using corner-neighbours, all forty leave one — not one of them separates anything. Forty-six sets are simple closed curves of edge-neighbours, after setting aside the twelve $2 \times 2$ blocks, in which each pixel has exactly two edge-neighbours but which enclose nothing. With the rest using corner-neighbours, all forty-six leave exactly two pieces. With the rest also using edge-neighbours, thirty-eight leave two and eight leave three.

That is the digital Jordan curve theorem, verified exhaustively at this size: with eight neighbours for the curve and four for the rest, or four for the curve and eight for the rest, every simple closed curve has exactly two complementary pieces. Rosenfeld proved it for curves of every size. The census shows the converse, which is what makes the theorem’s form compulsory: with the same rule for both, it fails, in one direction or the other, at the smallest size where it could.

A curve that divides the plane into three #

The eight failures with edge-neighbours throughout are all the same shape.

The curve winds round two inside pixels that meet only at a corner. Under the edge-neighbour rule those two pixels are separate pieces, so the curve has two insides and the plane is divided into three. Under the corner-neighbour rule they are one piece and the count is right. But the corner rule cannot be used for the curve as well: read with corner-neighbours, ten of the curve’s pixels have more than two neighbours in it, because the curve’s own turns touch diagonally across the inside, and it is no longer a simple curve at all.

The mixed rule has a price that the continuous theorem never charges: it is not symmetric between a picture and its negative. Swap black and white in the diamond and the same pixels that were a curve become part of the background, now read with the opposite rule, and the count of pieces changes. Software that analyses images has to decide which colour is the foreground before it can count objects or holes, and a black-on-white scan and its inverse can genuinely have different topologies. In the continuous plane a set and its complement are on equal terms; on the square grid one of them has to be given the corners.

The figure isolates the point of the whole essay. Where four squares meet at a corner, two diagonal squares either touch or do not, and the answer has to be the same for whatever lies on each diagonal. If the curve may pass through a corner, the rest of the plane may not; if the rest may, the curve may not. A corner can be a passage for one side, never for both — and the mixed rule is exactly the bookkeeping that enforces it.

Telling inside from outside along a row #

The first essay in this sequence decided inside and outside by parity: draw a ray from the point, count how often it crosses the curve, and call the point inside when the count is odd. On a grid the ray is a row of pixels, and the parity rule needs one adjustment that is the digital form of the corner case that essay dwelt on. A row can run along the curve for several pixels — a horizontal stretch of the curve — and such a stretch counts as a crossing only when the curve arrives at it from one side of the row and leaves it on the other. A stretch where the curve comes down to the row and goes back up is a touch, not a crossing, and counting it would flip the parity of every pixel beyond it.

With that rule, the parity along each row agrees with the flood fill on every curve in the census: under the mixed rule, the pixels of odd parity are exactly the shaded inside, and the pixels of even parity are exactly the outside. The same rule shows why the same-rule pairings cannot work. Under eight neighbours for both, a pixel of odd parity can be a corner-neighbour of a pixel of even parity, across a diagonal step of the curve, so parity is not constant on a piece of the complement and cannot be what tells the pieces apart. Under four neighbours for both, the trouble is the opposite one: parity is constant on each piece, but two pieces can share the same parity, as the two inside pixels of the three-piece curve do, so parity can no longer say how many pieces there are. Which side of the line is inside observed that a rule which works for almost every input is not a rule; on a grid the exceptional inputs are the corners, and they are not rare at all.

Why the continuous theorem has no such choice #

In the continuous plane two regions meeting at a single point do not form a connected region with a passage through the point unless the point belongs to one of them; a point belongs to one set or the other, never to both. The grid loses that information because it records only the squares and not their corners and edges. The mixed rule puts it back by deciding once and for all who owns the corners: the eight-neighbour side owns every corner it touches, the four-neighbour side owns none.

There is an equivalent repair that makes the corners explicit. Treat the grid as a cell complex, with each pixel an open square and its edges and corners as separate cells, and let a set of pixels include the edges and corners between its members. Ehud Khalimsky, Ralph Kopperman and Paul Meyer built a topology on the integer grid along these lines around 1990, and in it the Jordan curve theorem holds as a genuine theorem of topology, with no special rules. The mixed rule is that topology read off the pixels. A grid curve also cannot do what a curve that has area might suggest: Osgood’s continuous curve of positive area has no grid counterpart, because on a grid every curve occupies area by construction, a pixel at a time, and the question is only which pixels of the rest it cuts off.

The same bookkeeping turns up whenever pixels are counted topologically. Counting targets by their holes computed the Euler characteristic of shapes made of grid squares — corners minus edges plus squares — and found that it counts pieces minus holes. That formula is right only with the matching conventions: pieces counted with eight-neighbours, which is what closed squares sharing a corner do, and holes counted with four-neighbours. Count both with the same rule and the identity fails, for the same reason the census found. Pieces minus holes on a random surface computed the same quantity for the regions where a random landscape lies above a given height, on a grid of samples, and its counts are right only because they pair the rules in this way.

The honeycomb needs no choice #

On a hexagonal grid the problem never arises.

Hexagons meet three at a corner, never four, so no two cells meet at a point without also sharing an edge. There is no diagonal to argue about, and the six neighbours sharing an edge are the only sensible neighbours. With that single rule for the curve and for the rest, every one of the 82 simple closed curves among the 19 cells leaves exactly two pieces. The census sets aside 24 sets of three cells round a corner, in which each cell has two neighbours but nothing is enclosed — the honeycomb’s version of the $2\times2$ block.

This is the reason the hexagonal grid has long been advocated in image analysis, and the reason it appears in two classical places outside it. One is the board game Hex, played on a rhombus of hexagons, in which one player tries to join one pair of opposite sides and the other the other pair; a full board always has exactly one winner, and that is the honeycomb’s version of the Jordan curve theorem, a chain of one colour across the board being exactly what blocks every chain of the other. The other is percolation, the study of when a random scatter of open sites forms a path across, whose random-graph counterpart is the moment a giant appears. On the triangular lattice, whose sites are the honeycomb’s cells, a random colouring with each cell black or white at even odds is exactly balanced between the two colours, because black and white chains block each other with the same rule; the critical probability for crossing is exactly one half. On the square grid the two colours need different rules, and the thresholds differ: about $0.593$ for edge-neighbour crossings and $1 - 0.593 = 0.407$ for corner-neighbour ones, related by the same duality as the curves.

A paint bucket leaks through a diagonal step #

The practical form of all this is in every paint program.

The standard way to draw a straight line on a screen, Jack Bresenham’s algorithm of 1962, chooses at each step either to move along one axis or to move diagonally, and the lines it draws are connected only under the eight-neighbour rule. An outline built from such lines is a closed curve of corner-neighbours. A fill that spreads to all eight neighbours escapes through the first diagonal step, because the two pixels on either side of the step are diagonal neighbours of each other; a fill that spreads only to the four edge-neighbours stays inside. That is why the flood fill in graphics programs uses edge-neighbours by default — the mixed rule, chosen for practical reasons long before it was explained.

The pairing works the other way as well. An outline drawn with edge-neighbours only — thicker, with no diagonal steps — holds a fill that spreads through corners, and a fill through edges would be needlessly cautious.

What the census shows and what it cannot #

Every count here is exact: all $2^{20} - 1$ subsets of the square window, all $2^{19} - 1$ of the hexagonal one, and the complements broken into pieces by flood fill. The small window is the limitation. The theorem that every simple closed curve of corner-neighbours leaves exactly two edge-neighbour pieces is Rosenfeld’s, for curves of any size, and the census confirms it only up to the 4 by 5 window; it does find the failures of the same-rule pairings at the smallest size where they can occur, and those need no larger search, since one failure settles the matter.

The definition of a simple closed curve is also a choice, and other definitions exist. Some authors require at least eight pixels for an edge-neighbour curve, which removes the $2 \times 2$ blocks automatically; some require a minimum of four for a corner-neighbour curve, which the diamond of four pixels round one centre meets exactly. The theorem’s form does not depend on these details.

Still open: grids in three dimensions #

In three dimensions a voxel has six neighbours sharing a face, twelve more sharing only an edge and eight sharing only a corner, so there are three natural rules rather than two: 6, 18 and 26 neighbours. The digital form of the separation theorem — a closed surface of voxels divides space into exactly two pieces — needs paired rules again, (26, 6) or (6, 26) and, with care, (18, 6), and defining a digital surface so that the theorem holds turned out to be much harder than defining a digital curve. Several inequivalent definitions are in use in medical imaging, where the surfaces are organs extracted from scans, and none is both simple to test and complete. Which voxel sets ought to count as surfaces, and whether one definition can serve every application, is still argued, much as two pieces in every dimension found that separation survives the passage to higher dimensions while the tidier statements do not.

Who owns the corner #

The Jordan curve theorem on a square grid is a statement about corners. Where four pixels meet, the two on one diagonal and the two on the other cannot both be joined through the meeting point, and any rule for connectedness has to say which pair is. Give the curve the corners and the rest of the plane must go without; give the rest the corners and the curve must go without. With that settled, every closed curve has an inside and an outside, as in the continuous plane — and on a honeycomb, where no corner is shared by four cells, it never needs settling at all.