{"id":"608bb70ceabc900f","slug":"voronoi-projection","trashed":false,"description":"","likes":13,"publish_level":"public","forks":1,"fork_of":null,"has_importers":false,"update_time":"2022-09-30T13:10:51.399Z","first_public_version":null,"paused_version":null,"publish_time":"2018-10-05T10:27:52.168Z","publish_version":1772,"latest_version":1772,"thumbnail":"6a39ff1a7b1177abaf5602e922492225cd44a92dad3f9802b3e8c900acce6787","default_thumbnail":"6a39ff1a7b1177abaf5602e922492225cd44a92dad3f9802b3e8c900acce6787","roles":[],"sharing":null,"owner":{"id":"da2a32154638c457","avatar_url":"https://avatars.observableusercontent.com/avatar/9cf371db2e1a2b4ed5f4a9783b6954cf7aeb2a88c56d4054c96ef360cf85ef89","login":"fil","name":"Fil","bio":"Vocateur.","home_url":"https://visionscarto.net/","type":"team","tier":"starter_2024"},"creator":{"id":"45a379fcfcb14253","avatar_url":"https://avatars.observableusercontent.com/avatar/9cf371db2e1a2b4ed5f4a9783b6954cf7aeb2a88c56d4054c96ef360cf85ef89","login":"fil","name":"Fil","bio":"Vocateur.","home_url":"https://visionscarto.net/","tier":"pro"},"authors":[{"id":"45a379fcfcb14253","avatar_url":"https://avatars.observableusercontent.com/avatar/9cf371db2e1a2b4ed5f4a9783b6954cf7aeb2a88c56d4054c96ef360cf85ef89","name":"Fil","login":"fil","bio":"Vocateur.","home_url":"https://visionscarto.net/","tier":"pro","approved":true,"description":""}],"collections":[{"id":"8d7a994f5bc56ea2","type":"public","slug":"projections","title":"Projections","description":"flattening the earth","update_time":"2018-09-13T15:56:48.538Z","pinned":true,"ordered":false,"custom_thumbnail":null,"default_thumbnail":"813b390d11e566b160a43bec3a7363fb25faa754e72379c62875ba580674d487","thumbnail":"813b390d11e566b160a43bec3a7363fb25faa754e72379c62875ba580674d487","listing_count":137,"parent_collection_count":0,"owner":{"id":"da2a32154638c457","avatar_url":"https://avatars.observableusercontent.com/avatar/9cf371db2e1a2b4ed5f4a9783b6954cf7aeb2a88c56d4054c96ef360cf85ef89","login":"fil","name":"Fil","bio":"Vocateur.","home_url":"https://visionscarto.net/","type":"team","tier":"starter_2024"}},{"id":"1b93c3deba41e333","type":"public","slug":"voronoi","title":"Voronoi","description":"points to topologies","update_time":"2018-09-13T15:56:01.110Z","pinned":true,"ordered":false,"custom_thumbnail":"e7bf1c8327c05c47d8ff37cf875a8a245b16b3945626725c0fb81e575bf7148f","default_thumbnail":"00e4202fa6df3512306c24d1cd7e830ece63f92c10c2fa66996210779e501474","thumbnail":"e7bf1c8327c05c47d8ff37cf875a8a245b16b3945626725c0fb81e575bf7148f","listing_count":50,"parent_collection_count":0,"owner":{"id":"da2a32154638c457","avatar_url":"https://avatars.observableusercontent.com/avatar/9cf371db2e1a2b4ed5f4a9783b6954cf7aeb2a88c56d4054c96ef360cf85ef89","login":"fil","name":"Fil","bio":"Vocateur.","home_url":"https://visionscarto.net/","type":"team","tier":"starter_2024"}}],"files":[],"comments":[],"commenting_lock":null,"suggestion_from":null,"suggestions_to":[],"version":1772,"title":"The Voronoi projection","license":null,"copyright":"","nodes":[{"id":0,"value":"md`# The Voronoi projection\n\nUsage:\n\\`\\`\\`{javascript}\n   require(\"d3-geo\", \"d3-geo-polygon\");\n   const projection = d3.geoPolyhedralVoronoi(parents, polygons, faceProjection, faceFind)\n  \n   OR\n   projection.parents(parents)\n   projection.polygons(polygons);\n\\`\\`\\`\n\nMany options are available, see [github.com/Fil/voronoi-projection](https://github.com/Fil/voronoi-projection) for implementation details, and [liris.cnrs.fr/mi2](https://projet.liris.cnrs.fr/mi2/posts/2018/10/05/voronoi-projection-en.html) for explanations.\n`","pinned":false,"mode":"js","data":null,"name":null},{"id":15,"value":"VORONOI = map(projection)","pinned":false,"mode":"js","data":null,"name":null},{"id":752,"value":"projection = d3\n  .geoPolyhedralVoronoi()\n  .parents(parents)\n  .polygons(polygons)\n  .angle(38)\n  .fitExtent([[0, 0], [950, 500]], { type: \"Sphere\" })","pinned":true,"mode":"js","data":null,"name":null},{"id":1393,"value":"function map(projection, opts) {\n  const height = width * (2 / 3),\n    scale = 1;\n  const context = DOM.context2d(width * scale, height * scale);\n\n  context.scale(scale, scale);\n\n  opts = Object.assign({}, opts);\n\n  const projectionmap = opts.view || projection;\n  projectionmap.fitExtent([[2, 2], [width - 2, height - 2]], {\n    type: \"Sphere\"\n  });\n\n  var path = d3.geoPath(projectionmap, context);\n  context.clearRect(0, 0, width, height);\n\n  context.beginPath(),\n    path({ type: \"Sphere\" }),\n    (context.fillStyle = \"#fefef6\"),\n    context.fill();\n\n  context.beginPath(),\n    path(d3.geoGraticule()()),\n    (context.strokeStyle = \"#ccc\"),\n    context.stroke();\n\n  context.beginPath(),\n    path(land),\n    (context.fillStyle = \"black\"),\n    context.fill();\n\n  // Polyhedral projections expose their structure as projection.tree()\n  // To draw them we need to cancel the rotate\n  if (true) {\n    var rotate = projection.rotate();\n    projection.rotate([0, 0, 0]);\n\n    // run the tree of faces to get all sites and folds\n    var sites = [],\n      folds = [],\n      i = 0;\n    function recurse(face) {\n      var site = d3.geoCentroid({ type: \"MultiPoint\", coordinates: face.face });\n      site.id = face.id || i++;\n      sites[site.id] = site;\n      if (face.children) {\n        face.children.forEach(function(child) {\n          folds.push({\n            type: \"LineString\",\n            coordinates: child.shared.map(e =>\n              d3.geoInterpolate(e, face.centroid)(1e-5)\n            )\n          });\n          recurse(child);\n        });\n      }\n    }\n    recurse(projection.tree());\n\n    const circles = points;\n\n    // links\n    if (opts.tree) {\n      context.beginPath(),\n        path({\n          type: \"MultiLineString\",\n          coordinates: parents\n            .map((from, to) => [circles[from], circles[to]])\n            .filter(d => !!d[0])\n        }),\n        (context.strokeStyle = \"green\"),\n        context.stroke();\n    }\n\n    // folding lines\n    context.beginPath(),\n      (context.lineWidth = 0.5),\n      context.setLineDash([3, 4]),\n      (context.strokeStyle = \"#666\");\n    if (opts.view) path(voro.cellMesh());\n    else folds.forEach(path);\n    context.stroke(), context.setLineDash([]);\n\n    if (opts.cut) {\n      (context.lineWidth = 1),\n        (context.strokeStyle = \"brown\"),\n        context.beginPath(),\n        path(projection.preclip().polygon()),\n        context.stroke();\n    }\n\n    (context.lineWidth = 1),\n      (context.strokeStyle = \"#000\"),\n      context.beginPath(),\n      path({ type: \"Sphere\" });\n    context.stroke();\n\n    // restore the projection’s rotate\n    projection.rotate(rotate);\n  }\n\n  return context.canvas;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":783,"value":"n = 43","pinned":false,"mode":"js","data":null,"name":null},{"id":797,"value":"md`The Voronoi projection allows many very different aspects. This aspect is built around the centroids of the 43 largest countries. The cost function that defines the spanning tree favors connections that are on land.`","pinned":false,"mode":"js","data":null,"name":null},{"id":970,"value":"points = countries.features\n  .slice()\n  .sort((a, b) => d3.descending(d3.geoArea(a), d3.geoArea(b)))\n  .slice(0, n) // n=38\n  .map(d3.geoCentroid)","pinned":false,"mode":"js","data":null,"name":null},{"id":771,"value":"voro = d3.geoVoronoi()(points.map((p, i) => [...p, i]))","pinned":false,"mode":"js","data":null,"name":null},{"id":779,"value":"polygons = voro.polygons()","pinned":false,"mode":"js","data":null,"name":null},{"id":1072,"value":"cost = {\n  return function(a, b) {\n    return d3.geoDistance(a, b) / (1 + 2 * (inland[a[2]] + inland[b[2]]));\n  };\n}","pinned":true,"mode":"js","data":null,"name":null},{"id":1479,"value":"clipPolygon = d3.geoProject(\n  {\n    type: \"MultiPolygon\",\n    coordinates: voro.polygons().features.map((d, i) => {\n      const c = voro.points[i];\n      return d.geometry.coordinates;\n    })\n  },\n  d3\n    .geoEquirectangular()\n    .scale(degrees)\n    .translate([0, 0])\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":1197,"value":"inland = {\n  // hack d.geoContains\n  const contains = geoContainsCache(land),\n    d3_geoContains = d3.geoContains;\n\n  d3.geoContains = function(_, d) {\n    if (_ === land) return contains(d);\n    return d3_geoContains(_, d);\n  };\n\n  const inland = points.map(d => +d3.geoContains(land, d));\n\n  return inland;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":1757,"value":"import {geoContainsCache} from \"@fil/another-hex-map\"","pinned":false,"mode":"js","data":null,"name":null},{"id":774,"value":"parents = {\n  var n = points.length;\n\n  var links = voro.links().features.map(d => d.properties);\n\n  var k = kruskal(\n    links.map(\n      d => ((d.source.index = d.source[2]), (d.target.index = d.target[2]), d)\n    ),\n    cost\n  ).map(l => ({\n    type: \"LineString\",\n    coordinates: [l.source, l.target],\n    properties: l\n  }));\n\n  // Build a tree of the faces\n  var parents = [-1];\n  var search = n - 1;\n  do {\n    k.forEach(l => {\n      var s = l.properties.source[2],\n        t = l.properties.target[2];\n      if (parents[s] !== undefined && parents[t] === undefined) {\n        parents[t] = s;\n        search--;\n      } else if (parents[t] !== undefined && parents[s] === undefined) {\n        parents[s] = t;\n        search--;\n      }\n    });\n  } while (search > 0);\n\n  return parents;\n}","pinned":true,"mode":"js","data":null,"name":null},{"id":513,"value":"md`-----------\n_Play zone_`","pinned":false,"mode":"js","data":null,"name":null},{"id":9,"value":"land = d3.json(\n  \"https://unpkg.com/visionscarto-world-atlas@0.0.4/world/110m_land.geojson\"\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":1161,"value":"countries = d3.json(\n  \"https://unpkg.com/visionscarto-world-atlas@0.0.3/world/110m_countries.geojson\"\n)","pinned":false,"mode":"js","data":null,"name":null},{"id":2,"value":"d3 = require(\"d3@7\", \"d3-geo-projection@4\", \"d3-geo-polygon@1.8\", \"d3-geo-voronoi@2\")","pinned":false,"mode":"js","data":null,"name":null},{"id":756,"value":"kruskal = {\n  // https://github.com/mikolalysenko/union-find\n  const UnionFind = (function() {\n    \"use strict\";\n    \"use restrict\";\n\n    function UnionFind(count) {\n      this.roots = new Array(count);\n      this.ranks = new Array(count);\n\n      for (var i = 0; i < count; ++i) {\n        this.roots[i] = i;\n        this.ranks[i] = 0;\n      }\n    }\n\n    var proto = UnionFind.prototype;\n\n    Object.defineProperty(proto, \"length\", {\n      get: function() {\n        return this.roots.length;\n      }\n    });\n\n    proto.makeSet = function() {\n      var n = this.roots.length;\n      this.roots.push(n);\n      this.ranks.push(0);\n      return n;\n    };\n\n    proto.find = function(x) {\n      var x0 = x;\n      var roots = this.roots;\n      while (roots[x] !== x) {\n        x = roots[x];\n      }\n      while (roots[x0] !== x) {\n        var y = roots[x0];\n        roots[x0] = x;\n        x0 = y;\n      }\n      return x;\n    };\n\n    proto.link = function(x, y) {\n      var xr = this.find(x),\n        yr = this.find(y);\n      if (xr === yr) {\n        return;\n      }\n      var ranks = this.ranks,\n        roots = this.roots,\n        xd = ranks[xr],\n        yd = ranks[yr];\n      if (xd < yd) {\n        roots[xr] = yr;\n      } else if (yd < xd) {\n        roots[yr] = xr;\n      } else {\n        roots[yr] = xr;\n        ++ranks[xr];\n      }\n    };\n\n    return UnionFind;\n  })();\n\n  function kruskal(graph, dist) {\n    // 1   A := ø\n    const A = [];\n    // 2   for each vertex v of G :\n    // 3      create set(v)\n    let n = -Infinity;\n    graph.forEach(l => {\n      if (l.source.index > n) n = l.source.index;\n      if (l.target.index > n) n = l.target.index;\n    });\n    const uf = new UnionFind(n);\n    // 4   sort the edges of G by increasing weight\n\n    graph = graph.map(l => {\n      l.w = dist ? dist(l.source, l.target) : l.length;\n      return l;\n    });\n    graph\n      .sort((a, b) => d3.ascending(a.w, b.w))\n      // 5   for each edge (u, v) of G (sorted by weigth):\n      .forEach(l => {\n        // 6      if find(u) ≠ find(v) :\n        if (uf.find(l.source.index) != uf.find(l.target.index)) {\n          // 7         add (u, v) to the set A\n          A.push(l);\n          // 8         union(u, v)\n          uf.link(l.source.index, l.target.index);\n        }\n      });\n    // 9   solution = A\n    return A;\n  }\n\n  return kruskal;\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":1709,"value":"import { degrees } from \"@fil/math\"","pinned":false,"mode":"js","data":null,"name":null}],"resolutions":[],"schedule":null,"last_view_time":null}