30:T8ca,md`# Square Packing This notebook was inspired by [this blog post](https://blog.interactivethings.com/simple-square-packing-algorithm-ddd3c2793711) by Tomas Carnecky. The problem consists of packing a collection of squares of varied sizes so that they form a compact shape, usually a square or a circle. Here, we use more of a brute force approach, which may be unsuitable for large collections. The algorithm consists of placing one square at a time, from the largest to the smallest. At each step we maintain a polygon describing the boundary of the subset of squares already placed. For a new square, we try placing it flushed to one of the polygon edges and sharing at least one vertex. We choose the position that is closer to the arrangement center. In fact, we implemented two heuristics: - In the "first fit" algorithm, all vertices of the polygon are first sorted in distance order from the center, and the first vertex that yields a position so that the new square can be placed contiguously to it is chosen. - In the "best fit" algorithm, all positions are tested and the closest to the center is chosen. In order to simplify the border of the polygon so we have fewer postions to test, every so often we apply a "closing" [morphological operation](https://en.wikipedia.org/wiki/Mathematical_morphology) (dilation followed by erosion), which removes small holes where later squares will likely never fit anyway. This speeds up the placement, at the cost of making the arrangement larger. The main tool used here are orthogonal polygons, which can be very neatly represented by [vertex lists](https://observablehq.com/@esperanc/vertex-lists), and support all of the operations needed for the algorithm. However, the intersection test between each new square and the polygon was unbearably slow. In order to speed up the algorithm, the polygon is first split into a collection of rectangles having maximal width (this is a fast operation with vertex lists). These, in turn. have their y coordinates indexed by using an [interval tree](https://en.wikipedia.org/wiki/Interval_tree). This way, only rectangles having y coordinates intersecting those of the square are tested. A small demo of this data-structure is also included here. `31:T50f,viewof polygonDemo = { let ctx = DOM.context2d(640,480); let polygon = new VList(); let rlist = new RectList (polygon); let operation; let lastPos = [100,100], side, R; let setOperation = (opname) => { operation = (opname=="draw") ? union : difference; } setOperation ("draw"); let refresh = () => { ctx.clearRect(0,0,640,480); let hit = rlist.rectIntersection(R); ctx.strokeStyle = hit ? "red" : "black"; drawPolygon (ctx, polygon); drawVList(ctx,R); } let setBrush = (s) => { side = s; R = rectangle (lastPos, [side,side]); refresh(); } setBrush (20); let dilatePolygon = ()=>{ polygon = dilate(polygon,side); rlist = new RectList (polygon); refresh(); } let erodePolygon = () => { polygon = erode(polygon,side); rlist = new RectList (polygon); refresh(); } ctx.canvas.onmousemove = ctx.canvas.onmousedown = (e) => { let c = side/Math.sqrt(2); lastPos = [e.offsetX-c,e.offsetY-c]; R = rectangle(lastPos,[side,side]); if (e.buttons != 0) { polygon = operation(polygon,R); rlist = new RectList (polygon); } refresh(); } refresh(); ctx.canvas.value = { setOperation, setBrush, dilatePolygon, erodePolygon }; return ctx.canvas; }32:T19f7,testPolygon = jsonToVlist(`[{"w":1,"p":[182.60181767582546,116.565338576438]},{"w":-1,"p":[220.549149597846,116.565338576438]},{"w":1,"p":[170.76965810962622,117.38228965091227]},{"w":-1,"p":[182.60181767582546,117.38228965091227]},{"w":1,"p":[220.549149597846,119.21086434177136]},{"w":-1,"p":[232.38130916404523,119.21086434177136]},{"w":1,"p":[232.38130916404523,121.04302390797059]},{"w":-1,"p":[242.38130916404523,121.04302390797059]},{"w":1,"p":[154.02648228028195,121.28268621493012]},{"w":-1,"p":[164.98093343038528,121.28268621493012]},{"w":1,"p":[140.14853645619394,129.04670200918386]},{"w":-1,"p":[150.14853645619394,129.04670200918386]},{"w":1,"p":[168.5876253707797,129.2144492171115]},{"w":-1,"p":[170.76965810962622,129.2144492171115]},{"w":1,"p":[242.38130916404523,131.70256031860896]},{"w":-1,"p":[250.87347995686702,131.70256031860896]},{"w":1,"p":[150.14853645619394,132.23713736503345]},{"w":-1,"p":[154.02648228028195,132.23713736503345]},{"w":1,"p":[164.98093343038528,132.92739871549384]},{"w":-1,"p":[168.5876253707797,132.92739871549384]},{"w":1,"p":[250.87347995686702,137.14141722811118]},{"w":-1,"p":[261.8279311069703,137.14141722811118]},{"w":1,"p":[136.7321285911952,139.04670200918386]},{"w":-1,"p":[140.14853645619394,139.04670200918386]},{"w":1,"p":[124.02402095959684,146.75546580458047]},{"w":-1,"p":[134.02402095959684,146.75546580458047]},{"w":1,"p":[261.8279311069703,148.0958683782145]},{"w":-1,"p":[270.61226870878687,148.0958683782145]},{"w":1,"p":[134.02402095959684,152.4631098741826]},{"w":-1,"p":[136.7321285911952,152.4631098741826]},{"w":1,"p":[122.1918613933976,156.75546580458047]},{"w":-1,"p":[124.02402095959684,156.75546580458047]},{"w":-1,"p":[258.78010914258766,159.92802794441374]},{"w":1,"p":[270.61226870878687,159.92802794441374]},{"w":1,"p":[262.37083303481916,162.13968577580124]},{"w":-1,"p":[274.20299260101837,162.13968577580124]},{"w":-1,"p":[243.94771216839632,162.92826535240584]},{"w":1,"p":[258.78010914258766,162.92826535240584]},{"w":1,"p":[243.94771216839632,166.53495729280027]},{"w":-1,"p":[244.48228921482084,166.53495729280027]},{"w":1,"p":[244.48228921482084,168.11398096573143]},{"w":-1,"p":[262.37083303481916,168.11398096573143]},{"w":1,"p":[120.85748485211961,169.59373145782882]},{"w":-1,"p":[122.1918613933976,169.59373145782882]},{"w":1,"p":[274.20299260101837,173.97184534200048]},{"w":-1,"p":[276.5129686585501,173.97184534200048]},{"w":1,"p":[116.38534889712002,178.53800336782797]},{"w":-1,"p":[120.85748485211961,178.53800336782797]},{"w":1,"p":[276.5129686585501,181.78942564539466]},{"w":-1,"p":[282.83752397888685,181.78942564539466]},{"w":-1,"p":[264.3849701376473,188.11398096573143]},{"w":1,"p":[282.83752397888685,188.11398096573143]},{"w":1,"p":[264.3849701376473,191.8603891619988]},{"w":-1,"p":[284.851661081715,191.8603891619988]},{"w":-1,"p":[278.52710576137827,198.18494448233557]},{"w":1,"p":[284.851661081715,198.18494448233557]},{"w":1,"p":[278.52710576137827,206.00252478572975]},{"w":-1,"p":[285.383106356159,206.00252478572975]},{"w":-1,"p":[276.43883444615983,214.9467966957289]},{"w":1,"p":[285.383106356159,214.9467966957289]},{"w":-1,"p":[116.38534889712002,218.7872269628242]},{"w":1,"p":[118.57828223000394,218.7872269628242]},{"w":-1,"p":[262.2966988224289,220.1446604094607]},{"w":1,"p":[276.43883444615983,220.1446604094607]},{"w":1,"p":[262.2966988224289,223.3230328614185]},{"w":-1,"p":[280.04625039018373,223.3230328614185]},{"w":-1,"p":[118.57828223000394,230.61938652902344]},{"w":1,"p":[130.41044179620317,230.61938652902344]},{"w":-1,"p":[272.3002836977689,231.06899955383335]},{"w":1,"p":[280.04625039018373,231.06899955383335]},{"w":1,"p":[122.85956534850729,234.9117424594213]},{"w":-1,"p":[130.41044179620317,234.9117424594213]},{"w":-1,"p":[271.422575281673,235.15519242761775]},{"w":1,"p":[272.3002836977689,235.15519242761775]},{"w":-1,"p":[133.8140164986106,240.34102022800187]},{"w":1,"p":[148.64641347280195,240.34102022800187]},{"w":-1,"p":[241.10070624333713,243.4152796613258]},{"w":1,"p":[244.44161370031551,243.4152796613258]},{"w":1,"p":[133.8140164986106,244.48228921482084]},{"w":-1,"p":[148.64641347280195,244.48228921482084]},{"w":-1,"p":[122.85956534850729,245.86619360952463]},{"w":1,"p":[129.28646529591146,245.86619360952463]},{"w":-1,"p":[267.01997736692164,246.10964357772107]},{"w":1,"p":[271.422575281673,246.10964357772107]},{"w":1,"p":[241.10070624333713,247.32280790010273]},{"w":-1,"p":[244.44161370031551,247.32280790010273]},{"w":-1,"p":[241.10070624333713,253.6473632204395]},{"w":1,"p":[249.27401067450683,253.6473632204395]},{"w":-1,"p":[259.2740106745068,253.8556102701359]},{"w":1,"p":[267.01997736692164,253.8556102701359]},{"w":-1,"p":[129.28646529591146,254.48228921482084]},{"w":1,"p":[139.28646529591146,254.48228921482084]},{"w":-1,"p":[139.28646529591146,257.89869707981956]},{"w":1,"p":[146.4018173041205,257.89869707981956]},{"w":1,"p":[241.10070624333713,259.53979515792287]},{"w":-1,"p":[246.92659465219535,259.53979515792287]},{"w":-1,"p":[220.1446604094607,262.2966988224289]},{"w":1,"p":[223.3230328614185,262.2966988224289]},{"w":-1,"p":[169.18842802042306,262.79060035434804]},{"w":1,"p":[173.97184534200048,262.79060035434804]},{"w":-1,"p":[249.27401067450683,263.6473632204395]},{"w":1,"p":[259.2740106745068,263.6473632204395]},{"w":-1,"p":[188.11398096573143,263.87855882726524]},{"w":1,"p":[191.8603891619988,263.87855882726524]},{"w":1,"p":[169.18842802042306,265.1005764118798]},{"w":-1,"p":[173.97184534200048,265.1005764118798]},{"w":-1,"p":[146.4018173041205,270.26913733911545]},{"w":1,"p":[157.35626845422382,270.26913733911545]},{"w":-1,"p":[235.97214350209202,270.49424630802616]},{"w":1,"p":[246.92659465219535,270.49424630802616]},{"w":-1,"p":[157.35626845422382,271.14684575521136]},{"w":1,"p":[162.13968577580124,271.14684575521136]},{"w":1,"p":[220.1446604094607,272.1889057985964]},{"w":-1,"p":[223.3230328614185,272.1889057985964]},{"w":-1,"p":[231.06899955383335,272.1889057985964]},{"w":1,"p":[235.97214350209202,272.1889057985964]},{"w":-1,"p":[162.13968577580124,276.932735978079]},{"w":1,"p":[181.78942564539466,276.932735978079]},{"w":1,"p":[188.11398096573143,276.932735978079]},{"w":-1,"p":[191.8603891619988,276.932735978079]},{"w":-1,"p":[194.4385362860682,278.0206944509962]},{"w":1,"p":[198.2565580933149,278.0206944509962]},{"w":-1,"p":[214.9467966957289,279.9348724910112]},{"w":1,"p":[231.06899955383335,279.9348724910112]},{"w":-1,"p":[181.78942564539466,283.25729129841574]},{"w":1,"p":[194.4385362860682,283.25729129841574]},{"w":-1,"p":[198.2565580933149,285.383106356159]},{"w":1,"p":[214.9467966957289,285.383106356159]}]`) 33:T41a,// A data structure for quick intersection tests against an orthogonal polygon class RectList { // Constructor from a vertex list constructor (vlist) { this.rects = vlist.rectangles(); this.it = createIntervalTree(this.rects.map(r=>{ let interval = [r[0].p[1],r[3].p[1]]; interval.rect = r return interval })) } rangeSearch (ymin,ymax) { let all = []; this.it.queryInterval (ymin,ymax,interval=>{all.push(interval)}); return all; } // Returns true if polygon intersects point p pointIntersection (p) { for (let interval of this.rangeSearch(p[1],p[1]+1)) { let r = interval.rect; if (r[3].p[1]>p[1] && r[3].p[0]>p[0] && r[0].p[0]<=p[0]) return true; } return false } // Returns true if polygon intersects rectangle R rectIntersection (R) { let ymin = R[0].p[1]; let ymax = R[3].p[1]; for (let interval of this.rangeSearch(ymin,ymax)) { let r = interval.rect; if (rectRectIntersect (r,R)) return true; } return false } }34:T970,class SquareArrangement { constructor( center = [0, 0], options = { heuristic: "first", metric: "euclidean", closeFreq: 1, closeFactor: 0.5 } ) { this.center = center; this.squares = []; this.polygon = new VList(); Object.assign(this, options); this.distance = this.metric == "chessboard" ? (p, q) => Math.max(Math.abs(p[0] - q[0]), Math.abs(p[1] - q[1])) : this.metric == "euclidean" ? (p, q) => Math.sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) : (p, q) => Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]); } closePolygon(amount) { this.polygon = topo(topo(this.polygon, amount), -amount); } addSquare(area) { let [cx, cy] = this.center; let side = Math.sqrt(area); let d = side / Math.sqrt(2); let s = undefined; let poly; if (this.squares.length == 0) { s = square([cx - d, cy - d], side); } else { let distToCenter = Number.MAX_VALUE; let smallestPerimeter; let vtx = [...this.polygon].map((v) => { v.dist = this.distance(v.p, this.center); return v; }); vtx.sort((a, b) => a.dist - b.dist); let rlist = new RectList(this.polygon); for (let v of vtx) { let [x, y] = v.p; if (v.dist > distToCenter + d) continue; // Worse than the best so far for (let [sx, sy, sign] of [ [x, y, -1], [x - side, y, +1], [x, y - side, +1], [x - side, y - side, -1] ]) { if (Math.sign(v.w) != sign) continue; // Wrong sign let candidate = square([sx, sy], side); let [scx, scy] = [sx + d, sy + d]; // Center of square if (rlist.pointIntersection([scx, scy])) continue; // Center inside polygon if (rlist.rectIntersection(candidate)) continue; // Polygon intersects square let dist = this.distance([scx, scy], [cx, cy]); if (!s || dist < distToCenter) { s = candidate; distToCenter = dist; } } if (this.heuristic == "first" && s) break; } } if (s == undefined) throw "Something went wrong : could not find a place for square"; this.squares.push(s); this.polygon = union(this.polygon, s); let factor = d * this.closeFactor; if (this.squares.length % this.closeFreq == 0) this.closePolygon(factor); } }35:[] 2e:{"title":"Square Packing","cells":[{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":929,"value":"md`## Square packing demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":681,"value":"viewof config = {\n return combo ({heuristic: select({title:\"Fit heuristic\", options:[\"first\",\"best\"],value:\"first\"}),\n metric: select({title:\"Distance metric\", \n options:[\"euclidean\", \"chessboard\",\"manhattan\"],value:\"euclidean\"}),\n renderFreq: shortSlider({title:\"Render freq.\", min:1, max:50, value:10, step:1}),\n closeFreq: shortSlider({title:\"Closing freq.\", min:1, max:100, value:1, step:1}),\n closeFactor: shortSlider({title:\"Closing amount\", min:0.1, max:1, value:0.3, step:0.1})})\n} ","pinned":false,"hidden":false,"mode":"ojs"},{"id":940,"value":"viewof dataConfig = {\n return combo ({nSquares : shortSlider({title:\"# squares\", min:10, max:500, step: 1, value:100}),\n nSizes: shortSlider({title:\"# different sizes\", min:5, max:500, step: 1, value:20}),\n distribution : select({title: \"Distribution\", options: [\"random areas\", \"random sides\"]})})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"{\n \n let ctx = DOM.context2d(400,400);\n \n // Draw the squares\n ctx.strokeStyle = 'gray'\n ctx.fillStyle = 'lightblue';\n for (let s of arrangement.squares) {\n let [x0,y0] = s[0].p, [x1,y1] = s[3].p;\n ctx.beginPath()\n ctx.moveTo(x0,y0);\n ctx.lineTo(x1,y0);\n ctx.lineTo(x1,y1);\n ctx.lineTo(x0,y1);\n ctx.closePath();\n ctx.fill();\n ctx.stroke();\n }\n \n // Draw the boundary\n ctx.strokeStyle = \"black\";\n ctx.lineWidth = 2;\n drawPolygon(ctx,arrangement.polygon)\n \n // Highlight the last square\n // ctx.strokeStyle = \"red\";\n // drawPolygon(ctx,arrangement.squares[arrangement.squares.length-1])\n \n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"squareAreas = {\n let {nSquares,distribution,nSizes} = dataConfig;\n let areas = []\n let maxArea = (400*0.9)**2 / nSquares;\n let minArea = 16;\n if (distribution == \"random areas\") {\n for (let i = 0; i < nSquares; i++) {\n areas.push (~~(Math.random()*nSizes)/nSizes*(maxArea-minArea)+minArea)\n }\n }\n else {\n let maxSide = Math.sqrt(maxArea);\n let minSide = Math.sqrt(minArea);\n for (let i = 0; i < nSquares; i++) {\n areas.push ((~~(Math.random()*nSizes)/nSizes*(maxSide-minSide)+minSide)**2)\n }\n }\n areas.sort((a,b) => b-a);\n return areas\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"arrangement = {\n let sa = new SquareArrangement([200,200],config);\n let renderFreq = config.renderFreq;\n let n = 0;\n for (let a of squareAreas) {\n sa.addSquare (a)\n n++;\n if (n % renderFreq == 0) yield sa;\n }\n if (n % renderFreq != 0) yield sa;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":729,"value":"md`## Orthogonal polygon demo\n\nYou can use a square-shaped brush to draw an orthogonal polygon. The UI below lets you draw/erase squares\nonto an orthogonal polygon and also to apply dilation/erosion morphological operations to it. The polygon is drawn in red if the brush overlaps it, or black otherwise.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":981,"value":"viewof polygonDemoUI = {\n let dilate = button({value:\"Dilate\"});\n dilate.oninput = () => {polygonDemo.dilatePolygon()};\n let erode = button({value:\"Erode\"});\n erode.oninput = () => {polygonDemo.erodePolygon()};\n let setOp = select ({title:\"Operation\", options:[\"draw\",\"erase\"]});\n setOp.onchange = () => {polygonDemo.setOperation(setOp.value)};\n let brushSize = shortSlider({title:\"Brush Size\", min:2, max:50, step:1, value:20});\n brushSize.addEventListener (\"input\", () => { polygonDemo.setBrush(brushSize.value)});\n return combo ({setOp,brushSize,dilate,erode})\n}\n\n ","pinned":false,"hidden":false,"mode":"ojs"},{"id":963,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":752,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":802,"value":"md`## Orthogonal polygons\n\nWe represent orthogonal as *Vertex Lists*, a data structure for representing orthogonal scalar fields. Orthogonal polygons are scalar fields mapping the interior to 1 and the exterior to 0.\n\nBelow we define several functions/classes that deal with orthogonal polygons.\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":64,"value":"// Returns the perimeter of an orthogonal polygon represented as vertex list vlist\nfunction perimeter (vlist) {\n let hedgesLen = (vlist) => {\n let sum = 0;\n for (let [prev,v] of vlist.faces()) {\n sum += v.p[0] - prev.p[0];\n }\n return sum\n };\n return hedgesLen(vlist) + hedgesLen(vlist.rotAxesClock())\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":67,"value":"// Returns a vertex list representing a square having length/height equal to side\n// and minimum corner (corner with smallest coordinates) at mincorner\nfunction square (minCorner = [0,0], side = 1) {\n return rectangle(minCorner,[side,side])\n} ","pinned":true,"hidden":false,"mode":"ojs"},{"id":555,"value":"// Returns a vertex list representing a rectangle having [length,height] equal to sides\n// and minimum corner (corner with smallest coordinates) at mincorner\nfunction rectangle (minCorner = [0,0], sides = [10,10]) {\n let [x,y] = minCorner;\n let [sidex,sidey] = sides;\n return new VList(\n new Vertex(+1,[x,y]),\n new Vertex(-1,[x+sidex,y]),\n new Vertex(-1,[x,y+sidey]),\n new Vertex(+1,[x+sidex,y+sidey])\n )\n} ","pinned":true,"hidden":false,"mode":"ojs"},{"id":723,"value":"// Returns true iff rectangle a intersects rectangle b\nfunction rectRectIntersect (a,b) {\n return Math.min(a[3].p[0],b[3].p[0]) > Math.max(a[0].p[0],b[0].p[0]) &&\n Math.min(a[3].p[1],b[3].p[1]) > Math.max(a[0].p[1],b[0].p[1])\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":724,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":559,"value":"// Returns the union of two orthogonal polygons represented as vertex lists\nfunction union (a,b) {\n return a.add(b).transform(w => +(w>0))\n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":561,"value":"// Returns the intersection of two orthogonal polygons represented as vertex lists\nfunction intersection (a,b) {\n return a.add(b).transform(w => +(w>1))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":976,"value":"// Returns the difference of two orthogonal polygons represented as vertex lists\nfunction difference (a,b) {\n return a.add(b.scale(-1)).transform(w => +(w>0))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":689,"value":"// Returns the minimum and maximum corner of the smallest rectangle containing all vertices of vlist\nfunction boundingBox (vlist) {\n let min = [Number.MAX_VALUE,Number.MAX_VALUE],\n max = [Number.MIN_VALUE,Number.MIN_VALUE];\n for (let v of vlist) {\n for (let i of [0,1]) {\n if (v.p[i] < min[i]) min[i] = v.p[i];\n if (v.p[i] > max[i]) max[i] = v.p[i];\n }\n }\n return {min,max}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":623,"value":"// Returns a normalized vlist, i.e., one with no 2 vertices at the same position\nfunction normalizeVList(vlist) {\n if (vlist.length < 2) return vlist;\n let result = new VList();\n let prev = vlist[0];\n for (let i = 1; i < vlist.length; i++) {\n let next = vlist[i];\n if (prev.cmp(next) == 0) {\n prev.w += next.w;\n }\n else {\n if (prev.w != 0) result.push (prev)\n prev = next;\n }\n }\n if (prev.w != 0) result.push (prev)\n return result;\n} ","pinned":true,"hidden":false,"mode":"ojs"},{"id":506,"value":"// Returns the polygon given by vlist dilated (positive d) or contracted (negative d)\nfunction topo (vlist, d) {\n if (d < 0) return erode (vlist,-d)\n else return dilate (vlist, d)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":648,"value":"// Returns the polygon given by vlist dilated by d\nfunction dilate (vlist, d) {\n let vtx = [];\n for (let r of vlist.rectangles()) {\n [[-d,-d],[d,-d],[-d,d],[d,d]].forEach(([dx,dy],i) => {\n r[i].p[0]+=dx;\n r[i].p[1]+=dy;\n vtx.push(r[i]);\n });\n }\n return normalizeVList(new VList(...vtx)).transform(w => +(w>0))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":651,"value":"function erode(vlist,d) {\n if (vlist.length < 4) return new VList();\n // Find bounding box\n let {min,max} = boundingBox(vlist);\n for (let v of vlist) {\n for (let i of [0,1]) {\n if (v.p[i] < min[i]) min[i] = v.p[i];\n if (v.p[i] > max[i]) max[i] = v.p[i];\n }\n }\n let m = 10; //margin\n let box = rectangle ([min[0]-m,min[1]-m],[max[0]-min[0]+m+m,max[1]-min[1]+m+m]);\n // subtract \n let boxMinus = new VList();\n boxMinus.push(box[0],box[1]);\n for (let v of vlist) boxMinus.push (v.scale(-1));\n boxMinus.push(box[2],box[3]);\n // dilate the result\n let result = dilate(boxMinus,d);\n // Return -hole\n return result.slice(2,result.length-2).map(v=>{v.w = -v.w; return v})\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":535,"value":"// Draws a color-coded representation of vlist onto canvas using context ctx\nfunction drawVList (ctx,vlist) {\n for (let d of vlist.rectangles()) {\n let x = d[0].p[0];\n let y = d[0].p[1];\n let w = d[1].p[0] - d[0].p[0];\n let h = d[2].p[1] - d[0].p[1];\n ctx.fillStyle = colorScale(d[0].w);\n ctx.fillRect (x,y,w,h);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":190,"value":"// Draws the boundary of vertex list vlist onto a canvas using context ctx\nfunction drawPolygon (ctx,vlist) {\n let faces = vlist.faces();\n for (let f of vlist.rotAxesClock().faces()) faces.push(f.rotAxesCounter())\n \n // Draw the polygon\n ctx.beginPath();\n for (let d of faces) {\n let x1 = d[0].p[0];\n let y1 = d[0].p[1];\n let x2 = d[1].p[0];\n let y2 = d[1].p[1];\n ctx.moveTo(x1,y1);\n ctx.lineTo(x2,y2);\n }\n ctx.stroke();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":411,"value":"\n// Converts a JSON representing a VList to a VList object\njsonToVlist = json =>\n Object.assign(new VList, JSON.parse(json).map(obj => Object.assign (new Vertex, obj)))\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"import {Vertex, VList} from \"@esperanc/vertex-lists\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":533,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":531,"value":"colorScale = d3.scaleOrdinal(d3.schemeCategory10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":840,"value":"createIntervalTree = require('https://bundle.run/interval-tree-1d@1.0.3')","pinned":true,"hidden":false,"mode":"ojs"},{"id":919,"value":"import {tabbed,paged,combo} from \"@esperanc/aggregated-inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":921,"value":"import {select,button,slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":942,"value":"// Used to style one of Jeff Ashkenas input components\nfunction styleInput(form,style) {\n let input = form.querySelector(\"input\");\n for (let s in style) {\n input.style[s] = style[s];\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":944,"value":"// Makes a slider with 80px width\nfunction shortSlider (...args) {\n let s = slider(...args);\n styleInput(s,{width:\"80px\"});\n return s;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}