[GIS] TopoJSON: how to calculate scale and translate

pythontopojson

Context:

I'm using the topojson file format along with d3. Since I could not find a library in Python that handles this format, I'm writing one. I've got the topojson to other formats working.

Question:

When converting other formats to topojson, how do I calculate the ideal value for the topojson transforms scale and translate?

In order to save space (among other tricks), the format uses relative integer offsets from the previous point. For example, this is the topojson file for Aruba:

{
  "type": "Topology",
  "transform": {
    "scale": [0.036003600360036005, 0.017361589674592462],
    "translate": [-180, -89.99892578124998]
  },
  "objects": {
    "aruba": {
      "type": "Polygon",
      "arcs": [[0]],
      "id": 533
    }
  },
  "arcs": [
    [[3058, 5901], [0, -2], [-2, 1], [-1, 3], [-2, 3], [0, 3], [1, 1], 
     [1, -3], [2, -5], [1, -1]]
  ]
}

The same information as a GeoJSON feature looks like this:

{
    "type" : "Feature",
    "id" : 533,
    "properties" : {},
    "geometry" : {
        "type" : "Polygon",
        "coordinates" : [[
                 [-69.9009900990099, 12.451814888520133], 
                 [-69.9009900990099, 12.417091709170947], 
                 [-69.97299729972997, 12.43445329884554], 
                 [-70.00900090009, 12.486538067869319], 
                 [-70.08100810081008, 12.538622836893097], 
                 [-70.08100810081008, 12.590707605916876], 
                 [-70.04500450045005, 12.608069195591469], 
                 [-70.00900090009, 12.55598442656769], 
                 [-69.93699369936994, 12.469176478194726], 
                 [-69.9009900990099, 12.451814888520133]
            ]]
    }
}

It is easy to see how the former is more compact than the later. In order to obtain the absolute coordinates, the function is:

def arc_to_coordinates(topology, arc):
    scale = topology['transform']['scale']
    translate = topology['transform']['translate']

    x = 0
    y = 0
    coordinates = []

    for point in arc:
        x += point[0]
        y += point[1]
        coordinates.append([
            x * scale[0] + translate[0],
            y * scale[1] + translate[1] 
        ])

    return coordinates

Reading topojson is easy enough:

>>> arc_to_coordinates(topology, topology['arcs'][0])
[[-69.9009900990099, 12.451814888520133],
 [-69.9009900990099, 12.417091709170947],
 [-69.97299729972997, 12.43445329884554],
 [-70.00900090009, 12.486538067869319],
 [-70.08100810081008, 12.538622836893097],
 [-70.08100810081008, 12.590707605916876],
 [-70.04500450045005, 12.608069195591469],
 [-70.00900090009, 12.55598442656769],
 [-69.93699369936994, 12.469176478194726],
 [-69.9009900990099, 12.451814888520133]]

Update:

Reading Mike Bostock's code, I saw this:

kx = ((Q - 1) / (x1 - x0)) if x1 - x0 else 1
ky = ((Q - 1) / (y1 - y0)) if y1 - y0 else 1
...
scale = [1/kx, 1/ky]

In the example, given the bounding box in the form (x0, y0, x1, y1), Q seems to be around 6 and 12 for the values [0.036003600360036005, 0.017361589674592462].

>>> x0, y0, x1, y1
(-70.08100810081008, 12.417091709170947, -69.9009900990099, 12.608069195591469)
>>> Q = 6
>>> 1 / ((Q - 1) / (x1 - x0))
0.036003600360035644
>>> Q = 12
>>> 1/ ((Q - 1) / (y1 - y0))
0.017361589674592892

I know the Q has to do with quantization, any idea where the Q values near 6 and 12 came from?

Best Answer

In Python

"Functions that extract GeoJSON-ish data structures from TopoJSON (https://github.com/mbostock/topojson) topology data.

Author: Sean Gillies (https://github.com/sgillies)"

Example:

from itertools import chain

def rel2abs(arc, scale=None, translate=None):
    """Yields absolute coordinate tuples from a delta-encoded arc.

    If either the scale or translate parameter evaluate to False, yield the
    arc coordinates with no transformation."""
    if scale and translate:
        a, b = 0, 0
        for ax, bx in arc:
            a += ax
            b += bx
            yield scale[0]*a + translate[0], scale[1]*b + translate[1]
    else:
        for x, y in arc:
            yield x, y

https://github.com/sgillies/topojson/blob/master/topojson.py

Related Question