25:["$","title",null,{"children":"Power diagram | Luis Retondaro | Observable"}] 4b:T7df,class PowerDiagram { constructor (F,todraw) { this.sites = []; this.width = F.length; this.height = F[0].length; this.pix = []; this.todraw = todraw; for (var x=0; x < this.width; x++) { this.pix[x] = []; for (var y=0; y < this.height; y++) { if (F[x][y] != 0) { let p = Vec(x+0.5,y+0.5); let rr = Math.sqrt(F[x][y]); let S = new Site(p,rr-0.25); //-0.5 this.add(S); } } } if (todraw) { this.computeDiagram(); } } add (site) { this.sites.push(site); } addItem (p,s,m) { let v = { site: s, visited:false, power: m}; this.pix[p.x][p.y] = v; } power (p,s) { let d = p.dist(s.center); return d*d-s.radius*s.radius; } computeDiagram() { for (var i=0; i < this.width; i++) { for (var j=0; j < this.height; j++) { let minPower = Number.POSITIVE_INFINITY; let minK = 0; let border = false; let borderK = 0; let p = Vec(i,j); let neighbors = 0; for (var k = 0; k < this.sites.length; k++) { let pwr = this.power(p,this.sites[k]); if (pwr < minPower) { minPower = pwr; minK = k; border = false; } } this.addItem(p,minK,minPower); } } } draw(ctx) { if (this.todraw) { if (this.sites.length == 0) return; for (var x=0; x < this.width; x++) { for (var y=0; y < this.height; y++) { ctx.fillStyle = this.sites[this.pix[x][y].site].color; ctx.fillRect(x, y, 1, 1); } } } } }4c:[] 47:{"id":"e5d75345cce7cba7","slug":"power-diagram","title":"Power diagram","thumbnail":"91f3e5a89926bbabb18df073a086716d25256e1f02f0725cc454830fc682fc42","access_level":"public","create_time":"$D2019-06-12T20:27:31.177Z","update_time":"$D2021-12-28T00:42:10.810Z","view_time":null,"first_public_time":"$D2019-06-13T17:03:02.066Z","has_unpublished_edits":null,"fork":{"id":"66fe094aaf1c38b3","slug":"power-diagram","title":"Power diagram","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"stars":5,"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":320,"publish_version":320,"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":1,"collection":{"id":"aac69fe6b3972389","slug":"utility-library","title":"Utility & Library","owner":{"id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro"}},"type":"notebook","body":{"titling":"auto","title":"Power diagram","cells":[{"id":0,"value":"md`# Power diagram`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"md`This notebook contains a generic **power diagram** implementation to be used in the pyramidal structure described on the paper:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"md `[BROUTTA, Alain; COEURJOLLY, David; SIVIGNON, Isabelle. Hierarchical discrete medial axis for sphere-tree construction. In: International Workshop on Combinatorial Image Analysis. Springer, Berlin, Heidelberg, 2009. p. 56-67.](https://www.researchgate.net/profile/David_Coeurjolly/publication/221016922_Hierarchical_Discrete_Medial_Axis_for_Sphere-Tree_Construction/links/0fcfd508fcd1b22c0b000000.pdf)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"md `## Introduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"md`In computational geometry, the Power diagram (also known as the *Laguerre diagram*) is a generalization of the Voronoi Diagram. This tool is widely used for ball interaction computation and surface\nreconstruction. We consider a set of sites *S = {s_i }*, such that each point\n*s_i* is associated with a radius *r_i* . The power *σ_i(p)* of a point *p* according to the\nsite s_i is given by:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":254,"value":"tex.block`\\sigma_i(p)=d(p,s_i)-r_i`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"md`If ${tex`\\sigma_i(p) < 0`}, ${tex`p`} belongs to the ball of center ${tex`s_i`} and radius ${tex`r_i`}. The Power diagram is based on the metric induced by ${tex`\\sigma`} and it is a decomposition of the object into\ncells ${tex`C = \\{c_i\\}`} associated with each site ${tex`s_i`} such that:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":260,"value":"tex.block`c_i = \\{ p\\in \\mathbb{R}^d : \\sigma_i(p) < \\sigma_j(p), i \\neq j \\}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"md`In discrete geometry, the power labeling is defined as the power diagram\nlabeling of grid points. More precisely, we assign to each grid point of the\nplane the index of the cell containing it in the power diagram, so the discrete\npower diagram is a labelling for each voxel by the circle which best covers it.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"md`## Demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"md`The gray right area represents the matrix of the points in the image. Click on it to insert new points or remove them.\n\n The corresponding Power Diagram will be displayed on the left`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"demointerface = {\n let div = html``;\n div.append(showDiagram());\n div.append(showInterface);\n return div\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"md`The function **showDiagram** draws the power diagram for *mymatrix*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"showDiagram = function() {\n let canvas = html`