29:null 2a:["$","title",null,{"children":"Scanline Fill Algorithm | Florian Ledermann | Observable"}] 2f:T556,{ // create SVG element let svg = d3.select(DOM.svg(width, height)) let projection = d3.geoMercator().fitExtent([[margin, margin], [width - margin, height - margin]], district) let pathGenerator = d3.geoPath().projection(projection) let timer = Date.now() let polygon = district.geometry.coordinates[0].map(c => projection(c).map(val => Math.round(val/resolution))) let cleanedPoly = []; for (let i=0; i0 ? polygon[i-1] : polygon[polygon.length-1]; let next = i (cnt-1)) { j = 0 } else { j = k+1 } while (pts[k][1] == pts[j][1]) { if ((j+1) > (cnt-1)) { j = 0 } else { j++ } } return pts[j][1] } function makeEdgeRec(lower, upper, yComp, edges) { let edge = {} edge.dxPerScan = (upper[0] - lower[0]) / (upper[1] - lower[1]) edge.xIntersect = lower[0] if (upper[1] < yComp) { edge.yUpper = upper[1] - 1 } else { edge.yUpper = upper[1] } insertEdge(edges[lower[1]], edge) } function buildEdgeList(pts, edges) { let cnt = pts.length, i, v1 = [0,0], v2 = [0,0], yPrev = pts[cnt-2][1] v1[0] = pts[cnt-1][0] v1[1] = pts[cnt-1][1] for (i=0; i v2[1]) { makeEdgeRec(v2, v1, yPrev, edges) } yPrev = v1[1] v1 = v2 } } function buildActiveList(scan, active, edges) { let p = edges[scan].next, q while (p) { q = p.next insertEdge(active, p) p = q } } function fillScan(scan, active) { let p1 = active.next, p2, i while (p1) { p2 = p1.next // HACK FL for some reason we sometimes don't get pairwise lists...? if (p2) { for (i=Math.floor(p1.xIntersect); i= p.yUpper) { p = p.next deleteAfter(q) } else { p.xIntersect = p.xIntersect + p.dxPerScan q = p p = p.next } } } function resortActiveList(active) { let q, p = active.next active.next = null while (p) { q = p.next insertEdge(active, p) p = q } } let edges = [], active, i,scan for (i = 0; i<500; i++) { edges[i] = {next: null} } buildEdgeList(polygon, edges) active = { next: null } for (scan = 0; scan<500; scan++) { buildActiveList(scan, active, edges) if (active.next) { fillScan(scan, active) updateActiveList(scan, active) resortActiveList(active) } } }31:[] 2d:{"id":"09efe751102abde0","slug":"scanline-fill-algorithm","title":"Scanline Fill Algorithm","thumbnail":"dfd47f7d9189e99d987a3d1c8a6ed2067bd7f87f2ba84a31a64902f68402ec44","access_level":"public","create_time":"$D2018-05-17T10:04:13.811Z","update_time":"$D2018-05-18T11:56:52.877Z","view_time":null,"first_public_time":"$D2018-05-17T10:44:32.369Z","has_unpublished_edits":null,"fork":{"id":"681e26e71bb1af8d","slug":"polygon-erosion-using-a-bitmap-based-approach","title":"Polygon Erosion Using a Bitmap-Based Approach","owner":{"id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann"}},"stars":4,"starred":false,"owner":{"type":"team","id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann","avatar_url":"https://avatars-next.observableusercontent.com/6a0df0eeae726b31981d0e7972c010612aa76ce1f8d25615d7a1a554faf9ae1e","tier":"starter_2024"},"version":697,"publish_version":697,"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":3,"collection":{"id":"7e1078d5396f1f06","slug":"cartographic-experiments","title":"Cartographic Experiments","owner":{"id":"5952e5f3991fd83c","login":"floledermann","name":"Florian Ledermann"}},"type":"notebook","body":{"title":"Scanline Fill Algorithm","cells":[{"id":0,"value":"md`# Scanline Fill Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":596,"value":"md`\n[... unfortunately there is a bug in my port of [\\`fillPoly()\\`](#fillPoly) that sometimes leads to scanlines only partially filled, particularly in low resolutions ... (check by setting \\`districtIndex\\` to 4 for an example)\n\nI abandoned this approach of rendering in plain JS, and instead now go for [rendering the polygon to a canvas and then un-antialiasing it](/@floledermann/polygon-erosion-using-a-bitmap-based-approach).]`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":666,"value":"helpers.signature","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"viewof districtIndex = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"viewof resolution = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"html`${resolution}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":627,"value":"md`Render time: ${renderTime} ms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":370,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"md`----\n### Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"md`#### Parameters:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"viewof width = html``","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":13,"value":"viewof margin = 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":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[districtIndex]","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":611,"value":"helpers.defaultCSS","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2e:"$2d:body"