Identifying Nearest Major Cities

go-geographic-attractor is a new project that indexes world city and population data and can match a given coordinate to either the nearest major city or the nearest city (if no major city is near) in near-instantaneous time.

From the example:

// Load countries.

countryDataFilepath := path.Join(appPath, "test", "asset", "countryInfo.txt")

f, err := os.Open(countryDataFilepath)

defer f.Close()

countries, err := geoattractorparse.BuildGeonamesCountryMapping(f)

// Load cities.

gp := geoattractorparse.NewGeonamesParser(countries)

cityDataFilepath := path.Join(appPath, "index", "test", "asset", "allCountries.txt.detroit_area_handpicked")
g, err := os.Open(cityDataFilepath)

defer g.Close()

ci := NewCityIndex()

err = ci.Load(gp, g)

// Do the query.

clawsonCoordinates := []float64{42.53667, -83.15041}

sourceName, visits, cr, err := ci.Nearest(clawsonCoordinates[0], clawsonCoordinates[1])

// Print the results.

for _, vhi := range visits {
    fmt.Printf("%s: %s\n", vhi.Token, vhi.City)


fmt.Printf("Source: %s\n", sourceName)
fmt.Printf("ID: %s\n", cr.Id)
fmt.Printf("Country: %s\n", cr.Country)
fmt.Printf("City: %s\n", cr.City)
fmt.Printf("Population: %d\n", cr.Population)
fmt.Printf("Latitude: %.10f\n", cr.Latitude)
fmt.Printf("Longitude: %.10f\n", cr.Longitude)

go-exif-knife: One Exif Command-Line Tool to [Nearly] Rule Them All

go-exif-knife is a tool that will allow you to parse Exif from JPEG and PNG images and to do a brute-force parse of Exif embedded in any other format. You can cherry-pick specific IFDs or tags to print, and print them both as normal and JSON-formatted text. You can can also print parsed GPS data and timestamps and even produce a Google S2 geohash from the GPS data, and dump the thumbnail. If using JPEG or PNG, you can also update or add new Exif data.

This project is built on top of go-jpeg-image-structure, go-png-image-structure, and go-exif. PNG added support for Exif only in the last year, and this project was in service of providing useful Exif support for PNG.

Binary downloads are available here.



Space-Filling Curves to Map Multidimensional Data to a Single Dimension

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)