31:T47f,function distanceToNearestItem(point, segments, points, prevBest) { // Note: distances to segments of the border are multiplied by 2 // Note: as an optimisation, the function returns -1 if result is <= prevBest let nearest = Infinity; for (let p of points) { let dx = point[0] - p[0]; let dy = point[1] - p[1]; if (Math.abs(dx) >= nearest || Math.abs(dy) >= nearest) continue; // a little optimisation let d = Math.hypot(dx, dy); if (d < nearest) { nearest = d; if (d <= prevBest) return -1; } } for (let segment of segments) { // Do a few quick checks to try to avoid an expensive pointToLineDistance() call if (point[0] >= Math.max(segment[0][0], segment[1][0]) + nearest) continue; if (point[1] >= Math.max(segment[0][1], segment[1][1]) + nearest) continue; if (point[0] <= Math.min(segment[0][0], segment[1][0]) - nearest) continue; if (point[1] <= Math.min(segment[0][1], segment[1][1]) - nearest) continue; let d = pointToLineDistance(point, segment) * edgeSpacing; if (d < nearest) { nearest = d; if (d <= prevBest) return -1; } } return nearest; }32:[{"id":"5505d875c80d82317564b6c6074ef481fff94116d52563a0ca4d8543f4398f5d7b195f32c1a2a297cd34367a862dedf33180d5a3b667f44d4b317ba8bb65186b","href":"https://static.observableusercontent.com/files/5505d875c80d82317564b6c6074ef481fff94116d52563a0ca4d8543f4398f5d7b195f32c1a2a297cd34367a862dedf33180d5a3b667f44d4b317ba8bb65186b","name":"clipped.geojson","type":"application/geo+json","lastModified":1633085158089.825,"size":220329},{"id":"0db0acc7313588c593afe31dbf5b02f4e3eb0af72a417687dccdc43be6c091369955d692776aa6e0d12675efb78f67e3e8232d95bf08cc51700082f83c23444f","href":"https://static.observableusercontent.com/files/0db0acc7313588c593afe31dbf5b02f4e3eb0af72a417687dccdc43be6c091369955d692776aa6e0d12675efb78f67e3e8232d95bf08cc51700082f83c23444f","name":"clipped_pops.csv","type":"text/csv","lastModified":1633086359051.792,"size":4923},{"id":"a7bf793e925d88d91e3eec74d7fe4eee53954199404005c036cd675940881b082e68694436f9485431c355b854eaf10354ba39a243690042d9bff5faf7d44854","href":"https://static.observableusercontent.com/files/a7bf793e925d88d91e3eec74d7fe4eee53954199404005c036cd675940881b082e68694436f9485431c355b854eaf10354ba39a243690042d9bff5faf7d44854","name":"clipped-with-pops.geojson","type":"application/geo+json","lastModified":1633339256735.19,"size":187768},{"id":"cb8394bc98985c4c243492135382d0407ca5fde3b6409285c0e775e89c5391679dbd21acf6f1ff050396a7a64a10afd9bf824f706f5d10f9e7c9d2f482710567","href":"https://static.observableusercontent.com/files/cb8394bc98985c4c243492135382d0407ca5fde3b6409285c0e775e89c5391679dbd21acf6f1ff050396a7a64a10afd9bf824f706f5d10f9e7c9d2f482710567","name":"mapshaper-dots-point9.json","type":"application/json","lastModified":1633341939712.564,"size":1864239},{"id":"a05f2a452a20b60e2ee00d0bb12a90978e623aea3385a143e195bed9d77e67cca226399526a1a85873d4b938bfb4d32bfefde9b017119514055a959c59013830","href":"https://static.observableusercontent.com/files/a05f2a452a20b60e2ee00d0bb12a90978e623aea3385a143e195bed9d77e67cca226399526a1a85873d4b938bfb4d32bfefde9b017119514055a959c59013830","name":"mapshaper-dots-1.json","type":"application/json","lastModified":1633340478040.699,"size":1861677},{"id":"d7ad78b89db88d85240a1a53ba2d67730b41cac6bc8d1b1ef792ef676aa0318c5d7cd8fb62c79961183c4114a4334bb0ab83a4cc55e7c3c18faa40df36baba5a","href":"https://static.observableusercontent.com/files/d7ad78b89db88d85240a1a53ba2d67730b41cac6bc8d1b1ef792ef676aa0318c5d7cd8fb62c79961183c4114a4334bb0ab83a4cc55e7c3c18faa40df36baba5a","name":"mapshaper-dots-point5.json","type":"application/json","lastModified":1633340477446.453,"size":1864144},{"id":"cab71aa52b8b7aef88a22088ffa8e558f196a3fc86169d4b76caa332a727f349858b0a319690280e0f6c776bf0677023acf567ac7403460423dd7d464e4a73ad","href":"https://static.observableusercontent.com/files/cab71aa52b8b7aef88a22088ffa8e558f196a3fc86169d4b76caa332a727f349858b0a319690280e0f6c776bf0677023acf567ac7403460423dd7d464e4a73ad","name":"mapshaper-dots-0.json","type":"application/json","lastModified":1633340476864.023,"size":1864313}] 2f:{"title":"Dot placement for dot density maps","cells":[{"id":0,"value":"# Dot placement for dot density maps\n\nThis notepad is my attempt to spread the dots in a dots-density map in a nice way within their enclosing polygons. The map on the left uses random placement. The map on the right spends a bit more time to spread the dots out more evenly.\n\nHow does it work? Each time a point is placed, a number (to be precise, five times the value of the *effort* slider below) of candidate points within the polygon are generated at random. Of these candidates, the point that is furthest away from any other dots in the polygon and from the polygon's borders (with these latter distances multiplied by the value of the *edge spacing* slider) is chosen.\n\nThe algorithm is a version of *Mitchell's best-candidate algorithm*, which is [described nicely by Mike Bostock](https://bost.ocks.org/mike/algorithms/).","pinned":false,"hidden":false,"mode":"md"},{"id":283,"value":"bothMaps = {\n let div = d3.create(\"div\");\n div.append(() => drawMap(dots, numberOfColours, \"Random placement\"));\n div.append(() =>\n drawMap(dots2, numberOfColours, \"This notebook's algorithm\")\n );\n return div.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":612,"value":"#### Algorithm parameters","pinned":false,"hidden":false,"mode":"md"},{"id":351,"value":"viewof peoplePerDot = Inputs.range([5, 100], {\n label: \"People per dot\",\n value: 15,\n step: 5\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":371,"value":"viewof effort = Inputs.range([1, 6], {\n label: \"Effort to spread dots nicely\",\n value: 3,\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":607,"value":"viewof edgeSpacing = Inputs.range([1, 5], {\n label: \"Edge spacing\",\n value: 3,\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":616,"value":"#### Style parameters","pinned":false,"hidden":false,"mode":"md"},{"id":379,"value":"viewof radius = Inputs.range([0.6, 2], {\n label: \"Dot radius\",\n value: 1,\n step: 0.2\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":384,"value":"viewof opacity = Inputs.range([0.2, 1], {\n label: \"Dot opacity\",\n value: 0.8,\n step: 0.1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":368,"value":"viewof numberOfColours = Inputs.range([1, 7], {\n label: \"Number of colours\",\n value: 4,\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":530,"value":"viewof borderColour = Inputs.range([150, 250], {\n label: \"Border colour\",\n value: 200,\n step: 25\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":493,"value":"## Comparison with Mapshaper\n\nAfter creating this notebook, I discovered John Keefe's [blog post](https://www.mapbox.com/blog/cnn-maps-the-most-diverse-usa-ever), which points towards a [Mapshaper](https://github.com/mbloch/mapshaper) feature for creating dot-density maps. It's really good! The first map below shows the results of this notebook's algoritm; the remaining three maps show the output of Mapshaper with three different *evenness* values. All four of these maps use 10 people per dot and one colour.\n\nI haven't yet found a description of how Mapshaper's algorithm works.","pinned":false,"hidden":false,"mode":"md"},{"id":490,"value":"mapshaperComparison = {\n let div = d3.create(\"div\");\n div.append(() => drawMap(dots2_10, 1, \"This notebook's algorithm\"));\n div.append(() => drawMap(mapshaperDots1, 1, \"Mapshaper, evenness=1\"));\n div.append(() => drawMap(mapshaperDotsPoint9, 1, \"Mapshaper, evenness=0.9\"));\n div.append(() => drawMap(mapshaperDotsPoint5, 1, \"Mapshaper, evenness=0.5\"));\n return div.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":454,"value":"## Notes on this notebook's algorithm\n\n- A hill-climbing algorithm could be used to improve the dot positions after placing them.\n- If a polygon has a long, thin part, the algorithm tends not to put points there because they would be close to the edge. This might be a disadvantage.\n- There are other algorithms for this problem that I haven't explored.\n- I've written a slightly faster variant of this algorithm [here](https://observablehq.com/@jtrim-ons/dot-density-map-a-tweaked-version).","pinned":false,"hidden":false,"mode":"md"},{"id":577,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":204,"value":"function drawMap(dots, numberOfColours, title) {\n const div = d3\n .create(\"div\")\n .style(\"width\", width)\n .style(\"display\", \"inline-block\");\n\n div.append(\"h4\").text(title);\n\n const svg = div\n .append(\"svg\")\n .attr(\"viewBox\", [0, 0, width, height])\n .attr(\"width\", width);\n\n svg\n .append(\"path\")\n .attr(\"d\", path(data))\n .style(\"fill\", \"none\")\n .style(\"stroke-width\", 0.5)\n .style(\"stroke\", `rgba(${borderColour},${borderColour},${borderColour},1)`);\n\n svg\n .selectAll(\"circle\")\n .data(dots.features)\n .enter()\n .append(\"circle\")\n .attr(\"r\", radius)\n .attr(\n \"transform\",\n (d) => `translate(${projection(d.geometry.coordinates)})`\n )\n .style(\n \"fill\",\n (d) => dotColours[idToColourIndex(d.properties.id, numberOfColours)]\n )\n .style(\"opacity\", opacity);\n\n return div.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":418,"value":"dots = genDots(data)","pinned":true,"hidden":false,"mode":"ojs"},{"id":421,"value":"dots2 = genDots2(data, peoplePerDot)","pinned":true,"hidden":false,"mode":"ojs"},{"id":510,"value":"dots2_10 = genDots2(data, 10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":58,"value":"data = {\n let geojson = await FileAttachment(\"clipped-with-pops.geojson\").json();\n // fix winding order of polygons\n geojson.features = geojson.features.map((feature) =>\n turf.rewind(feature, { reverse: true })\n );\n return geojson;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":506,"value":"mapshaperDots0 = FileAttachment(\"mapshaper-dots-0.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"mapshaperDotsPoint5 = FileAttachment(\"mapshaper-dots-point5.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":526,"value":"mapshaperDotsPoint9 = FileAttachment(\"mapshaper-dots-point9.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":516,"value":"mapshaperDots1 = FileAttachment(\"mapshaper-dots-1.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":264,"value":"getProjectedSegments = function (polygon) {\n return turf\n .lineSegment(polygon)\n .features.map((f) => f.geometry.coordinates.map(projection));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"function genDots(geo) {\n // This function is based on code by Ahmad Barclay\n let points = { type: \"FeatureCollection\", features: [] };\n for (let polygon of geo.features) {\n let bbox = turf.bbox(polygon);\n let count = Math.round(polygon.properties.pop / peoplePerDot);\n let i = 1;\n while (i <= count) {\n let point = randomPointInPolygon(polygon, bbox);\n point.properties.id =\n polygon.properties.item + i.toString().padStart(3, \"0\");\n points.features.push(point);\n i++;\n }\n }\n // Shuffle points to avoid plotting one colour on top of the others where there are overlaps\n d3.shuffle(points.features);\n return points;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":197,"value":"function genDots2(geo, peoplePerDot) {\n let points = { type: \"FeatureCollection\", features: [] };\n for (let polygon of geo.features) {\n let bbox = turf.bbox(polygon);\n let lineSegments = getProjectedSegments(polygon);\n let count = Math.round(polygon.properties.pop / peoplePerDot);\n let i = 1;\n let projectedPoints = [];\n while (i <= count) {\n let point = nicePointInPolygon(\n polygon,\n bbox,\n lineSegments,\n projectedPoints\n );\n point.properties.id =\n polygon.properties.item + i.toString().padStart(3, \"0\");\n points.features.push(point);\n projectedPoints.push(projectPoint(point));\n i++;\n }\n }\n // Shuffle points to avoid plotting one colour on top of the others where there are overlaps\n d3.shuffle(points.features);\n return points;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":253,"value":"function nicePointInPolygon(polygon, bbox, lineSegments, points) {\n let bestDist = -Infinity;\n let bestPoint;\n let iters = effort * 5;\n for (let i = 0; i < iters; i++) {\n let p = randomPointInPolygon(polygon, bbox);\n let dist = distanceToNearestItem(\n projectPoint(p),\n lineSegments,\n points,\n bestDist\n );\n if (dist > bestDist) {\n bestDist = dist;\n bestPoint = p;\n }\n }\n return bestPoint;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":306,"value":"// Based on https://stackoverflow.com/a/1501725/3347737\nfunction pointToLineDistance(p, [v, w]) {\n function dist2(v, w) {\n let dx = v[0] - w[0];\n let dy = v[1] - w[1];\n return dx * dx + dy * dy;\n }\n function distToSegmentSquared(p, v, w) {\n var l2 = dist2(v, w);\n if (l2 == 0) return dist2(p, v);\n var t =\n ((p[0] - v[0]) * (w[0] - v[0]) + (p[1] - v[1]) * (w[1] - v[1])) / l2;\n t = Math.max(0, Math.min(1, t));\n return dist2(p, [v[0] + t * (w[0] - v[0]), v[1] + t * (w[1] - v[1])]);\n }\n return Math.sqrt(distToSegmentSquared(p, v, w));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":235,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":208,"value":"function randomPointInPolygon(polygon, bbox) {\n let point;\n do {\n point = turf.randomPoint(1, { bbox: bbox }).features[0];\n } while (!turf.booleanPointInPolygon(point.geometry.coordinates, polygon));\n return point;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":328,"value":"function idToColourIndex(id, numberOfColours) {\n // This is just a made-up function to assign some pretty colours\n if (numberOfColours === 1) return 0;\n let result = +id[id.length - 4] % numberOfColours;\n if (id[id.length - 1] > 6) {\n result = (result + +id[id.length - 1]) % numberOfColours;\n }\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":174,"value":"dotColours = d3.schemeDark2","pinned":false,"hidden":false,"mode":"ojs"},{"id":277,"value":"function projectPoint(point) {\n return projection(point.geometry.coordinates);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"path = d3.geoPath(projection).pointRadius(radius)","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"projection = d3.geoMercator().fitWidth(width * 1, data)","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"width = 560","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"height = Math.ceil(path.bounds(data)[1][1])","pinned":false,"hidden":false,"mode":"ojs"},{"id":109,"value":"turf = require(\"@turf/turf\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":133,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}