A space-filling curve (SFC) is, essentially, a line that bends through a space and hits every point. It was made possible by a proof created by Georg Cantor in the late 1800s. You can then map a coordinate in N-dimensions on to it to determine a single, identifying, scalar index. Google’s S2 library uses a specific SFC called a Hilbert curve (which is a fractal) and some other tricks to map geographic coordinates to a single 64-bit integer. This has the characteristic of assigning any coordinate within the same locality a very similar index; the closer the points are, the more of the prefix will be the same. Indeed, the difference between one SFC and another is, physically, how the curve bends and, ultimately, how it preserves locality. Hilbert is most popular for this though it is not the simplest SFC. For a list of various curves, look in the “See also” section of the Wikipedia page. Each of those references shows illustrations of what the curves look like.

As far as the index produced by S2, you can compare smaller, finer areas and larger, rougher areas by comparing a larger prefix or a smaller prefix, respectively. This not only allows you to easily search an index for places in a specific area but to also implicitly determine if one area contains another.

If you are interested in the mechanics of S2 (the Go version), the mapping magic happens in the following progression.

First, convert the LatLng to a Point (which just encapsulates a vector type provided by the R3 sibling project for three-dimensional coordinate systems):

func PointFromLatLng(ll LatLng) Point {
    phi := ll.Lat.Radians()
    theta := ll.Lng.Radians()
    cosphi := math.Cos(phi)
    return Point{r3.Vector{math.Cos(theta) * cosphi, math.Sin(theta) * cosphi, math.Sin(phi)}}
}

Second, convert the Point to face coordinates:

func cellIDFromPoint(p Point) CellID {
    f, u, v := xyzToFaceUV(r3.Vector{p.X, p.Y, p.Z})
    i := stToIJ(uvToST(u))
    j := stToIJ(uvToST(v))
    return cellIDFromFaceIJ(f, i, j)
}

Third, convert the face coordinates to the one-dimensional index (a 64-bit integer aliased as the CellID type):

func cellIDFromFaceIJ(f, i, j int) CellID {
    // Note that this value gets shifted one bit to the left at the end
    // of the function.
    n := uint64(f) <= 0; k-- {
        mask := (1 <>uint(k*lookupBits))&mask) <>uint(k*lookupBits))&mask) <>2) << (uint(k) * 2 * lookupBits)
        bits &= (swapMask | invertMask)
    }
    return CellID(n*2 + 1)
}

There is also the function that allows you to step along the curve, which is very inexpensive:

func (ci CellID) AdvanceWrap(steps int64) CellID {
    if steps == 0 {
        return ci
    }

    // We clamp the number of steps if necessary to ensure that we do not
    // advance past the End() or before the Begin() of this level.
    shift := uint(2*(maxLevel-ci.Level()) + 1)
    if steps > shift); steps > shift)
            steps %= wrap
            if steps > shift); steps > max {
            wrap := int64(wrapOffset >> shift)
            steps %= wrap
            if steps > max {
                steps -= wrap
            }
        }
    }

    // If steps is negative, then shifting it left has undefined behavior.
    // Cast to uint64 for a 2's complement answer.
    return CellID(uint64(ci) + (uint64(steps) << shift))
}

The S2 project has its own Hilbert implementation. To see an implementation that excludes all of the sphere mechanics (the presence of which makes things considerably more complicated), see Google’s hilbert (Go implementation) project.

Space-filling functions are a fantastically-useful method for clustering anything that you might have a requirement for, though you might need a mathematician to come up with a process to adjust your coordinates if they are not initially acceptable as inputs (the qualification of which might also require said mathematician). Also, SFCs are non-injective: The index that you get is not necessarily unique for any two coordinates, though, in such a situation, you are guaranteed that two coordinates resulting in an identical index would basically have to be very similar themselves (the accuracy of this depends on which SFC you use).

For reference, there also exists a reversible geographic-to-string conversion library called Geohash (also here). However, this does not use SFCs and, I believe, suffers from distortion either over the equator or for great distances though I am having trouble finding where I saw that, just now. The Hilbert/S2 approach does not have this problem.

Google’s S2, geometry on the sphere, cells and Hilbert curve (great article)

Space-filling curve

Peano curve (the first known space-filling curve)

Analysis of the Clustering Properties of Hilbert Space-filling Curve (paper)

Mapping N-dimensional value to a point on Hilbert curve (SO)

S2 (Go package)