29:null 2a:["$","title",null,{"children":"Polygon Erosion Using a Bitmap-Based Approach | Florian Ledermann | Observable"}] 2f:[] 2d:{"id":"681e26e71bb1af8d","slug":"polygon-erosion-using-a-bitmap-based-approach","title":"Polygon Erosion Using a Bitmap-Based Approach","thumbnail":"406a7bbefe0872b7aa7d660080a14ea7768ee06109c6e16db34e1c90792f9b53","access_level":"public","create_time":"$D2018-05-16T08:35:04.135Z","update_time":"$D2018-05-20T08:15:11.369Z","view_time":null,"first_public_time":"$D2018-05-17T11:08:53.677Z","has_unpublished_edits":null,"fork":{"id":"9ecbf53e94763a52","slug":"dot-density-maps-with-d3","title":"Dot Density Maps with D3","owner":{"id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann"}},"stars":1,"starred":false,"owner":{"type":"team","id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann","avatar_url":"https://avatars-next.observableusercontent.com/6a0df0eeae726b31981d0e7972c010612aa76ce1f8d25615d7a1a554faf9ae1e","tier":"starter_2024"},"version":797,"publish_version":797,"role":null,"authored":false,"authors":[{"type":"individual","id":"bb2fc280c71d473c","login":"floledermann","name":"Florian Ledermann","avatar_url":"https://avatars-next.observableusercontent.com/6a0df0eeae726b31981d0e7972c010612aa76ce1f8d25615d7a1a554faf9ae1e","tier":null}],"members":[{"type":"individual","id":"bb2fc280c71d473c","login":"floledermann","name":"Florian Ledermann","avatar_url":"https://avatars-next.observableusercontent.com/6a0df0eeae726b31981d0e7972c010612aa76ce1f8d25615d7a1a554faf9ae1e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"7e1078d5396f1f06","slug":"cartographic-experiments","title":"Cartographic Experiments","owner":{"id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann"}},"type":"notebook","body":{"title":"Polygon Erosion Using a Bitmap-Based Approach","cells":[{"id":0,"value":"md`# Polygon Erosion Using a Bitmap-Based Approach`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":623,"value":"md`For many cartographic applications (label placement, outline offsets) we need to erode polygons (i.e. create a “negative buffer” inside the polygon), which is complex and slow because of the required geometry calculations and special cases. This is an attempt to use a bitmap-based approach, by rendering the polygon to a canvas and marking neighboring pixels with increasing z values, starting at the polygon boundaries.\n\nThe calculated bitmap can be [further processed to generate a contour polygon](/@floledermann/contours-from-eroded-polygon).\n\nAnother idea would be to use [voronoi stippling](/@mbostock/voronoi-stippling) to create dot-density maps with a natural dot distribution.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":630,"value":"helpers.signature","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"viewof districtOffset = helpers.labeledInput({\n value: 8,\n min: 0,\n max:22,\n label: \"Geometry Index:\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"viewof resolution = helpers.labeledSlider({\n value: 60,\n min: 4,\n max: 100,\n label: \"Bitmap resolution:\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":733,"value":"viewof thresholdValue = helpers.labeledSlider({\n value: 6,\n min: 1,\n max: resolution >> 2,\n label: \"Threshold Value:\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"html`RenderTime: ${renderTime} ms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"{\n const width = resolution, height = resolution\n \n let canvas = DOM.canvas(width,height),\n context = canvas.getContext(\"2d\")\n\n canvas.style.width = \"400px\";\n canvas.style.imageRendering = \"pixelated\"\n\n let projection = d3.geoMercator().fitExtent([[0,0], [width,height]], district)\n \n let time = Date.now()\n \n let monochrome = renderGeoToBitmap(district, projection, width, height)\n let unantialiased = threshold(monochrome)\n let eroded = erode(unantialiased, width, height)\n\n mutable renderTime = Date.now() - time\n \n // draw our target value in black\n eroded = Uint8Array.from(eroded, d => (d == thresholdValue) ? 255: d)\n \n // amplify for visual output\n let amplified = Uint8ClampedArray.from(eroded, val => val * 255 * 4 / resolution)\n \n let imgData = new ImageData(monochromeToMultichannel(amplified), width, height)\n context.putImageData(imgData,0,0)\n \n return canvas\n\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":769,"value":"function renderGeoToCanvas(context, geo, projection, fillStyle='#000000') {\n let pathGenerator = d3.geoPath().projection(projection).context(context)\n \n context.save();\n \n context.fillStyle = fillStyle;\n context.beginPath();\n pathGenerator(district)\n context.fill(); \n \n context.restore();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":771,"value":"function renderGeoToBitmap(geo, projection, width, height, fillStyle='#000000') {\n \n let canvas = DOM.canvas(width,height),\n context = canvas.getContext(\"2d\")\n \n renderGeoToCanvas(context, geo, projection)\n \n return imageChannel(context.getImageData(0, 0, width, height).data)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":670,"value":"function maxNeighbours(imgData,x,y,width,height) {\n /*\n neighbours = [\n 1,1,1\n 1, 1,\n 1,1,1\n ]\n \n 0 ... outside polygon\n 255 ... inside polygon\n */\n \n let max=-1;\n \n // cylce through 8 neighbours by adding offsets -1..1 to x,y location\n for (let dy=-1; dy<=1; dy++) {\n for (let dx=-1; dx<=1; dx++) {\n // ignore actual pixel\n if (dx == 0 && dy == 0) continue;\n \n let px = x+dx,\n py = y+dy;\n \n // check image boundaries\n if (px<0 || py<0 || px>=width || py>=height) continue;\n \n let val = imgData[py*width + px];\n // 255 is value for \"inside, but not yet processed\", so set to -1 to be ingored/wrapped\n if (val != 255 && val > max) max = val;\n \n }\n }\n // return the maximum of all neighbours, increased by 1\n // interior values will be -1, so will return 0 for an interior point without neighbours\n return max+1;\n }\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":643,"value":"function erode(imgData, width, height) {\n\n // we can't write to the image we read from in the same pass to not disturb the data\n // so create two images\n let imgRead = Uint8ClampedArray.from(imgData)\n let imgWrite = Uint8ClampedArray.from(imgData)\n \n let goOn = true\n \n while (goOn) {\n goOn = false\n for (let y=0; y (d > threshold) ? 255: 0)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":647,"value":"function imageChannel(imgData, channel=3, numChannels=4) {\n \n console.assert(imgData.length % numChannels == 0, \"Image does not have \" + numChannels + \" channels!\")\n \n let newData = new Uint8Array(imgData.length / numChannels)\n \n for (let i=0; i`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"viewof height = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":395,"value":"mutable renderTime = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"viewof margin = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"md`#### Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"import {viennaTopoJSON as topology} from \"@floledermann/helpers\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"presimplified = simplify.presimplify(topology)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"viewof geometryDetail = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":137,"value":"geometryDetail","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"simplified = simplify.simplify(presimplified, simplify.quantile(presimplified, geometryDetail))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"districts = topojson.feature(simplified, simplified.objects.districts)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":360,"value":"district = districts.features[districtOffset]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"boundaries = topojson.mesh(simplified, simplified.objects.districts)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md`#### Libraries`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"d3 = require(\"d3\",\"d3-polygon\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"topojson = require(\"topojson-client@3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"simplify = require(\"topojson-simplify@3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"md`#### Custom CSS`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"import {helpers} from \"@floledermann/helpers\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":582,"value":"helpers.defaultCSS","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2f","stdlib":"1","titling":"auto"}} 2e:"$2d:body"