Hilbert Map V

README.md

This experiment concludes the Hilbert Map series (1, 2, 3, 4). The level of detail has been added in order to show quad tiles only when a certain zoom level has been reached.

index.coffee

# Random data construction
n_class = Array(Math.ceil(Math.random()*10)).fill()
data = n_class.map (d,i) -> {name: "class#{i+1}", size: Math.ceil(Math.random()*100000)}

order = Math.ceil(Math.log(d3.sum(data, (d) -> d.size)) / Math.log(4))

### INITIALIZATION
###
start = 0
scale = 480
precision_multiplier = 10000
tile_size = scale*precision_multiplier/Math.pow(2, order)

### regions DATA
###
data.forEach (cls) ->
  # START, END, Z offsets calculation
  cls.start = start
  cls.end = start + cls.size
  start += cls.size

  cls.z = get_z cls
  cls.quads = get_quads cls, order

data.forEach (d) ->
  quads = d.quads.map quad_layout(hquad, scale*precision_multiplier)
  quads.forEach (i) ->
    i.name = d.name
  d._quads = quads

features = []

data.forEach (d) ->
  cpr = new ClipperLib.Clipper()
  squares = new ClipperLib.Paths()
  merge = new ClipperLib.Paths()

  squares = d._quads.map (q) -> [{X: q.x, Y: q.y}, {X: q.x+q.dx, Y: q.y}, {X: q.x+q.dx, Y: q.y+q.dy}, {X: q.x, Y: q.y+q.dy}]

  cpr.AddPaths(squares, ClipperLib.PolyType.ptSubject, true)
  succeeded = cpr.Execute(ClipperLib.ClipType.ctUnion, merge)

  features.push {
    type: "Feature",
    geometry: {
      type: "Polygon",
      coordinates: [(merge[0].map (q) -> [q.X, q.Y]).concat([[merge[0][0].X, merge[0][0].Y]])]
      },
    properties: {
      class: d.name
      }
  }

collection = {
  collection: {
    type: "FeatureCollection",
    features: features
    }
  }

### tiles DATA
###
data_tiles = []

data.forEach (d) ->
  tiles = []

  for n in [d.start...d.end]
    n_4 = (n).toString(4)
    tiles.push Array(order - n_4.length + 1).join('0') + n_4

  tiles = tiles.map(quad_layout(hquad, scale*precision_multiplier))
  tiles.forEach (t) ->
    t.name = d.name
  data_tiles = data_tiles.concat tiles

### VISUALIZATION
###
svg = d3.select 'svg'

width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

svg
  .attr
    width: width
    height: height

# zoom
zoomable_layer = svg.append('g')
zoom = d3.behavior.zoom()
  .scaleExtent([1, Infinity])
  .on 'zoom', () ->
    zoomable_layer
      .attr
        transform: "translate(#{zoom.translate()})scale(#{zoom.scale()})"
    lod(zoom.translate(), zoom.scale())
svg.call(zoom)

vis = zoomable_layer.append 'g'
  .attr
    transform: "translate(#{(width-scale)/2}, #{(height-scale)/2}) scale(#{1/precision_multiplier})"

# SVG groups
legend = svg.append 'g'

regions_group = vis.append 'g'

tiles_group = vis.append 'g'

# other functions
color = d3.scale.category10()

path_generator = d3.geo.path()
  .projection null

### tiles VISUALIZATION
###
redraw_tiles = (x_start, x_end, y_start, y_end) ->
  if not x_start?
    _data_tiles = []
  else
    _data_tiles = data_tiles.filter (d) -> x_start-d.dx <= d.x+d.dx/2 and x_end+d.dx >= d.x+d.dx/2 and y_start-d.dy <= d.y+d.dy/2 and y_end+d.dy >= d.y+d.dy/2
  
  tiles = tiles_group.selectAll '.tile'
    .data _data_tiles

  tiles.enter().append 'rect'
    .attr
      class: 'tile'

  tiles
    .attr
      x: (d) -> d.x
      y: (d) -> d.y
      width: (d) -> d.dx
      height: (d) -> d.dy
      fill: (d) -> color d.name
    .append 'title'
      .html (d) -> "#{d.name}<br>#{d.digits}"

  tiles.exit().remove()

### regions VISUALIZATION
###
topology = topojson.server.topology(collection, {'coordinate-system': 'cartesian', quantization: 0, 'property-transform': (feature) -> feature.properties})

regions = regions_group.selectAll '.region'
  .data data.map (d) -> d.name

regions.enter().append 'path'
  .attr
    class: 'region'
    d: (d) -> path_generator topojson.client.merge(topology, topology.objects.collection.geometries.filter((g) -> g.properties.class is d))
    fill: (d) -> color d

# Legend
legend_items = legend.selectAll '.legend_item'
  .data data

legend_items.enter().append 'g'
  .attr
    class: 'legend_item'

legend_items.append 'rect'
  .attr
    x: 10
    y: (d,i) -> 10 + i*15
    width: (d) -> 10
    height: (d) -> 10
    fill: (d) -> color d.name

legend_items.append 'text'
  .attr
    x: 30
    y: (d,i) -> 15 + i*15
    dy: '0.35em'
  .text (d) -> d3.format(',d')(d.size)

### Viewport and Level of details
###
lod = (translation, z) ->
  x = (-(width-scale)/2-translation[0]/z) * precision_multiplier
  y = (-(height-scale)/2-translation[1]/z) * precision_multiplier
  dx = width*precision_multiplier/z
  dy = height*precision_multiplier/z

  if tile_size*10 > dx
    redraw_tiles(x, x+dx, y, y+dy)
  else
    redraw_tiles()

lod([0,0], 1)

index.css

html, body {
  padding: 0;
  margin: 0;
  height: 100%;
  overflow: hidden;
  font-family: sans-serif;
}

svg {
  width: 100%;
  height: 100%;
}

rect {
  stroke: #fff;
  stroke-width: 0.5px;
  vector-effect: non-scaling-stroke;
}

text {
  pointer-events: none;
}

.region {
  stroke: #333;
  shape-rendering: crispEdges;
  vector-effect: non-scaling-stroke;
}
.tile {
  stroke: #000;
}
.legend_item {
  font-size: 12px;
}

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <script src="http://d3js.org/d3.v3.min.js"></script>
  <script src="http://jsclipper.sourceforge.net/6.1.3.1/clipper.js"></script>
  <script src="quad_utils.js"></script>
  <script src="topojsonAll.js"></script>
  <link rel="stylesheet" href="index.css">
  <title></title>
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var collection, color, data, data_tiles, features, height, legend, legend_items, lod, n_class, order, path_generator, precision_multiplier, redraw_tiles, regions, regions_group, scale, start, svg, tile_size, tiles_group, topology, vis, width, zoom, zoomable_layer;

  n_class = Array(Math.ceil(Math.random() * 10)).fill();

  data = n_class.map(function(d, i) {
    return {
      name: "class" + (i + 1),
      size: Math.ceil(Math.random() * 100000)
    };
  });

  order = Math.ceil(Math.log(d3.sum(data, function(d) {
    return d.size;
  })) / Math.log(4));


  /* INITIALIZATION
   */

  start = 0;

  scale = 480;

  precision_multiplier = 10000;

  tile_size = scale * precision_multiplier / Math.pow(2, order);


  /* regions DATA
   */

  data.forEach(function(cls) {
    cls.start = start;
    cls.end = start + cls.size;
    start += cls.size;
    cls.z = get_z(cls);
    return cls.quads = get_quads(cls, order);
  });

  data.forEach(function(d) {
    var quads;
    quads = d.quads.map(quad_layout(hquad, scale * precision_multiplier));
    quads.forEach(function(i) {
      return i.name = d.name;
    });
    return d._quads = quads;
  });

  features = [];

  data.forEach(function(d) {
    var cpr, merge, squares, succeeded;
    cpr = new ClipperLib.Clipper();
    squares = new ClipperLib.Paths();
    merge = new ClipperLib.Paths();
    squares = d._quads.map(function(q) {
      return [
        {
          X: q.x,
          Y: q.y
        }, {
          X: q.x + q.dx,
          Y: q.y
        }, {
          X: q.x + q.dx,
          Y: q.y + q.dy
        }, {
          X: q.x,
          Y: q.y + q.dy
        }
      ];
    });
    cpr.AddPaths(squares, ClipperLib.PolyType.ptSubject, true);
    succeeded = cpr.Execute(ClipperLib.ClipType.ctUnion, merge);
    return features.push({
      type: "Feature",
      geometry: {
        type: "Polygon",
        coordinates: [
          (merge[0].map(function(q) {
            return [q.X, q.Y];
          })).concat([[merge[0][0].X, merge[0][0].Y]])
        ]
      },
      properties: {
        "class": d.name
      }
    });
  });

  collection = {
    collection: {
      type: "FeatureCollection",
      features: features
    }
  };


  /* tiles DATA
   */

  data_tiles = [];

  data.forEach(function(d) {
    var j, n, n_4, ref, ref1, tiles;
    tiles = [];
    for (n = j = ref = d.start, ref1 = d.end; ref <= ref1 ? j < ref1 : j > ref1; n = ref <= ref1 ? ++j : --j) {
      n_4 = n.toString(4);
      tiles.push(Array(order - n_4.length + 1).join('0') + n_4);
    }
    tiles = tiles.map(quad_layout(hquad, scale * precision_multiplier));
    tiles.forEach(function(t) {
      return t.name = d.name;
    });
    return data_tiles = data_tiles.concat(tiles);
  });


  /* VISUALIZATION
   */

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  svg.attr({
    width: width,
    height: height
  });

  zoomable_layer = svg.append('g');

  zoom = d3.behavior.zoom().scaleExtent([1, Infinity]).on('zoom', function() {
    zoomable_layer.attr({
      transform: "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")"
    });
    return lod(zoom.translate(), zoom.scale());
  });

  svg.call(zoom);

  vis = zoomable_layer.append('g').attr({
    transform: "translate(" + ((width - scale) / 2) + ", " + ((height - scale) / 2) + ") scale(" + (1 / precision_multiplier) + ")"
  });

  legend = svg.append('g');

  regions_group = vis.append('g');

  tiles_group = vis.append('g');

  color = d3.scale.category10();

  path_generator = d3.geo.path().projection(null);


  /* tiles VISUALIZATION
   */

  redraw_tiles = function(x_start, x_end, y_start, y_end) {
    var _data_tiles, tiles;
    if (x_start == null) {
      _data_tiles = [];
    } else {
      _data_tiles = data_tiles.filter(function(d) {
        return x_start - d.dx <= d.x + d.dx / 2 && x_end + d.dx >= d.x + d.dx / 2 && y_start - d.dy <= d.y + d.dy / 2 && y_end + d.dy >= d.y + d.dy / 2;
      });
    }
    tiles = tiles_group.selectAll('.tile').data(_data_tiles);
    tiles.enter().append('rect').attr({
      "class": 'tile'
    });
    tiles.attr({
      x: function(d) {
        return d.x;
      },
      y: function(d) {
        return d.y;
      },
      width: function(d) {
        return d.dx;
      },
      height: function(d) {
        return d.dy;
      },
      fill: function(d) {
        return color(d.name);
      }
    }).append('title').html(function(d) {
      return d.name + "<br>" + d.digits;
    });
    return tiles.exit().remove();
  };


  /* regions VISUALIZATION
   */

  topology = topojson.server.topology(collection, {
    'coordinate-system': 'cartesian',
    quantization: 0,
    'property-transform': function(feature) {
      return feature.properties;
    }
  });

  regions = regions_group.selectAll('.region').data(data.map(function(d) {
    return d.name;
  }));

  regions.enter().append('path').attr({
    "class": 'region',
    d: function(d) {
      return path_generator(topojson.client.merge(topology, topology.objects.collection.geometries.filter(function(g) {
        return g.properties["class"] === d;
      })));
    },
    fill: function(d) {
      return color(d);
    }
  });

  legend_items = legend.selectAll('.legend_item').data(data);

  legend_items.enter().append('g').attr({
    "class": 'legend_item'
  });

  legend_items.append('rect').attr({
    x: 10,
    y: function(d, i) {
      return 10 + i * 15;
    },
    width: function(d) {
      return 10;
    },
    height: function(d) {
      return 10;
    },
    fill: function(d) {
      return color(d.name);
    }
  });

  legend_items.append('text').attr({
    x: 30,
    y: function(d, i) {
      return 15 + i * 15;
    },
    dy: '0.35em'
  }).text(function(d) {
    return d3.format(',d')(d.size);
  });


  /* Viewport and Level of details
   */

  lod = function(translation, z) {
    var dx, dy, x, y;
    x = (-(width - scale) / 2 - translation[0] / z) * precision_multiplier;
    y = (-(height - scale) / 2 - translation[1] / z) * precision_multiplier;
    dx = width * precision_multiplier / z;
    dy = height * precision_multiplier / z;
    if (tile_size * 10 > dx) {
      return redraw_tiles(x, x + dx, y, y + dy);
    } else {
      return redraw_tiles();
    }
  };

  lod([0, 0], 1);

}).call(this);

quad_utils.coffee

window.sizeify = (n) ->
  #if typeof n is 'string'
  if !n.children?
    n.n = 0
    n.size = 1
    return 1
  else
    n.size = 0
    n.children.forEach (c) ->
      n.size += sizeify(c)

    # expand to fill a square
    n.n = Math.ceil(Math.log(n.size)/Math.log(4))
    n.size = Math.pow(4,n.n)

    return n.size

window.quad_layout = (mapping, size) ->

  return (digits) ->
    m = mapping digits

    return {
      x: m.j/Math.pow(2,m.n)*size,
      y: m.i/Math.pow(2,m.n)*size,
      dx: 1/Math.pow(2,m.n)*size,
      dy: 1/Math.pow(2,m.n)*size,
      digits: m.digits
    }

window.hquad = (digits) ->
  n = digits.length
  l = 1
  i = 0
  j = 0

  for d in digits by -1
    switch d
      when '0'
        i_temp = i
        i = j
        j = i_temp
      when '1'
        i += l
      when '2'
        i += l
        j += l
      when '3'
        i_temp = i
        i = l - j - 1
        j = 2*l - i_temp - 1

    l = 2*l

  return {
    j: j,
    i: i,
    n: n,
    digits: digits
  }

window.quad = (digits) ->
  n = digits.length
  l = 1
  i = 0
  j = 0

  for d in digits by -1
    switch d
      when '1'
        j += l
      when '2'
        i += l
      when '3'
        i += l
        j += l

    l = 2*l

  return {
    j: j,
    i: i,
    n: n,
    digits: digits
  }

window.get_quad_code = (offset, N, n) ->
  b4 = offset.toString(4)
  b4 = Array(N-b4.length+1).join('0') + b4
  b4 = b4[0...N-n]
  return b4

window.get_quads = (cls, order) ->
  quads = []

  # START to Z range
  if cls.start isnt cls.z
    offset = cls.start
    start_to_z = (cls.z - cls.start).toString(4).split('').reverse().join('')

    for d,i in start_to_z
      for j in [0...parseInt(d)]
        digits = start_to_z.length - (start_to_z.length - i)

        quad = get_quad_code offset, order, digits
        quads.push quad

        offset += parseInt('1' + Array(digits + 1).join('0'), 4)

  # Z to END range
  offset = cls.z
  z_to_end = (cls.end - cls.z).toString(4)

  for d,i in z_to_end
    for j in [0...parseInt(d)]
      digits = z_to_end.length - i - 1

      quad = get_quad_code offset, order, digits
      quads.push quad

      offset += parseInt('1' + Array(z_to_end.length - i).join('0'), 4)

  return quads

window.get_z = (d) ->
  start_4 = (d.start).toString(4)
  end_4 = (d.end).toString(4)

  if start_4 is '0'
    return parseInt(start_4, 4)

  i = start_4.length - 1
  initial_i = start_4.length - 1
  while start_4.length <= end_4.length
    # zero the i-th digit
    new_start_4 = replace_char start_4, i, '0'
    # plus one the (i-1)th digit
    new_start_4 = (parseInt('1' + Array(new_start_4.length - i + 1).join('0'), 4)+parseInt(new_start_4, 4)).toString(4)

    if parseInt(new_start_4, 4) < d.end
      start_4 = new_start_4
    else
      break

    if initial_i is start_4.length
      i -= 1
    else
      initial_i += 1

  return parseInt(start_4, 4)

window.replace_char = (s, index, new_char) ->
  s.substr(0, index) + new_char + s.substr(index + 1)

quad_utils.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.sizeify = function(n) {
    if (n.children == null) {
      n.n = 0;
      n.size = 1;
      return 1;
    } else {
      n.size = 0;
      n.children.forEach(function(c) {
        return n.size += sizeify(c);
      });
      n.n = Math.ceil(Math.log(n.size) / Math.log(4));
      n.size = Math.pow(4, n.n);
      return n.size;
    }
  };

  window.quad_layout = function(mapping, size) {
    return function(digits) {
      var m;
      m = mapping(digits);
      return {
        x: m.j / Math.pow(2, m.n) * size,
        y: m.i / Math.pow(2, m.n) * size,
        dx: 1 / Math.pow(2, m.n) * size,
        dy: 1 / Math.pow(2, m.n) * size,
        digits: m.digits
      };
    };
  };

  window.hquad = function(digits) {
    var d, i, i_temp, j, k, l, n;
    n = digits.length;
    l = 1;
    i = 0;
    j = 0;
    for (k = digits.length - 1; k >= 0; k += -1) {
      d = digits[k];
      switch (d) {
        case '0':
          i_temp = i;
          i = j;
          j = i_temp;
          break;
        case '1':
          i += l;
          break;
        case '2':
          i += l;
          j += l;
          break;
        case '3':
          i_temp = i;
          i = l - j - 1;
          j = 2 * l - i_temp - 1;
      }
      l = 2 * l;
    }
    return {
      j: j,
      i: i,
      n: n,
      digits: digits
    };
  };

  window.quad = function(digits) {
    var d, i, j, k, l, n;
    n = digits.length;
    l = 1;
    i = 0;
    j = 0;
    for (k = digits.length - 1; k >= 0; k += -1) {
      d = digits[k];
      switch (d) {
        case '1':
          j += l;
          break;
        case '2':
          i += l;
          break;
        case '3':
          i += l;
          j += l;
      }
      l = 2 * l;
    }
    return {
      j: j,
      i: i,
      n: n,
      digits: digits
    };
  };

  window.get_quad_code = function(offset, N, n) {
    var b4;
    b4 = offset.toString(4);
    b4 = Array(N - b4.length + 1).join('0') + b4;
    b4 = b4.slice(0, N - n);
    return b4;
  };

  window.get_quads = function(cls, order) {
    var d, digits, i, j, k, len, len1, o, offset, p, q, quad, quads, ref, ref1, start_to_z, z_to_end;
    quads = [];
    if (cls.start !== cls.z) {
      offset = cls.start;
      start_to_z = (cls.z - cls.start).toString(4).split('').reverse().join('');
      for (i = k = 0, len = start_to_z.length; k < len; i = ++k) {
        d = start_to_z[i];
        for (j = o = 0, ref = parseInt(d); 0 <= ref ? o < ref : o > ref; j = 0 <= ref ? ++o : --o) {
          digits = start_to_z.length - (start_to_z.length - i);
          quad = get_quad_code(offset, order, digits);
          quads.push(quad);
          offset += parseInt('1' + Array(digits + 1).join('0'), 4);
        }
      }
    }
    offset = cls.z;
    z_to_end = (cls.end - cls.z).toString(4);
    for (i = p = 0, len1 = z_to_end.length; p < len1; i = ++p) {
      d = z_to_end[i];
      for (j = q = 0, ref1 = parseInt(d); 0 <= ref1 ? q < ref1 : q > ref1; j = 0 <= ref1 ? ++q : --q) {
        digits = z_to_end.length - i - 1;
        quad = get_quad_code(offset, order, digits);
        quads.push(quad);
        offset += parseInt('1' + Array(z_to_end.length - i).join('0'), 4);
      }
    }
    return quads;
  };

  window.get_z = function(d) {
    var end_4, i, initial_i, new_start_4, start_4;
    start_4 = d.start.toString(4);
    end_4 = d.end.toString(4);
    if (start_4 === '0') {
      return parseInt(start_4, 4);
    }
    i = start_4.length - 1;
    initial_i = start_4.length - 1;
    while (start_4.length <= end_4.length) {
      new_start_4 = replace_char(start_4, i, '0');
      new_start_4 = (parseInt('1' + Array(new_start_4.length - i + 1).join('0'), 4) + parseInt(new_start_4, 4)).toString(4);
      if (parseInt(new_start_4, 4) < d.end) {
        start_4 = new_start_4;
      } else {
        break;
      }
      if (initial_i === start_4.length) {
        i -= 1;
      } else {
        initial_i += 1;
      }
    }
    return parseInt(start_4, 4);
  };

  window.replace_char = function(s, index, new_char) {
    return s.substr(0, index) + new_char + s.substr(index + 1);
  };

}).call(this);

thumbnail.png

topojsonAll.js

!function n(t,r,o){function e(a,u){if(!r[a]){if(!t[a]){var c="function"==typeof require&&require;if(!u&&c)return c(a,!0);if(i)return i(a,!0);var s=new Error("Cannot find module '"+a+"'");throw s.code="MODULE_NOT_FOUND",s}var f=r[a]={exports:{}};t[a][0].call(f.exports,function(n){var r=t[a][1][n];return e(r?r:n)},f,f.exports,n,t,r,o)}return r[a].exports}for(var i="function"==typeof require&&require,a=0;a<o.length;a++)e(o[a]);return e}({1:[function(n,t,r){function o(){f&&u&&(f=!1,u.length?s=u.concat(s):l=-1,s.length&&e())}function e(){if(!f){var n=setTimeout(o);f=!0;for(var t=s.length;t;){for(u=s,s=[];++l<t;)u&&u[l].run();l=-1,t=s.length}u=null,f=!1,clearTimeout(n)}}function i(n,t){this.fun=n,this.array=t}function a(){}var u,c=t.exports={},s=[],f=!1,l=-1;c.nextTick=function(n){var t=new Array(arguments.length-1);if(arguments.length>1)for(var r=1;r<arguments.length;r++)t[r-1]=arguments[r];s.push(new i(n,t)),1!==s.length||f||setTimeout(e,0)},i.prototype.run=function(){this.fun.apply(null,this.array)},c.title="browser",c.browser=!0,c.env={},c.argv=[],c.version="",c.versions={},c.on=a,c.addListener=a,c.once=a,c.off=a,c.removeListener=a,c.removeAllListeners=a,c.emit=a,c.binding=function(n){throw new Error("process.binding is not supported")},c.cwd=function(){return"/"},c.chdir=function(n){throw new Error("process.chdir is not supported")},c.umask=function(){return 0}},{}],2:[function(n,t,r){!function(n,o){"object"==typeof r&&"undefined"!=typeof t?o(r):"function"==typeof define&&define.amd?define(["exports"],o):o(n.topojson=n.topojson||{})}(this,function(n){"use strict";function t(){}function r(n){if(!n)return t;var r,o,e=n.scale[0],i=n.scale[1],a=n.translate[0],u=n.translate[1];return function(n,t){t||(r=o=0),n[0]=(r+=n[0])*e+a,n[1]=(o+=n[1])*i+u}}function o(n){if(!n)return t;var r,o,e=n.scale[0],i=n.scale[1],a=n.translate[0],u=n.translate[1];return function(n,t){t||(r=o=0);var c=Math.round((n[0]-a)/e),s=Math.round((n[1]-u)/i);n[0]=c-r,n[1]=s-o,r=c,o=s}}function e(n,t){for(var r,o=n.length,e=o-t;e<--o;)r=n[e],n[e++]=n[o],n[o]=r}function i(n,t){for(var r=0,o=n.length;o>r;){var e=r+o>>>1;n[e]<t?r=e+1:o=e}return r}function a(n,t){return"GeometryCollection"===t.type?{type:"FeatureCollection",features:t.geometries.map(function(t){return u(n,t)})}:u(n,t)}function u(n,t){var r={type:"Feature",id:t.id,properties:t.properties||{},geometry:c(n,t)};return null==t.id&&delete r.id,r}function c(n,t){function o(n,t){t.length&&t.pop();for(var r,o=l[0>n?~n:n],i=0,a=o.length;a>i;++i)t.push(r=o[i].slice()),f(r,i);0>n&&e(t,a)}function i(n){return n=n.slice(),f(n,0),n}function a(n){for(var t=[],r=0,e=n.length;e>r;++r)o(n[r],t);return t.length<2&&t.push(t[0].slice()),t}function u(n){for(var t=a(n);t.length<4;)t.push(t[0].slice());return t}function c(n){return n.map(u)}function s(n){var t=n.type;return"GeometryCollection"===t?{type:t,geometries:n.geometries.map(s)}:t in h?{type:t,coordinates:h[t](n)}:null}var f=r(n.transform),l=n.arcs,h={Point:function(n){return i(n.coordinates)},MultiPoint:function(n){return n.coordinates.map(i)},LineString:function(n){return a(n.arcs)},MultiLineString:function(n){return n.arcs.map(a)},Polygon:function(n){return c(n.arcs)},MultiPolygon:function(n){return n.arcs.map(c)}};return s(t)}function s(n,t){function r(t){var r,o=n.arcs[0>t?~t:t],e=o[0];return n.transform?(r=[0,0],o.forEach(function(n){r[0]+=n[0],r[1]+=n[1]})):r=o[o.length-1],0>t?[r,e]:[e,r]}function o(n,t){for(var r in n){var o=n[r];delete t[o.start],delete o.start,delete o.end,o.forEach(function(n){e[0>n?~n:n]=1}),u.push(o)}}var e={},i={},a={},u=[],c=-1;return t.forEach(function(r,o){var e,i=n.arcs[0>r?~r:r];i.length<3&&!i[1][0]&&!i[1][1]&&(e=t[++c],t[c]=r,t[o]=e)}),t.forEach(function(n){var t,o,e=r(n),u=e[0],c=e[1];if(t=a[u])if(delete a[t.end],t.push(n),t.end=c,o=i[c]){delete i[o.start];var s=o===t?t:t.concat(o);i[s.start=t.start]=a[s.end=o.end]=s}else i[t.start]=a[t.end]=t;else if(t=i[c])if(delete i[t.start],t.unshift(n),t.start=u,o=a[u]){delete a[o.end];var f=o===t?t:o.concat(t);i[f.start=o.start]=a[f.end=t.end]=f}else i[t.start]=a[t.end]=t;else t=[n],i[t.start=u]=a[t.end=c]=t}),o(a,i),o(i,a),t.forEach(function(n){e[0>n?~n:n]||u.push([n])}),u}function f(n){return c(n,l.apply(this,arguments))}function l(n,t,r){function o(n){var t=0>n?~n:n;(f[t]||(f[t]=[])).push({i:n,g:c})}function e(n){n.forEach(o)}function i(n){n.forEach(e)}function a(n){"GeometryCollection"===n.type?n.geometries.forEach(a):n.type in l&&(c=n,l[n.type](n.arcs))}var u=[];if(arguments.length>1){var c,f=[],l={LineString:e,MultiLineString:i,Polygon:i,MultiPolygon:function(n){n.forEach(i)}};a(t),f.forEach(arguments.length<3?function(n){u.push(n[0].i)}:function(n){r(n[0].g,n[n.length-1].g)&&u.push(n[0].i)})}else for(var h=0,p=n.arcs.length;p>h;++h)u.push(h);return{type:"MultiLineString",arcs:s(n,u)}}function h(n){var t=n[0],r=n[1],o=n[2];return Math.abs((t[0]-o[0])*(r[1]-t[1])-(t[0]-r[0])*(o[1]-t[1]))}function p(n){for(var t,r=-1,o=n.length,e=n[o-1],i=0;++r<o;)t=e,e=n[r],i+=t[0]*e[1]-t[1]*e[0];return i/2}function g(n){return c(n,v.apply(this,arguments))}function v(n,t){function r(n){n.forEach(function(t){t.forEach(function(t){(e[t=0>t?~t:t]||(e[t]=[])).push(n)})}),i.push(n)}function o(t){return Math.abs(p(c(n,{type:"Polygon",arcs:[t]}).coordinates[0]))}var e={},i=[],a=[];return t.forEach(function(n){"Polygon"===n.type?r(n.arcs):"MultiPolygon"===n.type&&n.arcs.forEach(r)}),i.forEach(function(n){if(!n._){var t=[],r=[n];for(n._=1,a.push(t);n=r.pop();)t.push(n),n.forEach(function(n){n.forEach(function(n){e[0>n?~n:n].forEach(function(n){n._||(n._=1,r.push(n))})})})}}),i.forEach(function(n){delete n._}),{type:"MultiPolygon",arcs:a.map(function(t){var r,i=[];if(t.forEach(function(n){n.forEach(function(n){n.forEach(function(n){e[0>n?~n:n].length<2&&i.push(n)})})}),i=s(n,i),(r=i.length)>1)for(var a,u,c=1,f=o(i[0]);r>c;++c)(a=o(i[c]))>f&&(u=i[0],i[0]=i[c],i[c]=u,f=a);return i})}}function d(n){function t(n,t){n.forEach(function(n){0>n&&(n=~n);var r=e[n];r?r.push(t):e[n]=[t]})}function r(n,r){n.forEach(function(n){t(n,r)})}function o(n,t){"GeometryCollection"===n.type?n.geometries.forEach(function(n){o(n,t)}):n.type in u&&u[n.type](n.arcs,t)}var e={},a=n.map(function(){return[]}),u={LineString:t,MultiLineString:r,Polygon:r,MultiPolygon:function(n,t){n.forEach(function(n){r(n,t)})}};n.forEach(o);for(var c in e)for(var s=e[c],f=s.length,l=0;f>l;++l)for(var h=l+1;f>h;++h){var p,g=s[l],v=s[h];(p=a[g])[c=i(p,v)]!==v&&p.splice(c,0,v),(p=a[v])[c=i(p,g)]!==g&&p.splice(c,0,g)}return a}function y(n,t){return n[1][2]-t[1][2]}function m(){function n(n,t){for(;t>0;){var r=(t+1>>1)-1,e=o[r];if(y(n,e)>=0)break;o[e._=t]=e,o[n._=t=r]=n}}function t(n,t){for(;;){var r=t+1<<1,i=r-1,a=t,u=o[a];if(e>i&&y(o[i],u)<0&&(u=o[a=i]),e>r&&y(o[r],u)<0&&(u=o[a=r]),a===t)break;o[u._=t]=u,o[n._=t=a]=n}}var r={},o=[],e=0;return r.push=function(t){return n(o[t._=e]=t,e++),e},r.pop=function(){if(!(0>=e)){var n,r=o[0];return--e>0&&(n=o[e],t(o[n._=0]=n,0)),r}},r.remove=function(r){var i,a=r._;if(o[a]===r)return a!==--e&&(i=o[e],(y(i,r)<0?n:t)(o[i._=a]=i,a)),a},r}function M(n,t){function e(n){u.remove(n),n[1][2]=t(n),u.push(n)}var i=r(n.transform),a=o(n.transform),u=m();return t||(t=h),n.arcs.forEach(function(n){var r,o,c,s,f=[],l=0;for(o=0,c=n.length;c>o;++o)s=n[o],i(n[o]=[s[0],s[1],1/0],o);for(o=1,c=n.length-1;c>o;++o)r=n.slice(o-1,o+2),r[1][2]=t(r),f.push(r),u.push(r);for(o=0,c=f.length;c>o;++o)r=f[o],r.previous=f[o-1],r.next=f[o+1];for(;r=u.pop();){var h=r.previous,p=r.next;r[1][2]<l?r[1][2]=l:l=r[1][2],h&&(h.next=p,h[2]=r[2],e(h)),p&&(p.previous=h,p[0]=r[0],e(p))}n.forEach(a)}),n}var b="1.6.26";n.version=b,n.mesh=f,n.meshArcs=l,n.merge=g,n.mergeArcs=v,n.feature=a,n.neighbors=d,n.presimplify=M})},{}],3:[function(n,t,r){t.exports=function(n){function t(n){n&&s.hasOwnProperty(n.type)&&s[n.type](n)}function r(n){var t=n[0],r=n[1];i>t&&(i=t),t>u&&(u=t),a>r&&(a=r),r>c&&(c=r)}function o(n){n.forEach(r)}function e(n){n.forEach(o)}var i=1/0,a=1/0,u=-(1/0),c=-(1/0),s={GeometryCollection:function(n){n.geometries.forEach(t)},Point:function(n){r(n.coordinates)},MultiPoint:function(n){n.coordinates.forEach(r)},LineString:function(n){o(n.coordinates)},MultiLineString:function(n){n.coordinates.forEach(o)},Polygon:function(n){n.coordinates.forEach(o)},MultiPolygon:function(n){n.coordinates.forEach(e)}};for(var f in n)t(n[f]);return[i,a,u,c]}},{}],4:[function(n,t,r){function o(n){return n.toString()}function e(n){for(var t,r=-1,o=n.length,e=n[o-1],i=0;++r<o;)t=e,e=n[r],i+=t[0]*e[1]-t[1]*e[0];return.5*i}function i(n){return Math.abs((n[0][0]-n[2][0])*(n[1][1]-n[0][1])-(n[0][0]-n[1][0])*(n[2][1]-n[0][1]))}function a(n,t,r,o){var e=n-r,i=t-o;return Math.sqrt(e*e+i*i)}r.name="cartesian",r.formatDistance=o,r.ringArea=e,r.absoluteArea=Math.abs,r.triangleArea=i,r.distance=a},{}],5:[function(n,t,r){function o(n,t){function r(n){n.reverse()}var o=null;t&&"coordinate-system"in t&&(o=c[t["coordinate-system"]]);var e=i(o.ringArea,r);u({LineString:a,MultiLineString:a,Point:a,MultiPoint:a,Polygon:function(n){e(n.coordinates)},MultiPolygon:function(n){n.coordinates.forEach(e)}}).object(n)}function e(n,t){function r(t){return e.ringArea(s.feature(n,{type:"Polygon",arcs:[t]}).geometry.coordinates[0])}function o(n){var t=-1,r=n.length;for(n.reverse();++t<r;)n[t]=~n[t]}var e=null;t&&"coordinate-system"in t&&(e=c[t["coordinate-system"]]);var f=i(r,o),l=u({LineString:a,MultiLineString:a,Point:a,MultiPoint:a,Polygon:function(n){f(n.arcs)},MultiPolygon:function(n){n.arcs.forEach(f)}});for(var h in n.objects)l.object(n.objects[h])}function i(n,t){return function(r){if(o=r.length){for(var o,e,i,a,u=new Array(o),c=-(1/0),s=0;o>s;++s){var i=Math.abs(u[s]=n(r[s]));i>c&&(c=i,e=s)}e&&(a=r[e],r[e]=r[0],r[0]=a,a=u[e],u[e]=u[0],u[0]=a),u[0]<0&&t(r[0]);for(var s=1;o>s;++s)u[s]>0&&t(r[s])}}}function a(){}var u=n("./type"),c=n("./coordinate-systems"),s=n("../../build/topojson");t.exports=function(n,t){"Topology"===n.type?e(n,t):o(n,t)}},{"../../build/topojson":2,"./coordinate-systems":7,"./type":30}],6:[function(n,t,r){t.exports=function(n,t){function r(n){n&&e.hasOwnProperty(n.type)&&e[n.type](n)}function o(n){var r=t(n);null==r?delete n.id:n.id=r}arguments.length<2&&(t=function(n){return n.id});var e={Feature:o,FeatureCollection:function(n){n.features.forEach(o)}};for(var i in n)r(n[i]);return n}},{}],7:[function(n,t,r){t.exports={cartesian:n("./cartesian"),spherical:n("./spherical")}},{"./cartesian":4,"./spherical":17}],8:[function(n,t,r){t.exports=function(n){for(var t=n.arcs,r=-1,o=t.length;++r<o;)for(var e,i,a=t[r],u=0,c=a.length,s=a[0],f=s[0],l=s[1];++u<c;)s=a[u],e=s[0],i=s[1],a[u]=[e-f,i-l],f=e,l=i;return n}},{}],9:[function(n,t,r){function o(){}function e(){return!1}var i=n("./type"),a=n("./prune"),u=n("./clockwise"),c=n("./coordinate-systems"),s=n("../../build/topojson");t.exports=function(n,t){function r(n){return n.length&&f(n[0])?[n.shift()].concat(n.filter(l)):null}function f(n){return y(n)||g.absoluteArea(h(n))>=p}function l(n){return y(n)||g.absoluteArea(-h(n))>=p}function h(t){return g.ringArea(s.feature(n,{type:"Polygon",arcs:[t]}).geometry.coordinates[0])}var p,g=null,v=!0,d=!0,y=e;if(t&&("coordinate-system"in t&&(g=c[t["coordinate-system"]]),"minimum-area"in t&&(p=+t["minimum-area"]),"preserve-attached"in t&&(d=!!t["preserve-attached"]),"force-clockwise"in t&&(v=!!t["force-clockwise"])),v&&u(n,t),p>0||(p=Number.MIN_VALUE),d){var m={},M=0,b=i({LineString:o,MultiLineString:o,Point:o,MultiPoint:o,MultiPolygon:function(n){for(var t=n.arcs,r=-1,o=t.length;++r<o;)this.polygon(t[r])},Polygon:function(n){this.polygon(n.arcs)},polygon:function(n){for(var t=0,r=n.length;r>t;++t,++M)for(var o=n[t],e=0,i=o.length;i>e;++e){var a=o[e];0>a&&(a=~a);var u=m[a];u>=0&&u!==M?m[a]=-1:m[a]=M}}});y=function(n){for(var t=0,r=n.length;r>t;++t){var o=n[t];if(m[0>o?~o:o]<0)return!0}};for(var P in n.objects)b.object(n.objects[P])}var w=i({LineString:o,MultiLineString:o,Point:o,MultiPoint:o,Polygon:function(n){n.arcs=r(n.arcs),n.arcs&&n.arcs.length||(n.type=null,delete n.arcs)},MultiPolygon:function(n){n.arcs=n.arcs.map(r).filter(function(n){return n&&n.length}),n.arcs.length||(n.type=null,delete n.arcs)},GeometryCollection:function(n){this.defaults.GeometryCollection.call(this,n),n.geometries=n.geometries.filter(function(n){return null!=n.type}),n.geometries.length||(n.type=null,delete n.geometries)}});for(var P in n.objects)w.object(n.objects[P]);a(n,t)}},{"../../build/topojson":2,"./clockwise":5,"./coordinate-systems":7,"./prune":13,"./type":30}],10:[function(n,t,r){t.exports=function(n){function t(n){return(n&&e.hasOwnProperty(n.type)?e[n.type]:o)(n)}function r(n){var t=n.geometry;return null==t?n.type=null:(o(t),n.type=t.type,t.geometries?n.geometries=t.geometries:t.coordinates&&(n.coordinates=t.coordinates)),delete n.geometry,n}function o(n){return n?(i.hasOwnProperty(n.type)&&i[n.type](n),n):{type:null}}var e={Feature:r,FeatureCollection:function(n){return n.type="GeometryCollection",n.geometries=n.features,n.features.forEach(r),delete n.features,n}},i={GeometryCollection:function(n){for(var t=n.geometries,r=-1,e=t.length;++r<e;)t[r]=o(t[r])},MultiPoint:function(n){n.coordinates.length?n.coordinates.length<2&&(n.type="Point",n.coordinates=n.coordinates[0]):(n.type=null,delete n.coordinates)},LineString:function(n){n.coordinates.length||(n.type=null,delete n.coordinates)},MultiLineString:function(n){for(var t=n.coordinates,r=0,o=0,e=t.length;e>r;++r){var i=t[r];i.length&&(t[o++]=i)}o?2>o?(n.type="LineString",n.coordinates=t[0]):n.coordinates.length=o:(n.type=null,delete n.coordinates)},Polygon:function(n){for(var t=n.coordinates,r=0,o=0,e=t.length;e>r;++r){var i=t[r];i.length&&(t[o++]=i)}o?n.coordinates.length=o:(n.type=null,delete n.coordinates)},MultiPolygon:function(n){for(var t=n.coordinates,r=0,o=0,e=t.length;e>r;++r){for(var i=t[r],a=0,u=0,c=i.length;c>a;++a){var s=i[a];s.length&&(i[u++]=s)}u&&(i.length=u,t[o++]=i)}o?2>o?(n.type="Polygon",n.coordinates=t[0]):t.length=o:(n.type=null,delete n.coordinates)}};for(var a in n)n[a]=t(n[a]);return n}},{}],11:[function(n,t,r){var o=n("./quantize");t.exports=function(n,t,r){function e(n){n&&g.hasOwnProperty(n.type)&&g[n.type](n)}if(t){if(r===t||!n.bbox.every(isFinite))return n;var i=r/t,a=o(0,0,i,i);n.transform.scale[0]/=i,n.transform.scale[1]/=i}else{var u=n.bbox,c=isFinite(u[0])?u[0]:0,s=isFinite(u[1])?u[1]:0,f=isFinite(u[2])?u[2]:0,l=isFinite(u[3])?u[3]:0,h=f-c?(r-1)/(f-c):1,p=l-s?(r-1)/(l-s):1,a=o(-c,-s,h,p);n.transform=a.transform}var g={GeometryCollection:function(n){n.geometries.forEach(e)},Point:function(n){a.point(n.coordinates)},MultiPoint:function(n){n.coordinates.forEach(a.point)}};for(var v in n.objects)e(n.objects[v]);return n.arcs=n.arcs.map(function(n){return a.line(n=n.map(function(n){return n.slice()})),n.length<2&&n.push(n[0]),n}),n}},{"./quantize":14}],12:[function(n,t,r){var o=n("./quantize");t.exports=function(n,t,r,e){function i(n){n&&p.hasOwnProperty(n.type)&&p[n.type](n)}arguments.length<4&&(e=r);var a=isFinite(t[0])?t[0]:0,u=isFinite(t[1])?t[1]:0,c=isFinite(t[2])?t[2]:0,s=isFinite(t[3])?t[3]:0,f=c-a?(e-1)/(c-a)*r/e:1,l=s-u?(e-1)/(s-u)*r/e:1,h=o(-a,-u,f,l),p={GeometryCollection:function(n){n.geometries.forEach(i)},Point:function(n){h.point(n.coordinates)},MultiPoint:function(n){n.coordinates.forEach(h.point)},LineString:function(n){var t=n.coordinates;h.line(t),t.length<2&&(t[1]=t[0])},MultiLineString:function(n){for(var t=n.coordinates,r=0,o=t.length;o>r;++r){var e=t[r];h.line(e),e.length<2&&(e[1]=e[0])}},Polygon:function(n){for(var t=n.coordinates,r=0,o=t.length;o>r;++r){var e=t[r];for(h.line(e);e.length<4;)e.push(e[0])}},MultiPolygon:function(n){for(var t=n.coordinates,r=0,o=t.length;o>r;++r)for(var e=t[r],i=0,a=e.length;a>i;++i){var u=e[i];for(h.line(u);u.length<4;)u.push(u[0])}}};for(var g in n)i(n[g]);return h.transform}},{"./quantize":14}],13:[function(n,t,r){(function(n){t.exports=function(t,r){function o(n){n&&p.hasOwnProperty(n.type)&&p[n.type](n)}function e(n){for(var t=0,r=n.length;r>t;++t){var o,e=n[t],i=0>e&&(e=~e,!0);null==(o=h[e])&&(h[e]=o=l++,f[o]=c[e]),n[t]=i?~o:o}}function i(n){n.forEach(e)}var a=!1,u=t.objects,c=t.arcs,s=c.length,f=t.arcs=[],l=0,h=new Array(c.length);r&&"verbose"in r&&(a=!!r.verbose);var p={GeometryCollection:function(n){n.geometries.forEach(o)},LineString:function(n){e(n.arcs)},MultiLineString:function(n){n.arcs.forEach(e)},Polygon:function(n){n.arcs.forEach(e)},MultiPolygon:function(n){n.arcs.forEach(i)}};for(var g in u)o(u[g]);return a&&n.stderr.write("prune: retained "+l+" / "+s+" arcs ("+Math.round(l/s*100)+"%)\n"),t}}).call(this,n("_process"))},{_process:1}],14:[function(n,t,r){t.exports=function(n,t,r,o){function e(e){return e[0]=Math.round((e[0]+n)*r),e[1]=Math.round((e[1]+t)*o),e}function i(n){for(var t,r,o,i=0,a=1,u=n.length,c=e(n[0]),s=c[0],f=c[1];++i<u;)c=e(n[i]),r=c[0],o=c[1],r===s&&o===f||(t=n[a++],t[0]=s=r,t[1]=f=o);n.length=a}return{point:e,line:i,transform:{scale:[1/r,1/o],translate:[-n,-t]}}}},{}],15:[function(n,t,r){function o(){}var e=n("./type");t.exports=function(n,t){function r(n){return[n[0]*s+(i/2-p*s)+u,n[1]*d+(a/2-g*d)+u]}var i,a,u=0,c=!0;t&&("width"in t&&(i=+t.width),"height"in t&&(a=+t.height),"margin"in t&&(u=+t.margin),"invert"in t&&(c=!!t.invert));var s,f=n.bbox,l=f[2]-f[0],h=f[3]-f[1],p=(f[2]+f[0])/2,g=(f[3]+f[1])/2;i=Math.max(0,i-2*u),a=Math.max(0,a-2*u),i&&a?s=Math.min(i/l,a/h):i?(s=i/l,a=s*h):(s=a/h,i=s*l);var v,d=c?-s:s,y=r([f[0],f[1]]),m=r([f[2],f[3]]);if(n.bbox=c?[y[0],m[1],m[0],y[1]]:[y[0],y[1],m[0],m[1]],v=n.transform)v.scale[0]*=s,v.scale[1]*=d,v.translate[0]=i/2+u-(p-v.translate[0])*s,v.translate[1]=a/2+u-(g-v.translate[1])*d;else{var M=e({LineString:o,MultiLineString:o,Point:function(n){n.coordinates=r(n.coordinates)},MultiPoint:function(n){n.coordinates=n.coordinates.map(r)},Polygon:o,MultiPolygon:o});for(var b in n.objects)M.object(n.objects[b]);n.arcs=n.arcs.map(function(n){return n.map(r)})}return n}},{"./type":30}],16:[function(n,t,r){(function(r){var o=n("../../build/topojson"),e=n("./coordinate-systems");t.exports=function(n,t){var i,a=0,u=!1,c=null,s=n.arcs.reduce(function(n,t){return n+t.length},0),f=0;if(t&&("minimum-area"in t&&(a=+t["minimum-area"]),"coordinate-system"in t&&(c=e[t["coordinate-system"]]),"retain-proportion"in t&&(i=+t["retain-proportion"]),"verbose"in t&&(u=!!t.verbose)),o.presimplify(n,c.triangleArea),i){var l=[];n.arcs.forEach(function(n){n.forEach(function(n){isFinite(n[2])&&l.push(n[2])})});var h=l.length;t["minimum-area"]=a=h?l.sort(function(n,t){return t-n})[Math.max(0,Math.ceil((s-1)*i+h-s))]:0,u&&r.stderr.write("simplification: effective minimum area "+a.toPrecision(3)+"\n")}return n.arcs.forEach(n.transform?function(n){for(var t,r,o=0,e=0,i=-1,u=-1,c=n.length;++i<c;)t=n[i],t[2]>=a?(r=n[++u],r[0]=t[0]+o,r[1]=t[1]+e,o=e=0):(o+=t[0],e+=t[1]);n.length=++u}:function(n){for(var t,r=-1,o=-1,e=n.length;++r<e;)t=n[r],t[2]>=a&&(n[++o]=t);n.length=++o}),n.arcs.forEach(n.transform?function(n){var t=0,r=0,o=n.length,e=n[0];for(e.length=2;++t<o;)e=n[t],e.length=2,(e[0]||e[1])&&(n[++r]=e);f+=n.length=(r||1)+1}:function(n){var t,r,o=0,e=0,i=n.length,a=n[0],u=a[0],c=a[1];for(a.length=2;++o<i;)a=n[o],t=a[0],r=a[1],a.length=2,u===t&&c===r||(n[++e]=a,u=t,c=r);f+=n.length=(e||1)+1}),u&&r.stderr.write("simplification: retained "+f+" / "+s+" points ("+Math.round(f/s*100)+"%)\n"),n}}).call(this,n("_process"))},{"../../build/topojson":2,"./coordinate-systems":7,_process:1}],17:[function(n,t,r){function o(n){var t=n*h*6371;return(t>1?t.toFixed(3)+"km":(1e3*t).toPrecision(3)+"m")+" ("+n.toPrecision(3)+"°)"}function e(n){if(!n.length)return 0;for(var t=0,r=n[0],o=r[0]*h,e=r[1]*h/2+l,i=o,a=Math.cos(e),u=Math.sin(e),c=1,s=n.length;s>c;++c){r=n[c],o=r[0]*h,e=r[1]*h/2+l;var p=o-i,g=Math.cos(e),v=Math.sin(e),d=u*v,y=a*g+d*Math.cos(p),m=d*Math.sin(p);t+=Math.atan2(m,y),i=o,a=g,u=v}return 2*(t>f?t-2*f:-f>t?t+2*f:t)}function i(n){return 0>n?n+4*f:n}function a(n){var t=u(n[0],n[1]),r=u(n[1],n[2]),o=u(n[2],n[0]),e=(t+r+o)/2;return 4*Math.atan(Math.sqrt(Math.max(0,Math.tan(e/2)*Math.tan((e-t)/2)*Math.tan((e-r)/2)*Math.tan((e-o)/2))))}function u(n,t){var r,o=(t[0]-n[0])*h,e=Math.sin(o),i=Math.cos(o),a=Math.sin(n[1]*h),u=Math.cos(n[1]*h),c=Math.sin(t[1]*h),s=Math.cos(t[1]*h);return Math.atan2(Math.sqrt((r=s*e)*r+(r=u*c-a*s*i)*r),a*c+u*s*i)}function c(n,t,r,o){return n*=h,t*=h,r*=h,o*=h,2*Math.asin(Math.sqrt(s(o-t)+Math.cos(t)*Math.cos(o)*s(r-n)))}function s(n){return(n=Math.sin(n/2))*n}var f=Math.PI,l=f/4,h=f/180;r.name="spherical",r.formatDistance=o,r.ringArea=e,r.absoluteArea=i,r.triangleArea=a,r.distance=c},{}],18:[function(n,t,r){var o=n("./type");t.exports=function(n,t){function r(n){return l>=n?[0,f]:n>=p?[0,h]:[a,n]}function e(n){for(var t=[],o=0,e=n.length;e>o;++o){for(var i=n[o],a=0,c=i.length;c>a;++a){var f=i[a];f.polygon=i,t.push(f);for(var h=0,g=f.length;g>h;++h){var v=f[h],d=v[0],y=v[1];if(u>=d||d>=s||l>=y||y>=p){for(var m=h+1;g>m;++m){var M=f[m],b=M[0],P=M[1];if(b>u&&s>b&&P>l&&p>P)break}if(m===h+1)continue;if(h){var w=f.slice(0,h+1);w.polygon=i,w[w.length-1]=r(y),t[t.length-1]=w}else t.pop();if(m>=g)break;t.push(f=f.slice(m-1)),f[0]=r(f[0][1]),f.polygon=i,h=-1,g=f.length}}}i.length=0}for(var E={},x={},h=0,g=t.length;g>h;++h){var j=t[h],L=j[0],S=j[j.length-1];L[0]!==S[0]||L[1]!==S[1]?(j.index=h,E[L]=x[S]=j):(j.polygon.push(j),t[h]=null)}for(var h=0;g>h;++h){var j=t[h];if(j){var L=j[0],S=j[j.length-1],q=x[L],A=E[S];if(delete E[L],delete x[S],L[0]===S[0]&&L[1]===S[1]){j.polygon.push(j);continue}q?(delete x[L],delete E[q[0]],q.pop(),t[q.index]=null,j=q.concat(j),j.polygon=q.polygon,q===A?j.polygon.push(j):(j.index=g++,t.push(E[j[0]]=x[j[j.length-1]]=j))):A?(delete E[S],delete x[A[A.length-1]],j.pop(),j=j.concat(A),j.polygon=A.polygon,j.index=g++,t[A.index]=null,t.push(E[j[0]]=x[j[j.length-1]]=j)):(j.push(j[0]),j.polygon.push(j))}}}var i=.01,a=-180,u=a+i,c=180,s=c-i,f=-90,l=f+i,h=90,p=h-i;if(t){var g=t.scale[0],v=t.scale[1],d=t.translate[0],y=t.translate[1];a=Math.round((a-d)/g),c=Math.round((c-d)/g),f=Math.round((f-y)/v),h=Math.round((h-y)/v),u=Math.round((u-d)/g),s=Math.round((s-d)/g),l=Math.round((l-y)/v),p=Math.round((p-y)/v)}var m=o({Polygon:function(n){e([n.coordinates])},MultiPolygon:function(n){e(n.coordinates)}});for(var M in n)m.object(n[M])}},{"./type":30}],19:[function(n,t,r){(function(r){var o=(n("./type"),n("./stitch")),e=n("./coordinate-systems"),i=n("./topology/index"),a=n("./delta"),u=n("./geomify"),c=n("./pre-quantize"),s=n("./post-quantize"),f=n("./bounds"),l=n("./compute-id"),h=n("./transform-properties"),p=1e-6;t.exports=function(n,t){var g,v=1e4,d=1e4,y=function(n){return n.id},m=function(){},M=0,b=!0,P=!1,w=null;if(t&&("verbose"in t&&(P=!!t.verbose),"stitch-poles"in t&&(b=!!t["stitch-poles"]),"coordinate-system"in t&&(w=e[t["coordinate-system"]]),"minimum-area"in t&&(M=+t["minimum-area"]),"quantization"in t&&(v=d=+t.quantization),"pre-quantization"in t&&(v=+t["pre-quantization"]),"post-quantization"in t&&(d=+t["post-quantization"]),"id"in t&&(y=t.id),"property-transform"in t&&(m=t["property-transform"])),v/d%1)throw new Error("post-quantization is not a divisor of pre-quantization");if(v&&!d)throw new Error("post-quantization is required when input is already quantized");l(n,y),h(n,m),u(n);var E=f(n),x=E[0]<-180-p||E[1]<-90-p||E[2]>180+p||E[3]>90+p;if(w||(w=e[x?"cartesian":"spherical"],t&&(t["coordinate-system"]=w.name)),w===e.spherical){if(x)throw new Error("spherical coordinates outside of [±180°, ±90°]");E[0]<-180+p&&(E[0]=-180),E[1]<-90+p&&(E[1]=-90),E[2]>180-p&&(E[2]=180),E[3]>90-p&&(E[3]=90)}P&&r.stderr.write("bounds: "+E.join(" ")+" ("+w.name+")\n"),v&&(g=c(n,E,v,d),P&&r.stderr.write("pre-quantization: "+g.scale.map(function(n){return w.formatDistance(n)}).join(" ")+"\n")),w===e.spherical&&b&&o(n,g);var j=i(n);return v&&(j.transform=g),j.bbox=E,P&&r.stderr.write("topology: "+j.arcs.length+" arcs, "+j.arcs.reduce(function(n,t){return n+t.length},0)+" points\n"),d&&d!==v&&(s(j,v,d),g=j.transform,P&&r.stderr.write("post-quantization: "+g.scale.map(function(n){return w.formatDistance(n)}).join(" ")+"\n")),d&&a(j),j}}).call(this,n("_process"))},{"./bounds":3,"./compute-id":6,"./coordinate-systems":7,"./delta":8,"./geomify":10,"./post-quantize":11,"./pre-quantize":12,"./stitch":18,"./topology/index":25,"./transform-properties":29,"./type":30,_process:1}],20:[function(n,t,r){function o(n,t,r,o){e(n,t,r),e(n,t,t+o),e(n,t+o,r)}function e(n,t,r){for(var o,e=t+(r-- -t>>1);e>t;++t,--r)o=n[t],n[t]=n[r],n[r]=o}var i=n("./join");t.exports=function(n){for(var t=i(n),r=n.coordinates,e=n.lines,a=n.rings,u=0,c=e.length;c>u;++u)for(var s=e[u],f=s[0],l=s[1];++f<l;)if(t.has(r[f])){var h={0:f,1:s[1]};s[1]=f,s=s.next=h}for(var u=0,c=a.length;c>u;++u)for(var p=a[u],g=p[0],v=g,d=p[1],y=t.has(r[g]);++v<d;)if(t.has(r[v]))if(y){var h={0:v,1:p[1]};p[1]=v,p=p.next=h}else o(r,g,d,d-v),r[d]=r[g],y=!0,v=g;return n}},{"./join":26}],21:[function(n,t,r){var o=(n("./join"),n("./hashmap")),e=n("./point-hash"),i=n("./point-equal");t.exports=function(n){function t(n){var t,r,o,e;if(o=M.get(t=l[n[0]]))for(var i=0,c=o.length;c>i;++i){var s=o[i];if(a(s,n))return n[0]=s[0],void(n[1]=s[1])}if(e=M.get(r=l[n[1]]))for(var i=0,c=e.length;c>i;++i){var f=e[i];if(u(f,n))return n[1]=f[0],void(n[0]=f[1])}o?o.push(n):M.set(t,[n]),e?e.push(n):M.set(r,[n]),b.push(n)}function r(n){var t,r;if(r=M.get(t=l[n[0]]))for(var o=0,e=r.length;e>o;++o){var i=r[o];if(c(i,n))return n[0]=i[0],void(n[1]=i[1]);if(s(i,n))return n[0]=i[1],void(n[1]=i[0])}if(r=M.get(t=l[n[0]+f(n)]))for(var o=0,e=r.length;e>o;++o){var i=r[o];if(c(i,n))return n[0]=i[0],void(n[1]=i[1]);if(s(i,n))return n[0]=i[1],void(n[1]=i[0])}r?r.push(n):M.set(t,[n]),b.push(n)}function a(n,t){var r=n[0],o=t[0],e=n[1],a=t[1];if(r-e!==o-a)return!1;for(;e>=r;++r,++o)if(!i(l[r],l[o]))return!1;return!0}function u(n,t){var r=n[0],o=t[0],e=n[1],a=t[1];if(r-e!==o-a)return!1;for(;e>=r;++r,--a)if(!i(l[r],l[a]))return!1;return!0}function c(n,t){var r=n[0],o=t[0],e=n[1],a=t[1],u=e-r;if(u!==a-o)return!1;for(var c=f(n),s=f(t),h=0;u>h;++h)if(!i(l[r+(h+c)%u],l[o+(h+s)%u]))return!1;return!0}function s(n,t){var r=n[0],o=t[0],e=n[1],a=t[1],u=e-r;if(u!==a-o)return!1;for(var c=f(n),s=u-f(t),h=0;u>h;++h)if(!i(l[r+(h+c)%u],l[a-(h+s)%u]))return!1;return!0}function f(n){for(var t=n[0],r=n[1],o=t,e=o,i=l[o];++o<r;){var a=l[o];(a[0]<i[0]||a[0]===i[0]&&a[1]<i[1])&&(e=o,i=a)}return e-t}var l=n.coordinates,h=n.lines,p=n.rings,g=h.length+p.length;delete n.lines,delete n.rings;for(var v=0,d=h.length;d>v;++v)for(var y=h[v];y=y.next;)++g;for(var v=0,d=p.length;d>v;++v)for(var m=p[v];m=m.next;)++g;for(var M=o(2*g*1.4,e,i),b=n.arcs=[],v=0,d=h.length;d>v;++v){var y=h[v];do t(y);while(y=y.next)}for(var v=0,d=p.length;d>v;++v){var m=p[v];if(m.next){do t(m);while(m=m.next)}else r(m)}return n}},{"./hashmap":23,"./join":26,"./point-equal":27,"./point-hash":28}],22:[function(n,t,r){t.exports=function(n){function t(n){n&&s.hasOwnProperty(n.type)&&s[n.type](n)}function r(n){for(var t=0,r=n.length;r>t;++t)c[++i]=n[t];var o={0:i-r+1,1:i};return a.push(o),o}function o(n){for(var t=0,r=n.length;r>t;++t)c[++i]=n[t];var o={0:i-r+1,1:i};return u.push(o),o}function e(n){return n.map(o)}var i=-1,a=[],u=[],c=[],s={GeometryCollection:function(n){n.geometries.forEach(t)},LineString:function(n){n.arcs=r(n.coordinates),delete n.coordinates},MultiLineString:function(n){n.arcs=n.coordinates.map(r),delete n.coordinates},Polygon:function(n){n.arcs=n.coordinates.map(o),delete n.coordinates},MultiPolygon:function(n){n.arcs=n.coordinates.map(e),delete n.coordinates}};for(var f in n)t(n[f]);return{type:"Topology",coordinates:c,lines:a,rings:u,objects:n}}},{}],23:[function(n,t,r){t.exports=function(n,t,r,o,e,i){function a(o,i){for(var a=t(o)&h,u=f[a],c=0;u!=e;){if(r(u,o))return l[a]=i;if(++c>=n)throw new Error("full hashmap");u=f[a=a+1&h]}return f[a]=o,l[a]=i,--p,i}function u(o,i){for(var a=t(o)&h,u=f[a],c=0;u!=e;){if(r(u,o))return l[a];if(++c>=n)throw new Error("full hashmap");u=f[a=a+1&h]}return f[a]=o,l[a]=i,--p,i}function c(o,i){for(var a=t(o)&h,u=f[a],c=0;u!=e;){if(r(u,o))return l[a];if(++c>=n)break;u=f[a=a+1&h]}return i}function s(){for(var n=[],t=0,r=f.length;r>t;++t){var o=f[t];o!=e&&n.push(o)}return n}3===arguments.length&&(o=i=Array,e=null);for(var f=new o(n=1<<Math.max(4,Math.ceil(Math.log(n)/Math.LN2))),l=new i(n),h=n-1,p=n,g=0;n>g;++g)f[g]=e;return{set:a,maybeSet:u,get:c,keys:s}}},{}],24:[function(n,t,r){t.exports=function(n,t,r,o,e){function i(o){for(var i=t(o)&s,a=c[i],u=0;a!=e;){if(r(a,o))return!0;if(++u>=n)throw new Error("full hashset");a=c[i=i+1&s]}return c[i]=o,--f,!0}function a(o){for(var i=t(o)&s,a=c[i],u=0;a!=e;){if(r(a,o))return!0;if(++u>=n)break;a=c[i=i+1&s]}return!1}function u(){for(var n=[],t=0,r=c.length;r>t;++t){var o=c[t];o!=e&&n.push(o)}return n}3===arguments.length&&(o=Array,e=null);for(var c=new o(n=1<<Math.max(4,Math.ceil(Math.log(n)/Math.LN2))),s=n-1,f=n,l=0;n>l;++l)c[l]=e;return{add:i,has:a,values:u}}},{}],25:[function(n,t,r){function o(n){var t,r=n[0],o=n[1];return r>o&&(t=r,r=o,o=t),r+31*o}function e(n,t){var r,o=n[0],e=n[1],i=t[0],a=t[1];return o>e&&(r=o,o=e,e=r),i>a&&(r=i,i=a,a=r),o===i&&e===a}var i=n("./hashmap"),a=n("./extract"),u=n("./cut"),c=n("./dedup");t.exports=function(n){function t(n){n&&p.hasOwnProperty(n.type)&&p[n.type](n)}function r(n){var t=[];do{var r=h.get(n);t.push(n[0]<n[1]?r:~r)}while(n=n.next);return t}function s(n){return n.map(r)}var f=c(u(a(n))),l=f.coordinates,h=i(1.4*f.arcs.length,o,e);n=f.objects,f.arcs=f.arcs.map(function(n,t){return h.set(n,t),l.slice(n[0],n[1]+1)}),delete f.coordinates,l=null;var p={GeometryCollection:function(n){n.geometries.forEach(t)},LineString:function(n){n.arcs=r(n.arcs)},MultiLineString:function(n){n.arcs=n.arcs.map(r)},Polygon:function(n){n.arcs=n.arcs.map(r)},MultiPolygon:function(n){n.arcs=n.arcs.map(s)}};for(var g in n)t(n[g]);return f}},{"./cut":20,"./dedup":21,"./extract":22,"./hashmap":23}],26:[function(n,t,r){var o=n("./hashset"),e=n("./hashmap"),i=n("./point-hash"),a=n("./point-equal");t.exports=function(n){function t(n,t,r,o){if(p[r]!==n){p[r]=n;var e=g[r];if(e>=0){var i=v[r];e===t&&i===o||e===o&&i===t||(++y,d[r]=1)}else g[r]=t,v[r]=o}}function r(){for(var n=e(1.4*s.length,u,c,Int32Array,-1,Int32Array),t=new Int32Array(s.length),r=0,o=s.length;o>r;++r)t[r]=n.maybeSet(r,r);return t}function u(n){return i(s[n])}function c(n,t){return a(s[n],s[t])}for(var s=n.coordinates,f=n.lines,l=n.rings,h=r(),p=new Int32Array(s.length),g=new Int32Array(s.length),v=new Int32Array(s.length),d=new Int8Array(s.length),y=0,m=0,M=s.length;M>m;++m)p[m]=g[m]=v[m]=-1;for(var m=0,M=f.length;M>m;++m){var b,P=f[m],w=P[0],E=P[1],x=h[w],j=h[++w];for(++y,d[x]=1;++w<=E;)t(m,b=x,x=j,j=h[w]);++y,d[j]=1}for(var m=0,M=s.length;M>m;++m)p[m]=-1;for(var m=0,M=l.length;M>m;++m){var L=l[m],S=L[0]+1,q=L[1],b=h[q-1],x=h[S-1],j=h[S];for(t(m,b,x,j);++S<=q;)t(m,b=x,x=j,j=h[S])}p=g=v=null;for(var A,F=o(1.4*y,i,a),m=0,M=s.length;M>m;++m)d[A=h[m]]&&F.add(s[A]);return F}},{"./hashmap":23,"./hashset":24,"./point-equal":27,"./point-hash":28}],27:[function(n,t,r){t.exports=function(n,t){return n[0]===t[0]&&n[1]===t[1]}},{}],28:[function(n,t,r){var o=new ArrayBuffer(16),e=new Float64Array(o),i=new Uint32Array(o);t.exports=function(n){e[0]=n[0],e[1]=n[1];var t=i[0]^i[1];return t=t<<5^t>>7^i[2]^i[3],2147483647&t}},{}],29:[function(n,t,r){t.exports=function(n,t){function r(n){n&&e.hasOwnProperty(n.type)&&e[n.type](n)}function o(n){null==n.properties&&(n.properties={});var r=n.properties=t(n);if(r)for(var o in r)return;delete n.properties}arguments.length<2&&(t=function(){});var e={Feature:o,FeatureCollection:function(n){n.features.forEach(o)}};for(var i in n)r(n[i]);return n}},{}],30:[function(n,t,r){t.exports=function(n){for(var t in o)t in n||(n[t]=o[t]);return n.defaults=o,n};var o={Feature:function(n){n.geometry&&this.geometry(n.geometry)},FeatureCollection:function(n){for(var t=n.features,r=-1,o=t.length;++r<o;)this.Feature(t[r])},GeometryCollection:function(n){for(var t=n.geometries,r=-1,o=t.length;++r<o;)this.geometry(t[r]);
},LineString:function(n){this.line(n.coordinates)},MultiLineString:function(n){for(var t=n.coordinates,r=-1,o=t.length;++r<o;)this.line(t[r])},MultiPoint:function(n){for(var t=n.coordinates,r=-1,o=t.length;++r<o;)this.point(t[r])},MultiPolygon:function(n){for(var t=n.coordinates,r=-1,o=t.length;++r<o;)this.polygon(t[r])},Point:function(n){this.point(n.coordinates)},Polygon:function(n){this.polygon(n.coordinates)},object:function(n){return null==n?null:i.hasOwnProperty(n.type)?this[n.type](n):this.geometry(n)},geometry:function(n){return null==n?null:e.hasOwnProperty(n.type)?this[n.type](n):null},point:function(){},line:function(n){for(var t=-1,r=n.length;++t<r;)this.point(n[t])},polygon:function(n){for(var t=-1,r=n.length;++t<r;)this.line(n[t])}},e={LineString:1,MultiLineString:1,MultiPoint:1,MultiPolygon:1,Point:1,Polygon:1,GeometryCollection:1},i={Feature:1,FeatureCollection:1}},{}],31:[function(n,t,r){var o=t.exports=n("./build/topojson");o.topology=n("./lib/topojson/topology"),o.simplify=n("./lib/topojson/simplify"),o.clockwise=n("./lib/topojson/clockwise"),o.filter=n("./lib/topojson/filter"),o.prune=n("./lib/topojson/prune"),o.stitch=n("./lib/topojson/stitch"),o.scale=n("./lib/topojson/scale")},{"./build/topojson":2,"./lib/topojson/clockwise":5,"./lib/topojson/filter":9,"./lib/topojson/prune":13,"./lib/topojson/scale":15,"./lib/topojson/simplify":16,"./lib/topojson/stitch":18,"./lib/topojson/topology":19}],32:[function(n,t,r){window.topojson={server:n("../node_modules/topojson/server.js"),client:n("../node_modules/topojson/build/topojson.js")}},{"../node_modules/topojson/build/topojson.js":2,"../node_modules/topojson/server.js":31}]},{},[32]);