The idea: apply a rule to its own output
Start with a simple shape and a rule that turns a curve into a slightly more detailed curve. Apply the rule, then apply it again to the result, and again. Each pass is a level. After a few levels the curve has thousands of segments, and the picture stops changing much at the scale you can see, but it never stops changing in the small. The limit of these curves is a fractal: every small piece looks like a copy of the whole.
The page draws each level as one long path and colours it by position: red at the start, through yellow, green and blue, to violet at the end. A black dot marks the start and a ring the end. Each Next level shows the rule as a motion, in three steps: the parts that will change, the change itself, and the numbers for the new level.
| curve | level 0 | one level up | levels drawn |
|---|---|---|---|
| Koch snowflake | a triangle, side 1 | every segment → 4 segments, 1/3 as long | 0 … 6 (12 288 segments) |
| Heighway dragon | one segment | copy the curve, turn the copy 90° about the end | 0 … 14 (16 384 segments) |
| Hilbert curve | the centre of a square | 4 half-size copies, joined by 3 segments | 0 … 7 (16 383 segments) |
Koch snowflake: an endless boundary around a finite area
Cut every segment into thirds and replace the middle third by the two other sides of an equilateral triangle that points outward. One segment becomes 4 segments, each 1/3 as long, so each level multiplies the length by 4/3. Starting from a triangle with side 1:
segments = 3 · 4ⁿ segment length = 3⁻ⁿ perimeter = 3 · (4/3)ⁿ → ∞The area grows too, but less and less. Level k adds 3·4ᵏ⁻¹ small triangles, each 1/9ᵏ of the starting triangle. Add them all up as a geometric series with ratio 4/9:
area = 1 + (1/3)·(1 + 4/9 + (4/9)² + …) = 1 + (1/3) · 9/5 = 8/5 of the triangle
| level n | segments | segment length | perimeter | area (triangles) |
|---|---|---|---|---|
| 0 | 3 | 1 | 3 | 1 |
| 1 | 12 | 1/3 | 4 | 1.3333 |
| 2 | 48 | 1/9 | 5.333 | 1.4815 |
| 3 | 192 | 1/27 | 7.111 | 1.5473 |
| 4 | 768 | 1/81 | 9.481 | 1.5766 |
| 5 | 3 072 | 1/243 | 12.642 | 1.5896 |
| 6 | 12 288 | 1/729 | 16.856 | 1.5954 |
So the limit is a curve of infinite length that encloses a finite area. The page keeps the view fixed: the snowflake grows outward, and from level 4 on the changes are smaller than a pixel. (Demo: Koch snowflake, level 0 → 6, Demo: one Koch step up close (level 1 → 2).)
Heighway dragon: folding a strip of paper
Take the whole curve, copy it, and turn the copy 90° about the end point. The copy, read backwards, is the second half of the new curve, so the number of segments doubles: 2ⁿ segments. This is exactly what happens when you fold a strip of paper in half n times, always the same way, and then open every fold to a right angle. The end point the copy turns about becomes the middle corner of the new curve, just as the first fold you make ends up as the middle crease of the strip.
Reading the corners from the start gives the paper-folding sequence of right (R) and
left (L) turns: R R L R R L L R R R L L R L L …. Turn number k is decided by the odd part m of
k (k = 2ʲ·m): R when m leaves remainder 1 after division by 4, L when it leaves 3. The middle turn is
always R, and the second half is the first half read backwards with every turn flipped.
If the start and end stay 1 apart, each fold makes the segments √2 times shorter while there are twice as many, so the total length is (√2)ⁿ, which also grows without bound. The two halves only ever touch at corners and never cross. In the limit the dragon covers a region of the plane with positive area, so the curve has dimension 2, while the boundary of that region is a fractal of dimension about 1.524. Copies of the dragon fit together to tile the plane. (Demo: dragon curve, fold 0 → 14, Demo: one dragon fold up close (level 3 → 4).)
Hilbert curve: visiting every cell, in order
Level 1 is a U through the centres of the 4 quarters of a square. To go one level up, shrink the curve to half size and put a copy in each quarter: the two top copies as they are, the bottom-left copy flipped over the main diagonal and the bottom-right copy flipped over the other one. Now each copy ends next to where the next one starts, and 3 short segments join them.
cells = 4ⁿ segments = 4ⁿ − 1 segment length = 2⁻ⁿ length = 2ⁿ − 2⁻ⁿ → ∞The path never jumps: cells that are next to each other on the path are next to each other in the square, and a stretch of the path stays inside a small block of cells. That locality is why databases and maps sort 2-D points by their position on a Hilbert curve: points close on the curve are close on the map, so they end up close on disk. The simpler Z-order (Morton order) behind geohash jumps more often; see Quadtree and Geohash. In the limit the curve passes through every point of the square: a continuous curve that fills an area. (Demo: Hilbert curve fills the square, 0 → 7, Demo: Hilbert level 2 → 3: four copies, joined.)
Fractal dimension
Cut a line into pieces 1/2 as long and you get 2 copies; a square gives 4 = 2² copies; a cube 8 = 2³. The exponent is the dimension. For a shape made of N copies of itself, each scaled by r, the similarity dimension is
D = log N / log(1/r)| curve | copies N | scale r | D |
|---|---|---|---|
| Koch curve (one side) | 4 | 1/3 | log 4 / log 3 ≈ 1.262 |
| Heighway dragon | 2 | 1/√2 | log 2 / log √2 = 2 (its boundary ≈ 1.524) |
| Hilbert curve | 4 | 1/2 | log 4 / log 2 = 2 |
A dimension between 1 and 2 says the Koch curve is "more than a line, less than an area": it is too long to have a length and too thin to have an area. The dragon and the Hilbert curve reach 2: they fill area. Other fractals on this site: the Weierstrass function, a graph with no tangent anywhere, the chaos game, which draws the Sierpinski triangle with random jumps, and the Barnsley fern, built from four affine copies like the Hilbert curve. Recursion itself, one call inside another, is on Factorial.
What the page leaves out
Levels above 6, 14 and 7 (the segments would be smaller than a pixel), the Koch anti-snowflake and other angles, the twindragon and how dragons tile the plane, Peano's earlier space-filling curve and the Z-order curve, the formal limit (a uniform limit of continuous curves is continuous), how the boundary dimension 1.524 of the dragon is computed, and box-counting on real coastlines.