Sierpiński Surface-Filling Coordinate

We're used to indicating positions on Earth (or on other planets or moons, or in the starry sky) with two coordinates: a longitude and a latitude. You first specify the one to the desired accuracy, and then the other. Until you have both of them, they are not of very much use.

In this document I show that we can indicate positions on Earth also with just one coordinate. That coordinate always indicates a compact region that is of about the same size in all horizontal directions. The more digits you get from that coordinate, the smaller the region becomes in which the location can lie, but it remains compact.

The ideas behind this coordinate come from the paper "Continuous Indexing of Hierarchical Subdivisions of the Globe" from 2000 by John J. Bartholdi, Ⅲ, and Paul Goldsman, which paper is available at http://www2.isye.gatech.edu/~jjb/mow/papers/hglobec.pdf.

1. Space-Filling Curves

A space-filling curve is a curve that passes roughly equally near every location in a space. Such a curve has a resolution, which is a measure of how close at least all locations are to the curve. In the limit of infinite resolution, the curve visits every location in the space.

Such a curve can be used to define a coordinate system in the space, in which only a single coordinate is needed to indicate a location, even if the space is an area or a volume for which usually two or three coordinates are used. The single coordinate is equal to the fraction of the length of the entire curve that must be traversed to get as near as possible to that location. That fraction gets ever closer to a fixed value as the resolution gets ever larger.

Space-filling curves are usually constructed from a template curve containing a small number of fairly equally distributed points connected by line segments. The curve must not intersect itself. You get the space-filling curve by scaling and rotating copies of the template curve and then connecting all of the copies in just the right way.

Each of the points is the center of an area of space for which that point is in some suitable sense the nearest one; We'll refer to that area as the point-related area. The point-related areas together cover the entire space, with no gaps and no overlap.

The template curve defines the space-filling curve at the first level. To get the next level of the curve, each of the line segments of the current curve is replaced by a suitably scaled and rotated copy of the template curve, in such a way that the curve as a whole remains connected and does not intersect itself. This corresponds to subdividing each point-related area.

Actually, for our purposes it is better to give the areas primacy over the points. To get to the next level, divide each of the areas into parts in such a way that a space-filling curve can be drawn through them with one point in each area.

Replacing ever smaller parts with copies of always the same template makes the space-filling curve self-similar. At infinite resolution, the space-filling curve is a fractal.

2. Sierpiński Triangles and Sierpiński Coordinates

The Sierpiński curves are a particular family of space-filling curves. They form the basis of a coordinate system on the surface of a sphere (such as the Earth), which I call Sierpiński coordinates. The point-related areas are spherical triangles, and each next level corresponds to dividing each of the triangles into two nearly equal smaller triangles. At every next level, the number of triangles doubles.

As a example, look at a particular level-18 Sierpiński triangle on Earth covering part of the Netherlands.

At the next level (level 19), that triangle is divided into two nearly equal parts.

And at level 20, each of the smaller triangles has itself been divided into two.

And likewise at level 21.

The Sierpiński curve through the level-21 triangles inside the level-18 triangle is shown below. We enter the level-18 triangle on the left, pass through the level-21 triangles in the order indicated by the Sierpiński curve, and leave the level-18 triangle at the lower right. This is the general pattern for every triangle: enter at the entry vertex, cover the interior, passing the median vertex halfway through, and exit at the exit vertex. The exit vertex of the previous triangle is the entry vertex of the next triangle.

We can keep moving to higher levels and greater resolution. Here are the level-24 triangles inside the level-18 triangle, and the Sierpiński curve through them.

At level 27, the triangles get very small at this scale.

so we show the corresponding Sierpiński curve by itself. The curve still enters the level-18 triangle at the left, passes near every location inside that triangle without crossing itself, and then leaves the triangle at the lower right.

3. Sierpiński Coordinate on a Sphere

The surface of a globe is not a triangle, so at the first few levels the Sierpiński areas aren't (spherical) triangles but rather segments. For convenience, I refer to all of them as triangles.

At level 1, the globe is divided into an eastern half and a western half. At level 2, each hemisphere is divided from pole to pole into two segments. At level 3, each of the segments is divided in two at the equator. The 8 areas that then divide the surface of globe are spherical triangles. At higher levels, each triangle is divided further, according to the Sierpiński surface-filling curve.

These triangles are shown in green in the following map of the Earth (in Mollweide projection). The number in the middle of each triangle is the decimal Sierpiński coordinate of the triangle. These are explained later. (I created this image using QGIS, using map data from Natural Earth.)

The following table shows, for the first 50 levels \(n\), the approximate average area \(A\) of a triangle at that level on Earth, the approximate angular radius \(ρ\) of the inscribed circle in the triangle, and the approximate linear radius \(L\) of the inscribed circle. The units are: 1 Mm² = 1 million km² ≈ 621 thousand sq mi, 1 km² ≈ 0.39 sq mi, 1 m² ≈ 10.8 sq ft, 1° = 60′, 1′ = 60″, 1 Mm = 1000 km ≈ 621 mi, 1 km = 1000 m ≈ 0.621 mi, 1 m = 1000 mm = 3.3 ft.

So, at level 30 each triangle has an area of about 1 km², and at level 40 each triangle has an area of about 930 m² (the same as a circle of 8.6 m radius).

3.1. Binary Coordinates

The Sierpiński coordinate ranges from 0 (at the North Pole) to 1 (back at the North Pole). If one traverses the triangles in the order of the coordinate, then one goes across the entire globe, without gaps and without overlap, until one ends up at the very first triangle again. Triangles with nearby coordinates tend to be nearby on the globe. A range of Sierpiński coordinate corresponds to a contiguous area on the globe.

Sierpiński coordinates are most precisely specified using binary numbers, because at each level the number of triangles doubles.

To make the distinction between binary fractional numbers and fractional numbers for other bases (e.g., decimal) more clear in the text below, we can prefix non-decimal fractionals with the base followed by a number sign "#", for example "2#" for binary numbers. If the base is clear from the context, then the prefix may be omitted.

At level 1, the areas are

Any location with a binary Sierpiński coordinate beginning (after the decimal point) with 0 is in the eastern hemisphere, and any location with a Sierpiński binary coordinate beginning (after the decimal point) with 1 is in the western hemisphere.

At level 2, the areas are

At level 3, the spherical triangles are

My standard notation for a binary Sierpiński coordinate is to omit the decimal point and anything before it, and to prefix a "b" to indicate its binary nature. So, Australia (near 140° east longitude, 35° south latitude) lies in the triangle designated b101. Germany (near 10° east longitude, 50° north latitude) lies in Sierpiński triangle b000. Chile (near 70° west longitude, and southern latitudes) lies in triangle b110.

Leading and trailing zeros are significant! Triangle b1 is not the same as triangle b01 or triangle b10. The more digits there are, the smaller the triangle is.

If a namespace must be indicated, then use "ssfc:" for "Sierpiński surface-filling coordinate". So, ssfc:b110 is a full designation of the level-3 triangle that contains Chile.

For binary Sierpiński coordinates, the coordinate of a larger triangle is the prefix of the coordinate of any of the smaller triangles that it contains. So, triangle b11011001 is contained within larger triangle b1101100, which itself is contained within even larger triangle b110110.

3.2. Octal Coordinates, Level Suffix

Sierpiński coordinates in binary format are somewhat unwieldy, because they get long rather quickly. Specifying a Sierpiński coordinate with sufficient precision to denote a triangle on Earth with an area of about 1 km² requires 30 binary digits, and a triangle of 1 m² requires 50 binary digits. For example, the binary Sierpiński coordinate of the level-30 triangle of about 1 km² that contains the Natural History Museum in Rotterdam is b000001111010001010001000111111.

For greater convenience, binary Sierpiński coordinates can be converted into octal (base 8), decimal (base 10), or hexadecimal (base 16) ones.

Each next group of three binary digits corresponds to one octal digit (0−7). The correspondence is as follows.

An octal Sierpiński coordinate is prefixed by an "o". So, Australia lies in b101 = o5, Germany lies in b000 = o0, and Chile lies in b110 = o6. The level-30 square kilometer containing the Natural History Museum in Rotterdam is at o0172121077.

An octal coordinate has roughly one third the number of digits that the corresponding binary coordinate has.

There is a problem with octal Sierpiński coordinates (and similarly with coordinates to any base except 2). What is the octal version of b10? That binary coordinate has two binary digits, but each octal number represents three binary digits. b10 represents the binary fraction 2#0.10 (= 1/2), to which corresponds the octal fraction 8#0.4 (= 4/8 = 1/2), which suggests o4, but o4 corresponds to b100, not b10. Region b10 includes regions b100 and b101.

To solve this problem, add a colon and the level number to the Sierpiński coordinate. We call that the level suffix. Region b10 is a level-2 region, because it requires 2 binary digits to specify, so its octal version is o4:2. Likewise, region b1 corresponds to o4:1, and region b100 corresponds to o4:3. If the level is a multiple of 3, so that the octal version has the correct precision already, then the level suffix may be omitted. So, region o4 = o4:3 = b100, and the octal Sierpiński coordinate of the square kilometer containing the Natural History Museum in Rotterdam needs no level suffix, because it is at level 30 which is a multiple of 3.

For octal Sierpiński coordinates, the coordinate of a larger triangle is the prefix of the coordinate of any of the smaller triangles that it contains, if the coordinates require no level to be specified. So, triangle o662 is contained within larger triangle o66, which itself is contained within even larger triangle o6.

3.3. Hexadecimal Coordinates

Each group of four binary digits corresponds to one hexadecimal digit (0−9 and a-f). The correspondence is as follows.

The letters a-f in a hexadecimal coordinate may be written in upper case or lower case as desired, without changing the meaning.

A hexadecimal Sierpiński coordinate is prefixed by an "x". For example, the central and western USA fall in b1000 = x8. A level suffix is needed for levels that are not multiples of 4. Australia lies in b101 = xa:3. The level-30 square kilometer containing the Natural History Museum in Rotterdam is at x07a288fc:30, and x07a288f is the level-28 triangle that includes it.

A hexadecimal coordinate has roughly one quarter the number of digits that the corresponding binary coordinate has, and is roughly 3/4 times as long as the corresponding octal coordinate.

For hexadecimal Sierpiński coordinates, the coordinate of a larger triangle is the prefix of the coordinate of any of the smaller triangles that it contains, if the coordinates require no level to be specified. So, triangle xd94 is contained within larger triangle xd9, which itself is contained within even larger triangle xd.

3.4. Decimal Coordinates

The correspondence between binary and decimal Sierpiński coordinates is less clear-cut, because 10 is not a power of 2. Each next decimal digit on average corresponds to about 3.32 additional binary digits.

To convert a binary Sierpiński coordinate to a decimal one, convert the binary fraction to a decimal fraction and truncate it at the minimum number of decimal digits that is needed to be able to distinguish between coordinates at the given level. See below for details.

Decimal Sierpiński coordinates may be prefixed by a "d", but that prefix is not required. A Sierpiński coordinate without a prefix is assumed to be a decimal one. A level suffix is needed if the maximum number of binary digits that can correspond to the number of decimal digits is not equal to the level.

For example, a level-3 Sierpiński coordinate has 3 binary digits. What decimal Sierpiński coordinate corresponds to b001? A 3-digit binary fractional number has a resolution of 1/2³ = 1/8: the smallest difference between any two different 3-digit binary fractionals is 1/8. A 1-digit decimal fractional has a resolution of 1/10¹ = 1/10, which is just less than 1/8, so we can use a different 1-digit decimal fractional to represent any 3-digit binary fractional.

b001 stands for 2#0.001, which means 1/8. That fraction is the nearest 3-digit (after the decimal point) binary fraction for all numbers in the range from 1/16 through 3/16, which are 0.0625 and 0.1875, respectively. The only 1-digit decimal fractional in that interval is 0.1, so that 1-digit decimal number corresponds to the 3-digit binary number 2#0.001, so b001 corresponds to d1, and d1 corresponds to b001.

Likewise, b010 stands for 2#0.010 = 2/8, which corresponds to the range from 3/16 through 5/16, which are 0.1875 and 0.3125, respectively. The 1-digit decimal fractionals 0.2 and 0.3 fall within that range, so either d2 or d3 can be used as a decimal representation of b010. If there are multiple choices like this, then we generally select the larger one. We refer to that choice as the canonical decimal Sierpiński coordinate.

All in all, the corresponding binary and decimal fractions and Sierpiński coordinates for all level-3 coordinates are:

so there is a different 1-digit decimal coordinate for every 3-digit binary coordinate, but some 3-digit binary coordinates have multiple possible 1-digit decimal coordinates.

The maximum number of binary digits that can be represented by the first couple of decimal digit counts are as follows:

So, a 33-digit binary coordinate can be represented by a 10-digit decimal one. If the level equals one of these binary digit counts, then the decimal Sierpiński coordinate needs no level indication. The level-29 triangle of 2 km² that includes the Natural History Museum in Rotterdam has decimal Sierpiński coordinate 029823838.

A decimal coordinate has roughly 30% as many digits as the corresponding binary coordinate.

For decimal Sierpiński coordinates, the canonical coordinate of a larger triangle is not necessarily the prefix of the canonical coordinate of any of the smaller triangles that it contains, even if the coordinates require no level to be specified. For example, triangle 02982394 = b00000111101000101000101011 contains triangle 029823957 = b00000111101000101000101011111, but the shorter decimal coordinate is not the prefix of the longer decimal coordinate. However, non-canonical coordinate 02982395 corresponds to the same triangle as canonical 02982394 and does prefix the smaller triangle's coordinate.

3.5. Index

Traversing the triangles at a specific level via the Sierpiński curve corresponds to starting at Sierpiński coordinate with all zeros at that level, and then incrementing the number (interpreted as a whole number) by one for each next triangle. At level \( n \) there are \( 2^n \) triangles.

For example, at level 6, we follow the Sierpiński curve when we travel through the triangles in the order o00, o01, o02, o03, o04, o05, o06, o07, o10, o11, and so on through o77, which is the last one before returning to o00, to which it is a neighbor.

We can indicate each triangle by its binary, octal, decimal, or hexadecimal Sierpiński coordinate, or by counting triangles from the first one. The decimal coordinate based on the count of triangles is called the Sierpiński index of the triangle.

The first triangle gets index 0, the next one gets 1, and so on until the last triangle (which leads back to triangle 0) which gets index number \( 2^n - 1 \). The standard notation for indicating a triangle by its index at a certain level is to prefix "i" to the index number. A level suffix is required for a Sierpiński index, because every index occurs at multiple levels. Triangle b010 corresponds to i2:3, and triangle b01 corresponds to i1:2.

For Sierpiński indexes the relationship between containing triangles is different than it was for Sierpiński coordinates. Smaller triangle \( i \) at level \( n \) is contained within larger triangle \( i/2 \) at level \( n - 1 \), which is contained within even larger triangle \( i/4 \) at level \( n - 2 \). Ignore the remainder from these divisions. For example, triangle i17:9 is contained within triangle i8:8, which itself is contained within triangle i4:7.

The square kilometer containing the Natural History Museum in Rotterdam has Sierpiński index i32023103:30.

3.6. Relative Coordinate

One can indicate a relative Sierpiński coordinate or index by appending a plus or minus sign and the integer offset to the base coordinate or index (after the level suffix, if any). The offset may be 0 and indicates how many triangles to advance (+) or retreat (−) along the Sierpiński curve from the one indicated by the base coordinate or index without the offset.

For example, the level-30 triangle including the Natural History Museum in Rotterdam is at o0172121077. The 100th triangle after that one is indicated by o0172121077+100. That triangle also has designation o0172121243, but to find that from the earlier one requires converting 100 from decimal to octal and then adding it to the original coordinate in octal, which is not all in a day's work for most people.

Even decimal relative Sierpiński coordinates are not easy to convert to the corresponding absolute (not relative) Sierpiński coordinates. 0298238387:30+100 corresponds to 0298239319:30, not to 0298238487:30 as you might think.

Relative Sierpiński indexes are easy to reduce to absolute Sierpiński indexes: just add the relative number to the index. i32023103:30+100 corresponds to i32023203:30.

3.7. Range

One can indicate a range of Sierpiński coordinates or indexes by concatenating two such coordinates or indexes (including a level suffix and an offset as needed or desired) separated by "..". The type of coordinate (binary, octal, decimal, or index) of the beginning and end of the range may differ. For example, b010..o5 indicates the range (combination) of four triangles starting with the one designated b010 = o2 and ending with the one designated b101 = o5.

If the beginning and end of the range do not specify or imply the same level, then the lesser of the two levels applies. So, o17..o226 is equivalent to o17..o22.

The type specifier of the end of the range may be omitted; It is then assumed the same as that of the range beginning. So, o17..o22 may be abbreviated to o17..22. If the end of the range is intended to be decimal but the beginning is not, then specify a "d" prefix for the end of the range. So, in 17..22 the range end is a decimal coordinate, just like the range beginning, but in o17..22 the range end is an octal coordinate, just like the range beginning. In o17..d22, the range beginning is octal but the range end is decimal.

If the range end is equal to the range beginning, ignoring any offsets on either, then the range end without the offset may be omitted. So, o17−4..o17+3 may be abbreviated to o17−4..+3 to indicate the range from 4 triangles before o17 through 3 triangles after o17.

Sierpiński coordinates wrap around to 0 when they reach their greatest possible value. If the range end indicates an earlier triangle (in the order of the Sierpiński curve) than the range beginning does, then the range runs from the range beginning triangle to the very last triangle, to the very first triangle, and then to the range ending triangle. For example, o6..1 contains triangles o6, o7, o0, and o1. One way to indicate the range of all triangles at level 17 is 0:17..−1, and likewise for other levels.

3.8. Summary

We've defined binary, octal, decimal, and hexadecimal Sierpiński coordinates, and the Sierpiński index. All of these indicate particular triangles on the globe, in a continuous sequence that cover the entire globe without gaps and without overlap. Two Sierpiński coordinates or indexes that are close together indicate triangles that are close together on the globe.

The various coordinates of the square kilometer containing the Natural History Museum in Rotterdam are:

4. Zooming in to the Natural History Museum in Rotterdam

The following sequence of images zooms in from the entire world to the Natural History Museum in Rotterdam, in steps of 3 levels, so that each triangle from the previous image is divided into 8 = 2³ triangles in the current image. The triangles are identified by their decimal Sierpiński coordinate.

We begin at level 3, where there are 8 triangles, each covering approximately 511 million km².

The number near the center of each triangle is the level-3 decimal canonical Sierpiński coordinate that identifies the triangle.

The curve passing through all of the triangles is the level-6 Sierpiński curve passing through the centers of all of the level-6 triangles in ascending order of the Sierpiński coordinate. That curve shows which vertex of the level-3 triangle is the entry vertex (where the curve enters the triangle), which is the median vertex (which is passed midway through the triangle), and which is the exit vertex (where the curve exits the triangle).

The triangle that is drawn thicker is the one containing the Museum.

A similar setup is used for the pictures for higher levels.

The level-3 Sierpiński curve is approximately 63 000 km long, which is 1.6 times the circumference of the Earth. The level-6 Sierpiński curve is approximately 151 000 km long, which is 3.8 times the circumference of the Earth.

Notice that there are gaps in the coordinate: Not every possible coordinate has a triangle of its own, because there are 10 possible one-digit numbers, but only 8 triangles. Coordinates 2 and 7 do not occur at this level.

We zoom in to level-3 triangle 0, and divide it into 8 level-6 sub-triangles. There are 64 level-6 triangles, each of which covers approximately 16 million km². The displayed level-9 Sierpiński curve passes through all level-6 triangles and is about 462 000 km long, which is more than the distance between the Earth and the Moon.

Then we zoom in to level-6 triangle 02, which covers much of northern and west-central Europe and a slice of Russia ending in the northwestern part of China. We divide it into 8 level-9 sub-triangles. There are 512 level-9 triangles, each of which covers approximately 2 million km². The displayed level-12 Sierpiński curve passes through all level-9 triangles and has a total length of approximately 1.31 million km.

We zoom in to level-9 triangle 029, which covers all of the Benelux, most of Germany, much of France, and some of Great-Britain, Poland, and the Czech Republic, and a tiny part of Denmark. We divide it into 8 level-12 triangles. There are 4096 level-12 triangles, each of which covers approximately 250 thousand km². The displayed level-15 Sierpiński curve passes trough all level-12 triangles and has a total length of about 3.8 million km,

Then we zoom in to level-12 triangle 0298:12, which covers most of the Netherlands and northwestern Germany. We divide it into 8 level-15 sub-triangles. There are 32 768 level-15 triangles, each of which covers approximately 31 thousand km². The displayed level-18 Sierpiński curve passes through all level-15 triangles and has a total length of approximately 10.6 million km.

Now we zoom in to level-15 triangle 02982:15, which covers a far-western part of the Netherlands and a small part of Belgium. We divide it into 8 level-18 sub-triangles. There are 262 144 level-18 triangles, each of which covers approximately 3900 km². The displayed level-21 Sierpiński curve passes through all level-18 triangles and has a total length of approximately 30 million km. From this level on, the background map data comes from OpenStreetMap.

We zoom in to level-18 triangle 029823:18, which covers part of the southwestern delta region of the Netherlands. We divide it into 8 level-21 sub-triangles. There are 2 097 152 level-21 triangles, each covering approximately 488 km². The displayed level-24 Sierpiński curve passes through all level-21 triangles and has a total length of approximately 85 million km, about half of the distance between the Earth and the Sun.

Then we zoom in to level-21 triangle 0298238:21, which reaches southwestward from central Rotterdam. We divide it into 8 level-24 sub-triangles. There are 16 777 216 level-24 triangles, each covering approximately 61 km². The displayed level-27 Sierpiński curve passes through all level-24 triangles and is approximately 240 million km long, longer than the distance between the Sun and the Earth.

Then we zoom in to level-24 triangle 02982378:24 which includes eastern Vlaardingen, Schiedam, and western Rotterdam. We divide it into 8 level-27 sub-triangles. There are 134 217 728 level-27 triangles, each covering approximately 7.6 km². The displayed level-30 Sierpiński curve passes through all level-27 triangles and is approximately 679 million km long.

Then we zoom in to level-27 triangle 029823832:27, which reaches westward from the Erasmus Bridge. We divide it into 8 level-30 sub-triangles. There are 1 073 741 824 level-30 triangles, each about 1.0 km² in size. The displayed level-33 Sierpiński curve passes through all level-30 triangles and is approximately 1.92 thousand million km long.

We zoom in to level-30 triangle 0298238387:30, which contains the Museum Park. We divide it into 8 level-33 sub-triangles. There are 8 589 934 592 level-33 triangles, each about 0.12 km² in size. The displayed level-36 Sierpiński curve passes through all level-33 triangles and is about 5.4 thousand million km long.

We zoom in to level-33 triangle 0298238392, which contains the southern end of the Museum Park and an eastern slice of the Erasmus Medical Center. We divide it into 8 level-36 sub-triangles. There are 68 719 476 736 level-36 triangles, each about 15 thousand m² in size. The displayed level-39 Sierpiński curve passes through all level-36 triangles and is about 15 thousand million km long.

We zoom in to level-36 triangle 02982383923, which contains the Natural History Museum and a large part of the park to the west of it. We divide the triangle into 8 level-39 sub-triangles. There are 549 755 813 888 level-39 triangles, each about 1900 m² in size. The displayed level-42 Sierpiński curve passes through all level-39 triangles and is approximately 43 thousand million km long. Level-39 triangle 029823839233 is mostly covered by the Natural History Museum in Rotterdam.

5. Converting from Sierpiński Coordinate to Latitude and Longitude

5.1. Converting from Sierpiński Coordinate to Binary Sierpiński Coordinate

5.1.1. Converting from Octal to Binary Sierpiński Coordinate

Converting an octal Sierpiński coordinate to a binary Sierpiński coordinate is simple: Replace every octal digit by the corresponding three binary digits, and truncate after the number of binary digits equal to the level of the coordinate.

5.1.2. Converting from Hexadecimal to Binary Sierpiński Coordinate

Converting a hexadecimal Sierpiński coordinate to a binary Sierpiński coordinate is simple: Replace every hexadecimal digit by the corresponding four binary digits, and truncate after the number of binary digits equal to the level of the coordinate.

5.1.3. Converting from Sierpiński Index to Binary Sierpiński Coordinate

Converting from a Sierpiński index to a binary Sierpiński coordinate is simple: Convert the decimal index into the corresponding binary number, and prefix 0s until the number of binary digits is equal to the level of the index.

5.1.4. Converting from Decimal to Binary Sierpiński Coordinate

Converting from a decimal Sierpiński coordinate is more difficult than the other conversions described above, because unlike 8 and 16, 10 is not a power of 2.

The first step is to determine the number of binary digits corresponding to the decimal coordinate. If the decimal coordinate includes a level suffix, then that determines the number of binary digits. If the decimal coordinate has \( d \) decimal digits and does not include a level suffix, then the number \( b \) of binary digits is the largest whole number such that \( 2^b \le 10^d \), which is equivalent to \( b\log_{10}(2) \le d \), which means

\[ b = \left\lfloor \frac{d}{\log_{10}(2)} \right\rfloor = \left\lfloor d\log_{2}(10) \right\rfloor \]

where \( \log_{10}(2) ≈ 0.30103001 \) and \( \log_{2}(10) = 1/\log_{10}(2) ≈ 3.321928 \).

If the decimal coordinate is \( D \), then it represents the fraction \( D/10^d \). We're looking for binary coordinate \( B \), which represents the fraction \( B/2^b \) that is nearest to \( D/10^d \). So

\[ B = \left[ \frac{D×2^b}{10^d} \right] = \left\lfloor \frac{D×2^b}{10^d} + \frac12 \right\rfloor = \left\lfloor \frac{D×2^b + \frac{1}{2}×10^d}{10^d} \right\rfloor \]

Now we have \( B \) but in base 10 (assuming we used a decimal calculator). To get the binary digits from left to right:

For each of the \( b \) binary digits,

1. Multiply \( B \) by \( b \) and call the result \( B \) again.
2. If \( B \) is less than \( 2^b \), then the next binary digit is 0. Otherwise, the next binary digit is 1 and you should subtract \( 2^b \) from \( B \) and call the result \( B \) again.

5.2. Convert from Binary Sierpiński Coordinate to Latitude and Longitude

Given a Sierpiński coordinate, convert to latitude and longitude as follows:

1. First, convert the Sierpiński coordinate to binary format, if it isn't a binary coordinate already.

2. Then, construct an initial triangle based on the first three binary digits, according to the following table.

   Octal	A	B	C
   000	(0,0,+1)	(0,+1,0)	(+1,0,0)
   001	(+1,0,0)	(0,+1,0)	(0,0,−1)
   010	(0,0,−1)	(0,+1,0)	(−1,0,0)
   011	(−1,0,0)	(0,+1,0)	(0,0,+1)
   100	(0,0,+1)	(0,−1,0)	(−1,0,0)
   101	(−1,0,0)	(0,−1,0)	(0,0,−1)
   110	(0,0,−1)	(0,−1,0)	(+1,0,0)
   111	(+1,0,0)	(0,−1,0)	(0,0,+1)

   The three numbers for each of the points A, B, and C are cartesian coordinates \(x, y, z\). Point (0,0,+1) is the north pole, point (+1,0,0) is at longitude 0 and latitude 0, and point (0,+1,0) is at longitude 90° east and latitude 0.

3. Then, for each next binary digit,

   1. Calculate the sum of points A and C and call it D.
   2. Calculate the length of D (of the line from the origin at (0,0,0) to point D), which is equal to \(r = \sqrt{x^2 + y^2 + z^2}\).
   3. Divide all of the coordinates of D by \( r \). Now D has length 1, just like A, B, and C have.
   4. If the current binary digit is 0, then set C equal to B. If the current binary digit is 1, then set A equal to B.
   5. Then set B equal to D.

4. When you've handled all of the binary digits, then you have found the vertices of the final triangle. Calculate the sum of points A, B, and C and call it E.
5. Calculate the length of E, which is equal to \(r = \sqrt{x^2 + y^2 + z^2}\).
6. The latitude of the center of the triangle is equal to \(φ = \arcsin(z/r)\)
7. The longitude of the center of the triangle is \(λ = \arctan(y,x)\) where \(\arctan\) is the special two-argument arc tangent function. \( \arctan(1,0) = 90° \) en \( \arctan(0,−1) = 180° \). If you don't have that function available, then instead use \(λ = \arctan(y/x)\) but add 180° if \( x \) is negative. If the result isn't between −180° and +180°, then you can add or subtract 360° until it is.

6. Converting from Latitude and Longitude to Sierpiński Coordinate

6.1. Converting from Binary Sierpiński Coordinate to Other Sierpiński Coordinates

6.1.1. Converting from Binary to Octal Sierpiński Coordinate

Converting a binary Sierpiński coordinate to an octal Sierpiński coordinate is simple: Append 0s until the number of binary digits is a multiple of 3, replace every three binary digits by the corresponding octal digit, and add a level suffix if the original number of binary digits wasn't a multiple of 3.

6.1.2. Converting from Binary to Hexadecimal Sierpiński Coordinate

Converting a binary Sierpiński coordinate to a hexadecimal Sierpiński coordinate is simple: Append 0s until the number of binary digits is a multiple of 4, replace every four binary digits by the corresponding hexadecimal digit, and add a level suffix if the original number of binary digits wasn't a multiple of 4.

6.1.3. Converting from Binary Sierpiński Coordinate to Sierpiński Index

Converting from a binary Sierpiński coordinate to a Sierpiński index is simple: Convert the binary number into the corresponding decimal number, and add a level suffix.

6.1.4. Converting from Binary to Decimal Sierpiński Coordinate

Converting to a decimal Sierpiński coordinate is more difficult than the other conversions described above, because unlike 8 and 16, 10 is not a power of 2.

The first step is to determine the number \( d \) of decimal digits corresponding to the \( b \) binary digits. That number \( d \) is the smallest whole number such that \( 2^b \le 10^d \), which is equivalent to \( b\log_{10}(2) \le d \), which means

\[ d = \left\lceil b \log_{10}(2) \right\rceil \]

where \( \log_{10}(2) ≈ 0.30103001 \).

However, the found number of decimal digits may correspond to more than \( b \) binary digits. The number \( b_2 \) of binary digits corresponding to \( d \) decimal digits is

\[ b_2 = \left\lfloor \frac{d}{\log_{10}(2)} \right\rfloor = \left\lfloor d\log_{2}(10) \right\rfloor \]

If \( b_2 \) differs from \( b \), then append 0s to the binary coordinate until it has \( b_2 \) binary digits, and add a level suffix (for level \( b \)) to the final decimal Sierpiński coordinate.

If the binary coordinate (with appended 0s as needed) is \( B \), then it represents the fraction \( B/2^{b_2} \). We're looking for decimal coordinate \( D \), which represents the fraction \( D/10^d \) that is nearest to \( B/2^{b_2} \). So

\[ D = \left[ \frac{B×10^d}{2^{b_2}} \right] = \left\lfloor \frac{B×10^d}{2^{b_2}} + \frac12 \right\rfloor = \left\lfloor \frac{B×10^d + \frac{1}{2}×2^{b_2}}{2^{b_2}} \right\rfloor \]

Now we have \( D \), except that it may be shorter than it should be because leading 0s are omitted. If \( D \) has fewer than \( d \) digits, then prefix sufficient 0s to make it have \( d \) digits.

And if \( b_2 ≠ b \), then a level suffix (for level \( b \)) must be added.

6.2. Convert from Latitude and Longitude to Binary Sierpiński Coordinate

Given latitude \( φ \) and longitude \( λ \) of a point P, convert to binary Sierpiński coordinate as follows:

1. Calculate the cartesian coordinates \( x, y, z \) of point P:

   \begin{align*} x & = \cos(λ) \cos(φ) \\ y & = \sin(λ) \cos(φ) \\ z & = \sin(φ) \end{align*}

2. Identify the first three binary digits from the signs of \(x, y, z\):

   \( x \)	\( y \)	\( z \)	Octant
   <0	<0	<0	101
   ≥0	<0	<0	110
   <0	≥0	<0	010
   ≥0	≥0	<0	001
   <0	<0	≥0	100
   ≥0	<0	≥0	111
   <0	≥0	≥0	011
   ≥0	≥0	≥0	000

   The "octant" provides the first three binary digits.

3. Find points A, B, and C corresponding to the octant, as in Sec. 5.2.
4. Then, for each next binary digit,

   1. Calculate the sum of points A and C and call it D.
   2. Calculate the length of D, which is equal to \( r = \sqrt{x^2 + y^2 + z^2} \) where \( x, y, z \) are the coordinates of D.
   3. Divide all of the coordinates of D by \( r \). Now D has length 1, just like A, B, and C have.
   4. Determine if point P is inside spherical triangle ABD: Calculate the determinant of the 3-by-3 matrix formed from P, A, and B (in that order), and of the matrix formed from P, B, and D, and of the matrix formed from P, D, and A. If all three of these determinants have the same sign, then the point is inside the spherical triangle.

      The determinant \( Δ \) of a 3-by-3 matrix is

      \begin{align*} Δ & = \det\left( \begin{matrix} a & d & g \\ b & e & h \\ c & f & i \end{matrix} \right) \\ & = a (ei - fh) - b (di - fg) + c (dh - eg) \end{align*}

   5. If P is inside that triangle, then the next binary digit is 0. Set C equal to B, and then set B equal to D.
   6. Otherwise, if P is not inside that triangle, then the next binary digit is 1. Set A equal to B, and then set B equal to D.

5. Keep going until you've reached the desired precision. One measure of that precision is half of the angle between A and C. That angle is 45° at level 3 and gets multiplied by on average a factor of ½√2 ≈ 0.7071068 for each next level, so the precision of level \( n \) is \( 90°× \left(\frac{1}{2}\right)^{n/2} \). If \( ρ_0 \) is the desired precision, then you achieve that at level \( n = \left\lceil 2×\log_2(90°/ρ_0) \right\rceil = \left\lceil 2×\log(90°/ρ_0)/\log(2) \right\rceil \).

© 2015 Louis Strous. I created the images in this paper using QGIS. I did all of the calculations that involve Sierpiński coordinates, using an application written by myself. The map data came from Natural Earth, OpenStreetMap, and Google Maps.