30:T6b2,md`## API Function \`getCirculations(imgdata)\` implements path tracing of a given bitmap. The single argument is an [\`ImageData\`](https://developer.mozilla.org/en-US/docs/Web/API/ImageData) object, where pixels having *alpha*=0 are considered background pixels and all others are considered foreground pixels. The return value is a \`ConnectedComponents\` object, which has two main fields: \`components\` and \`closed\` (the other fields are used internally by the algorithm and can be ignored). Both are arrays of connected components, i.e., objects representing polygons enclosing groups of foreground or background pixels. However, whereas all positions of \`closed\` hold valid connected components, array \`components\` may have null or undefined positions. This is because \`components\` is used as a table by the algorithm to keep track of incomplete curve segments that may be merged together. At the end, all curve segments should have been stitched together forming closed polygons, which are then placed in \`closed\`. Each connected component is an object having 3 main fields (the rest can be ignored): 1. \`points\`: an array of points in 2d, each an object having fields \`x\` and \`y\`, holding the point's coordinates. 2. \`contains\`: an array of indices of \`components\`. These indices refer to other components completely enclosed inside this component. 3. \`inside\`: an array of indices of \`components\`. This is a list of other components that completely enclose this component, sorted by nesting order. Thus, if \`components[5].inside\` is \`[3,9,2]\`, then \`components[3]\` encloses \`components[9]\`, which encloses \`components[2]\`, which encloses \`components[5]\`. `31:T8a5,function getCirculations (imgdata) { let [w,h] = [imgdata.width,imgdata.height]; let data = imgdata.data; function getRuns (x) { let last = false; let run = null; let runs = []; for (let y = 0; y < h; y++) { let pixel = data[(w*y+x)*4+3]; let current = pixel > 0; if (current) { if (run != null) run.ymax = y+1; else { run = { x:x, ymin: y, ymax:y+1 }; runs.push (run); } } else { run = null } } return runs } function runDifference (runs0,runs1) { runs0 = runs0.slice(0); if (runs0.length == 0) return runs0; if (runs1.length == 0) return runs0; let result = []; let [i0,i1] = [0,0]; while ( i0 < runs0.length && i1 < runs1.length ) { let [r0,r1] = [runs0[i0], runs1[i1]]; if (r0.ymax <= r1.ymin) { result.push(r0); i0++; } else if (r1.ymax <= r0.ymin) { i1++; } else { if (r0.ymin < r1.ymin) { result.push ({x:r0.x, ymin: r0.ymin, ymax:r1.ymin}); r0 = {x:r0.x, ymin:r1.ymin, ymax:r0.ymax}; } else { r0 = {x:r0.x, ymin:r1.ymax, ymax:r0.ymax}; } if (r0.ymax <= r0.ymin) i0++; else runs0[i0] = r0; } } result.push.apply(result,runs0.slice(i0)) return result; } let prevRuns = []; let connected = new ConnectedComponents(); let vEdge = (x) => { return (run) => [Vec(x,run.ymin),Vec(x,run.ymax)] }; for (let x= 0; x <= w; x++) { let runs = x == w ? [] : getRuns(x); let currMinusPrev = runDifference(runs, prevRuns); let prevMinusCurr = runDifference(prevRuns, runs); let verticalEdges = currMinusPrev.map(vEdge(x)).concat(prevMinusCurr.map(vEdge(x))); let horizontalEdges = []; for (let r of runs) { horizontalEdges.push ([Vec(r.x,r.ymin),Vec(r.x+1,r.ymin)]); horizontalEdges.push ([Vec(r.x,r.ymax),Vec(r.x+1,r.ymax)]); } for (let vEdge of verticalEdges) { connected.addVerticalEdge (vEdge); } for (let hEdge of horizontalEdges) { connected.addHorizontalEdge (hEdge); } prevRuns = runs } return connected; }32:T59f,canvas = { let [w,h] = [width, ~~(width*9/16)] let ctx = DOM.context2d(w,h,1) let imageData = ctx.getImageData(0,0,w,h); let paint = function (event) { let [x,y] = [event.offsetX,event.offsetY] ctx.fillStyle = `rgb(0,0,0)`; if (event.buttons) { if (event.buttons & 1) ctx.globalCompositeOperation = 'source-over' else ctx.globalCompositeOperation = 'destination-out' ctx.beginPath(); ctx.arc (x, y, viewof brushRadius.value, 0, 2*Math.PI) ctx.fill(); ctx.globalCompositeOperation = 'source-over' } } ctx.canvas._reset = function () { ctx.clearRect(0,0,w,h) imageData = ctx.getImageData(0,0,w,h); } ctx.canvas._refresh = function() { ctx.clearRect(0,0,w,h); ctx.lineWidth = viewof strokeThickness.value; drawCirculations(ctx, getCirculations(imageData), viewof strokeThickness.value == "none" ? null : viewof strokeColor.value, viewof fillStyle.value == 'none' ? null : viewof fillStyle.value == 'b/w' ? ['black','white'] : ['black','darkGray','gray','lightGray','white']) } ctx.canvas.oncontextmenu = (e) => { e.preventDefault() } ctx.canvas.onmousedown = (e) => { ctx.putImageData(imageData,0,0); paint(e) } ctx.canvas.onmouseup = (e) => { imageData = ctx.getImageData(0,0,w,h); ctx.canvas._refresh() } ctx.canvas.onmousemove = paint return ctx.canvas }33:T14da,class ConnectedComponents { constructor () { this.hash = [] this.components = [] this.closed = [] this.active = new Set() } // Returns a JSON from a ConnectedComponent. Useful for debugging. json () { return JSON.parse(JSON.stringify(this)) } // Returns an unused in the components array newComponentIndex () { for (let i = 0; i < this.components.length; i++) { if (this.components[i] === undefined) { return i; } } return this.components.length; } // Internal procedure to fix fields `contains` and `inside`. Called // by addVerticalEdge when component j is merged into component i _mergeComponents (i,j) { let [ci,cj] = [this.components[i],this.components[j]]; if (cj.leftmost.x < ci.leftmost.x) { ci.leftmost = cj.leftmost } let [icontains,jcontains] = [ci.contains,cj.contains]; for (let indexi = icontains.length-1; indexi >=0; indexi--) { let k = icontains[indexi]; let indexj = jcontains.indexOf(k); if (indexj >= 0) { icontains.splice(indexi,1); jcontains.splice(indexj,1); let inside = this.components[k].inside; let a = inside.indexOf(i); console.assert(a>=0); let b = inside.indexOf(j); console.assert(b>=0); console.assert(Math.abs(b-a) == 1); inside.splice(Math.min(a,b),2) } } for (let k of jcontains) { let inside = this.components[k].inside; let indexj = inside.indexOf(j); console.assert(indexj>=0); inside[indexj] = i; console.assert(icontains.indexOf(k) == -1); icontains.push(k) } } // Adds a new vertical edge to the scanline addVerticalEdge (edge) { let newIndex = this.newComponentIndex(); let component = { index : newIndex, ymin : edge[0].y, ymax : edge[1].y, points : [edge[0],edge[1]], leftmost : edge[0], inside : [], contains : [] }; this.components [component.index] = component; if (this.hash[component.ymin] !== undefined) { let c = this.hash[component.ymin]; this.hash[component.ymin] = undefined; this.components[component.index] = undefined; if (c.ymin == component.ymin) { c.ymin = component.ymax; c.points.unshift(component.points[1]); } else { console.assert(c.ymax == component.ymin); c.ymax = component.ymax; c.points.push (component.points[1]); } component = c; } if (this.hash[component.ymin] != undefined && this.hash[component.ymin].index != component.index) { let c2 = this.hash[component.ymin]; console.assert (component.index != c2.index); console.assert (c2.ymin == component.ymin); c2.points.reverse(); component.points.unshift(...c2.points.slice(0,c2.points.length-1)); component.ymin = c2.ymax; this.hash[c2.ymax] = undefined; if (component.index != newIndex && c2.index != newIndex) { this._mergeComponents (component.index, c2.index) } this.components[c2.index] = undefined; this.hash[c2.ymin] = undefined; this.active.delete(c2) } else { if (this.hash[component.ymax] !== undefined) { let c = this.hash[component.ymax]; this.hash[component.ymax] = undefined; if (c !== component) { if (component.index != newIndex && c.index != newIndex) { this._mergeComponents (c.index, component.index) } this.components[component.index] = undefined; this.active.delete(component) if (c.ymax == component.ymax) { c.ymax = component.ymin; component.points.reverse(); c.points.push(...component.points.slice(1)); } else { console.assert(c.ymin == component.ymax); c.ymin = component.ymin; c.points.unshift(...component.points.slice(0,component.points.length-1)); } component = c; } } } if (component.ymin < component.ymax) { this.hash[component.ymin] = this.hash[component.ymax] = component; this.active.add(component); } else { // Component has been closed. Look up for components in the // scanline that contain it for (let c of this.active) { if (c && c != component && c.ymin < edge[0].y && c.ymax > edge[1].y) { component.inside.push (c.index); c.contains.push (component.index) //console.assert(this.active.has(c)) } } // Sort them in y order component.inside.sort((i,j) => this.components[i].ymin - this.components[j].ymin); this.active.delete(component) this.closed.push(component) } } addHorizontalEdge (edge) { //this.edges.push(edge) console.assert(edge[0].y==edge[1].y); console.assert(this.hash[edge[0].y]); let c = this.hash[edge[0].y]; if (c != undefined) { if (c.ymin == edge[0].y) { c.points.unshift(edge[1]) } else { console.assert(c.ymax == edge[0].y); c.points.push(edge[1]) } } else { console.log ("Dangling h edge", edge) } } }34:[{"id":"0c9e1e2f00a520e9e08768d916fb13bbed7cf480ab2186bb2c96a77f0b91e894090a4167c38e5d1f9b92562113339741d1b2db440dc66555599b57f05ebd1eff","href":"https://static.observableusercontent.com/files/0c9e1e2f00a520e9e08768d916fb13bbed7cf480ab2186bb2c96a77f0b91e894090a4167c38e5d1f9b92562113339741d1b2db440dc66555599b57f05ebd1eff","name":"carpet.jpg","type":"image/jpeg","lastModified":1579450514743.902,"size":109529},{"id":"2bb8da8bbefe873cdbe289dd1a8e9c29113e7f5304234754b4bec86720eb4548e688d903dc1ecde418c7898ec2b6c11010b53d6879e514d60b34f6a9a57b425d","href":"https://static.observableusercontent.com/files/2bb8da8bbefe873cdbe289dd1a8e9c29113e7f5304234754b4bec86720eb4548e688d903dc1ecde418c7898ec2b6c11010b53d6879e514d60b34f6a9a57b425d","name":"staircase.jpg","type":"image/jpeg","lastModified":1579450204155.029,"size":57108},{"id":"7e9aca8e3dc55767fba48973cd561723fab2cb83ff67ebdcb27f2080abcd4d54e6c1ef560adbd04a1ab3dd841b1990d1efe411dc8ea601d9d104ccbc451ed58f","href":"https://static.observableusercontent.com/files/7e9aca8e3dc55767fba48973cd561723fab2cb83ff67ebdcb27f2080abcd4d54e6c1ef560adbd04a1ab3dd841b1990d1efe411dc8ea601d9d104ccbc451ed58f","name":"forte.png","type":"image/png","lastModified":1579385865405.189,"size":447060},{"id":"bf7fcc14eebb1e406e9769ed7c890853bbaf50a1e5497c91c4994e3e880c743298a5c88e2e4fe5948d0b3720642a567d84cab78f588d0729b0a5d9db4185ead0","href":"https://static.observableusercontent.com/files/bf7fcc14eebb1e406e9769ed7c890853bbaf50a1e5497c91c4994e3e880c743298a5c88e2e4fe5948d0b3720642a567d84cab78f588d0729b0a5d9db4185ead0","name":"celtic_cross.png","type":"image/png","lastModified":1579381072979.121,"size":130291},{"id":"1c75a05df5f94dd7585af60cc4459031e85c69eb28709fcd8979474121953f41e4e20638d9470b07c167e1dd59b49b25dd06bfdd787bcb6ff642c4b6d7a6c2df","href":"https://static.observableusercontent.com/files/1c75a05df5f94dd7585af60cc4459031e85c69eb28709fcd8979474121953f41e4e20638d9470b07c167e1dd59b49b25dd06bfdd787bcb6ff642c4b6d7a6c2df","name":"wire.jpg","type":"image/jpeg","lastModified":1579434330457.683,"size":68962}] 2e:{"title":"Bitmap tracing","cells":[{"id":0,"value":"md`# Bitmap tracing\n\nThis is my take on the problem of tracing a bitmap, i.e., obtaining polygons enclosing the foreground/background areas. The \"de facto\" standard for this is the [*potrace*](http://potrace.sourceforge.net/) package, written and maintained by Peter Selinger. There are quite a few versions of it, as well as JavaScript ports ([search *npm* for 'potrace'](npmjs.com/search?q=potrace) and you will find a bunch of them). Potrace contains much more than the core bitmap-to-polygon functionality, like fitting Bézier curves to the polygons and vectorizing raster images into SVGs.\n\nThe approach taken here differs from that of potrace in that it uses a scanline algorithm and finds all circulations in a single scan, together with the topological information, i.e., which circulations are enclosed in which, so that polygons with holes can be handled correctly. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"comment('Main function')","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":339,"value":"comment('Generates a function that classifies a pixel as foreground if its luminosity value is less than `maxValue`')","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"function isDark (maxValue = 127) {\n let rgbaWord = new Uint32Array(1);\n let rgba = new Uint8Array(rgbaWord.buffer);\n return (pixel) => {\n rgbaWord[0] = pixel;\n return rgba[0]*0.2126+rgba[1]*0.7152+rgba[2]*0.0722 <= maxValue\n }\n}\n ","pinned":true,"hidden":false,"mode":"ojs"},{"id":342,"value":"comment('Utility function to classify pixels of an image. `imgData` is an `ImageData` object. `isForeground` is a function that takes a pixel (an rgba value) and returns `true` if it is to be considered foreground, and defaults to a function that selects pixels with luminosity below 50%. Returns a mask image fit to be used with `getCirculations()`.')","pinned":false,"hidden":false,"mode":"ojs"},{"id":178,"value":"function segmentImage(imgData, isForeground = isDark()) {\n let [w,h] = [imgData.width,imgData.height]\n \n let mask = new ImageData(w,h);\n let src = new Uint32Array (imgData.data.buffer);\n let dst = new Uint32Array (mask.data.buffer);\n \n for (let i = 0; i < src.length; i++) {\n if (isForeground(src[i])) dst[i] = 0xff000000 // opaque black\n }\n return mask\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":356,"value":"comment(\"Utility function to draw circulations. `ctx` is a canvas context, `connected` is the `ConnectedComponents` object returned by `getCirculations()`. If `stroke` is given, draws the border of each polygon in that color. If `fill` is given, it should be a list of colors that will be used to fill successive nesting levels of circulations. If there are more nesting levels than there are colors in `fill`, they are cyclically repeated. Drawing is performed in nesting order - outer before inner - so that polygons with holes will be rendered correctly.\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":204,"value":"function drawCirculations (ctx, connected, stroke = 'red', fill = ['black','lightGray']) {\n let comps = connected.closed.slice(0);\n comps.reverse();\n let maxLevel = Math.max(...comps.map((c)=>c.inside.length))+1;\n for (let comp of comps) {\n ctx.beginPath();\n let curve = new Curve(...comp.points)//.subsample(0.7)\n let {x,y} = curve[0];\n ctx.moveTo(x,y);\n for (let {x,y} of curve) {\n ctx.lineTo(x,y)\n }\n if (fill) {\n ctx.fillStyle = fill[comp.inside.length % fill.length];\n ctx.fill()\n }\n if (stroke) {\n ctx.strokeStyle = stroke\n ctx.stroke()\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":361,"value":"md`## Image segmentation demo\n\nInput image: ${bindSelect({options:Object.keys(images)},viewof imageName)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":228,"value":"img = images[imageName].image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":374,"value":"md`### Segmented Image\nThreshold luminosity: ${bindSliderNumber({min:1,max:256,step:1},viewof darkLevel)}` ","pinned":false,"hidden":false,"mode":"ojs"},{"id":372,"value":"segmented = {\n let [w,h] = [img.width,img.height]\n let ctx = new DOM.context2d(w,h,1);\n ctx.drawImage(img,0,0);\n let imgData = ctx.getImageData(0,0,img.width,img.height);\n let mask = segmentImage(imgData,isDark(darkLevel))\n ctx.putImageData(mask,0,0)\n return ctx.canvas\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":443,"value":"md`### Circulations\n${drawUI()}` ","pinned":false,"hidden":false,"mode":"ojs"},{"id":176,"value":"{\n let [w,h] = [segmented.width,segmented.height]\n let ctx = new DOM.context2d(w,h,1);\n ctx.drawImage(segmented,0,0);\n let mask = ctx.getImageData(0,0,w,h);\n ctx.clearRect(0,0,w,h)\n let connected = getCirculations(mask);\n ctx.lineWidth = viewof strokeThickness.value;\n drawCirculations (ctx, connected,\n strokeThickness == \"none\" ? null : strokeColor,\n fillStyle == 'none' ? null :\n fillStyle == 'b/w' ? ['black','white'] : \n ['black','darkGray','gray','lightGray','white'])\n return ctx.canvas\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"{\n let clear = html``\n clear.onclick = () => { canvas._reset() }\n \n return md`## Painting demo\n\n Use the mouse to paint in the canvas below. Dragging with the *left* button pressed adds foreground pixels. Doing the same with the *right* (or *middle*) button erases pixels. Circulations are drawn when mouse button is released after each brush stroke.\n\n${clear}
\n\n Brush radius: ${bindSliderNumber({min:1, max:50, step: 1}, viewof brushRadius)}
\n \n ${drawUI()}\n \n `\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":64,"value":"comment('Auxiliary class for keeping track of circulations as vertical and horizontal edges are added in the left-to-right scanline algorithm implemented in `getCirculations()`')","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`## User interface variables`","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"viewof showNesting = new View(false)","pinned":true,"hidden":false,"mode":"ojs"},{"id":136,"value":"viewof brushRadius = new View (10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":369,"value":"viewof darkLevel = new View(127)","pinned":true,"hidden":false,"mode":"ojs"},{"id":389,"value":"viewof fillStyle = new View('none')","pinned":true,"hidden":false,"mode":"ojs"},{"id":424,"value":"viewof strokeThickness = new View('1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":393,"value":"viewof strokeColor = new View('#ff0000')","pinned":true,"hidden":false,"mode":"ojs"},{"id":392,"value":"drawUI = () => html`Circulation drawing style:
\nBorder: thickness ${bindSelect({options:[\"none\",\"1\",\"2\",\"3\",\"4\"]},viewof strokeThickness)} color ${bindColor({},viewof strokeColor)}
\nFill: ${bindSelect({options:[\"none\", \"b/w\", \"grays\"]}, viewof fillStyle)}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":144,"value":"{\n strokeColor;\n strokeThickness;\n fillStyle;\n canvas._refresh()\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":451,"value":"viewof imageName = new View(\"celtic\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":459,"value":"images = ({\"carpet\":FileAttachment(\"carpet.jpg\"),\n \"staircase\":FileAttachment(\"staircase.jpg\"),\n \"wire\":FileAttachment(\"wire.jpg\"),\n \"fort\":FileAttachment(\"forte.png\"),\n \"celtic\":FileAttachment(\"celtic_cross.png\")})","pinned":true,"hidden":false,"mode":"ojs"},{"id":125,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"import { comment } from \"@esperanc/notebook-css-utilities\" ","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"import { Vec, Curve } from \"@esperanc/2d-geometry-utils\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":129,"value":"import { bindSliderNumber, bindRadioGroup, bindSelect, bindCheckGroup, bindCheckbox, bindFile, bindColor, View } from \"@esperanc/inline-inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}