45:["$","title",null,{"children":"Object Shape Approximation | Luis Retondaro | Observable"}] 4d:T5a0,class Patch { constructor(img,imgD) { this.parent = null; this.selected = false; this.pinned = false; this.collision = false; this.visible = true; this.balls = powerDiagram(img,imgD); this.tree = Q(this.balls,0.5); this.tree.tree.computeEnclosingCircles(); this.img = img; this.x = 0; this.y = 0; this.w = img.width; this.h = img.height; this.level = 0; this.neighbors = []; } translate(p) { this.tree.translate(p); this.x += p.x; this.y += p.y } origin() { let dx = -(this.tree.ball.x); let dy = -(this.tree.ball.y); this.x += dx; this.y += dy; this.tree.origin(); } draw(ctx,tree) { if (tree) { this.tree.draw(ctx,true,true,false,"#0000004f","#0000007f","#0000004f","#0000007f"); } ctx.drawImage(this.img,this.x,this.y); } box() { return [ Vec(this.x,this.y), Vec(this.x+this.w, this.y), Vec(this.x+this.w,this.y+this.h), Vec(this.x,this.y+this.h) ] } contains(p) { return this.tree.intersecting(p); } likelyNeighbor (other, gap) { return this.tree.tree.ball.distance(other.tree.tree.ball) <= gap; } }4e:T9a8,class PatchCluster extends Array { constructor() { super(); this.parent = null; this.dirty = false; } insert (patch) { patch.parent = this; this.push(patch); } union (other) { for (let o of other) { this.insert(o); } other = null; } // Returns a bounding box for the cluster box () { if (this.length == 0) return null; var box = this[0].box(); for (var i = 1; i < this.length; i++) { let other = this[i].box(); let x1 = Math.min (box[0].x, other[0].x); let y1 = Math.min (box[0].y, other[0].y); let x2 = Math.max (box[2].x, other[2].x); let y2 = Math.max (box[2].y, other[2].y); box = [Vec(x1,y1),Vec(x2,y1),Vec(x2,y2),Vec(x1,y2)]; } return box; } intersect(b1,b2) { if ( ((b2[0].x > b1[0].x && b2[0].x < b1[1].x) || (b2[0].x < b1[0].x && b2[1].x > b1[0].x) ) && ((b2[0].y > b1[0].y && b2[0].y < b1[2].y) || (b2[0].y < b1[0].y && b2[2].y > b1[0].y) ) ) { return true; } return false; } dist (other) { let box = this.box(); let otherbox = other.box(); if (this.intersect(box,otherbox)) return [0,0]; return [ Math.min(Math.abs(otherbox[0].x-box[1].x), Math.abs(otherbox[1].x-box[0].x)), Math.min(Math.abs(otherbox[0].y-box[3].y), Math.abs(otherbox[3].y-box[0].y)) ]; } // True if PatchCluster contains point p contains (p) { for (let e of this) { if (e.contains (p)) return true; } return false; /*let box = [ p, p, p, p ] ; if (this.intersect(box,this.box())) return true; return false;*/ } translate (p) { for (let patch of this) { patch.translate(p); } } /* cluster (other) { } cluster (other) { let level = -1; let query1 = other.closestSegsNew(this.box[1],this.box[2]); if (query1.dist <= 2) { //a character level = 0; } else { (query1.dist <= 8) { // a word level = 1; } } if (level < 0) { } return level; }*/ } 4f:[{"id":"1f2a4a1a3ed2f1b04369407bd88acc5a8eda79988e00e6c3de6528d0fc1c8807b3a92cc113dfbf16d11383a4df363d77c6ea863116865dc7076426be72c562f4","href":"https://static.observableusercontent.com/files/1f2a4a1a3ed2f1b04369407bd88acc5a8eda79988e00e6c3de6528d0fc1c8807b3a92cc113dfbf16d11383a4df363d77c6ea863116865dc7076426be72c562f4","name":"rabbit_256_blue.png","type":"image/png","lastModified":1616272783974.451,"size":1501},{"id":"085658179932347cc72db1a0ff15836b18a2b33d72be7ef7018fee84a9ad8c1ab903d5967c579d38b32ad6c059abca6b341fd12f6478c11e357c3a66dc7be262","href":"https://static.observableusercontent.com/files/085658179932347cc72db1a0ff15836b18a2b33d72be7ef7018fee84a9ad8c1ab903d5967c579d38b32ad6c059abca6b341fd12f6478c11e357c3a66dc7be262","name":"rabbit_border.png","type":"image/png","lastModified":1616272793365.164,"size":10587},{"id":"2c41114cc1451110849f8f6e06db9f6f23ae94ec1dd9f20be6d41c9ce14767d92fd9bff8563a90e4c2dc7e83bbfe9b666b31d991a31a3990d5981122b911a6af","href":"https://static.observableusercontent.com/files/2c41114cc1451110849f8f6e06db9f6f23ae94ec1dd9f20be6d41c9ce14767d92fd9bff8563a90e4c2dc7e83bbfe9b666b31d991a31a3990d5981122b911a6af","name":"pangram_extra@1.png","type":"image/png","lastModified":1620830706741.929,"size":16727}] 49:{"id":"00a46c57e4732cea","slug":"object-shape-approximation","title":"Object Shape Approximation","thumbnail":"73d8163b9345d900b9e14a107a2d74a6a807426eeda7dc25dbe35831af469db9","access_level":"public","create_time":"$D2021-03-20T19:09:25.096Z","update_time":"$D2021-07-22T12:08:58.782Z","view_time":null,"first_public_time":"$D2021-03-20T21:17:12.183Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":"starter_2024","bio":".","followed_by_you":false,"follows_you":false},"version":498,"publish_version":498,"role":null,"authored":false,"authors":[{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"bio":".","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"0781ac0b2927381a","slug":"wip","title":"WIP","owner":{"id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro"}},"type":"notebook","body":{"titling":"auto","title":"Object Shape Approximation","cells":[{"id":0,"value":"md`# Object Shape Approximation\n\n### Patches\n\nIn this notebook, I use a simple implementation of hierarchical discrete medial axis to enable ball tree construction to object shape approximation by covering. Very useful for computing distance between objects with irregular shapes and their possible intersections.\n\nIn a scanned image I take the segments as objects of interest, which I call a \"Patch\".\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"md `## Example 1: Filled rabbit image`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"Rabbit256 = FileAttachment(\"rabbit_256_blue.png\").image();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"showBallTree(R256);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"md `## Contouring rabbit image`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"RabbitBorder = FileAttachment(\"rabbit_border.png\").image();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"showBallTree(RBorder);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"showBallTree(RPangram);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"RPangramimg = FileAttachment(\"pangram_extra@1.png\").image();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"md `## Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"R256 = new Patch(Rabbit256,imgData(Rabbit256));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"RBorder = new Patch(RabbitBorder).tree;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"RPangram = new Patch(RPangramimg).tree;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"md `## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"function showBallTree(tree, name = \"\") {\n let title = md `### Ball tree demonstration:\n Red balls are leaves on ball tree.`;\n\n let width = 900;\n let canvas = DOM.canvas(width*2, width);\n let ctx = canvas.getContext(\"2d\");\n ctx.imageSmoothingEnabled = true;\n\n ctx.font = '15px serif';\n ctx.fillText(` Tree height: ${tree.height}`, 10, 20);\n ctx.lineWidth = 1.8; \n ctx.fillStyle = '#0000000f';\n ctx.strokeStyle = '#0000000f';\n tree.draw(ctx,true,false,false,'#ee000000','#0000004f','#ee00000f','#ee00007f');\n\n return html`

${title}\n ${canvas}

`;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"$4d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"$4e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":466,"value":"function powerDiagram (img, imgD) {\n let I = _imgToArray(img,imgD);\n let F = Pow2Array(I);\n let dma = DMA(F);\n if (dma.length > 0) {\n let PD = new PowerDiagram(dma);\n let balls=[];\n for (let i=0; i< PD.sites.length; i++) {\n balls.push(new Ball(PD.sites[i].center.x, PD.sites[i].center.y, PD.sites[i].radius));\n }\n if (balls.length == 0) return [new Ball (0,0,0.5)];\n return balls;\n } else {\n return [new Ball (0,0,0.5)];\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"function pyramidal(F) {\n let Fn = Pow2Array(F);\n let levels = Math.log2(Fn.length)+ 1;\n let dma = DMA(Fn);\n if (dma.length > 0) {\n let PDlevel = new PowerDiagram(dma);\n if (PDlevel.sites.length == 0) PDlevel.sites.push(new Site(Vec(0,0),0.5));\n return PDlevel.sites;\n } \n return [new Site(Vec(0,0),0.5)];\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"function _imgToArray(img, imgData) {\n var _rows = img.height;\n var _cols = img.width;\n\n // Get the CanvasPixelArray from the given coordinates and dimensions.\n var imgD = imgData; \n\n var mmap = [];\n for (var x=0; x < _cols; x++) {\n mmap[x] = [];\n for (var y =0; y < _rows; y++) {\n var ind = (x + (y*_cols))*4;\n var alpha = imgD.data[ind+3];\n if (alpha < 10) {\n mmap[x][y] = 0;\n } else {\n mmap[x][y] = 1;\n }\n }\t\n }\n return mmap;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"function Pow2Array(A) {\n let _r = A[0].length;\n let _c = A.length;\n\n let dd = Math.max(_r,_c);\n let dim = Math.ceil(Math.log2(dd));\n\n let _rows = Math.pow(2,dim);\n let _cols = _rows;\n\n let ret = [];\n for (var i=0; i < _cols; i++) {\n ret[i] = [];\n for (var j=0; j < _rows; j++) {\n if (i >= A.length || j >= A[0].length) {\n ret[i][j] = 0;\n } else {\n ret[i][j] = A[i][j];\n }\n }\n }\n return ret;\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"function cropImage (canvas, sx, sy, sw, sh) {\n let buffer = DOM.canvas (sw, sh, 1);\n let b_ctx = buffer.getContext(\"2d\");\n\n // draw the main canvas on our buffer one\n // drawImage(source, source_X, source_Y, source_Width, source_Height, \n // dest_X, dest_Y, dest_Width, dest_Height)\n b_ctx.drawImage(canvas, sx, sy, sw, sh,\n 0, 0, sw, sh);\n\n // now call the callback with the dataURL of our buffer canvas\n let im = new Image();\n im.crossOrigin = \"anonymous\";\n im.width = sw;\n im.height = sh;\n im.src = buffer.toDataURL();\n return {img:im, data:b_ctx.getImageData(0,0,sw,sh)};\n};\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"function coveringPower (p,t,s) {\n let d = p.dist(t.center);\n return d-t.radius+(s.radius/2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"function sumGP(a1, q, n) {\n\t let qn = Math.pow(q,n);\n\t return (a1*(qn-1)) / (q-1);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md `## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"import { Vector, Vec } from \"@esperanc/2d-geometry-utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"import {PowerDiagram, Site} from \"@lretondaro/power-diagram\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"import {DMA} from '@lretondaro/discrete-medial-axis'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"import {Heap, Queue, Stack, Ball, BallTree, BTNode} from '@lretondaro/basic-data-structures'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"import {bottomUp, Q} from '@lretondaro/optimal-ball-trees'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"import {Bbox, imgData} from '@lretondaro/utils-library'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4f","stdlib":"1"}} 44:null