2c:null 2d:["$","title",null,{"children":"Vertex Lists | Claudio Esperança | Observable"}] 32:T818,/** * Vertex as in the ´Vertex List´ paper of Esperanca and Samet, 1998 **/ class Vertex { // A vertex with weight w and coordinates p[0],p[1],etc constructor (w, p=[]) { this.w = w; this.p = p.slice() } // A deep copy of this Vertex clone() { return new Vertex(this.w, this.p) } // The dimension of this vertex get dim () { return this.p.length } // Rotates the axes for this vertex coordinates (in place). rotAxesClock () { this.p.unshift(this.p.pop()); return this } // Undoes rotAxesClock rotAxesCounter () { this.p.push(this.p.shift()); return this } // The last coordinate of this vertex get lastCoord () { return this.p[this.p.length-1] } // Comparison function for establishing ordering between vertices. // Returns -1,0 or 0 according to whether this vertex precedes, is equal, or // follows vertex other in scanline order. cmp (other) { if (!(this.dim ==other.dim)) { console.assert (this.dim ==other.dim); } for (let i = this.p.length-1; i >= 0; i--) { if (this.p[i] < other.p[i]) return -1; if (this.p[i] > other.p[i]) return +1; } return 0; } // Returns a new vertex with weight equal to w*scalar scale(scalar) { console.assert(scalar!=0) return new Vertex(this.w*scalar,this.p) } // Returns a new vertex with one dimension less project() { return new Vertex(this.w,this.p.slice(0,this.p.length-1)) } // Returns a new vertex with one extra dimension, having h as the additional coordinate unproject(h) { return new Vertex(this.w,this.p.concat([h])) } // Returns true if point q is in the cone of this vertex dominates(q) { for (let i = 0; i < this.p.length; i++) { if (q[i] < this.p[i]) return false } return true } // Translates this vertex (in place) by vector u translate (u) { for (let i = 0; i < this.p.length; i++) { this.p[i] += u[i] } return this } repr () { return "("+this.w+",["+this.p+"])"; } }33:T1556,/** * A Vertex List - data structure to represent multidimensional orthogonal fields **/ class VList extends Array { // Constructor from an array of vertices constructor (...l) { super(...l); this.sort((a,b) => a.cmp(b)) } clone () { let clone = new VList(); for (let v of this) clone.push(v.clone()) return clone } // Returns a new VList with clockwise rotated vertices rotAxesClock () {; let clone = []; for (let v of this) clone.push(v.clone().rotAxesClock()); return new VList (...clone) } // Returns a new VList with counterclockwise rotated vertices rotAxesCounter () { let clone = []; for (let v of this) clone.push(v.clone().rotAxesCounter()); return new VList (...clone) } // A string representation of a VList repr () { let s = "{"; for (let x of this) s+=x.repr(); return s+"}" } // Returns the length of the prefix" prefixLen() { if (this.length == 0) return 0; let c = this[0].lastCoord; let n = 0; for (let v of this) { if (v.lastCoord != c) return n; n++; } return n; } // Returns a VList containing all vertices from the beginning of the list // with the same last coordinate prefix() { let plen = this.prefixLen(); return this.slice(0,plen); } // Returns this VList with its prefix removed remainder() { let plen = this.prefixLen(); return this.slice(plen); } // Combines prefix and remainder in a single operation split () { let plen = this.prefixLen(); return [this.slice(0,plen), this.slice(plen)] } // Returns this VList with one dimension less project() { let r = new VList(); for (let x of this) r.push(x.project()); return r; } // Returns this VList with one extra dimension, having h as the additional coordinate unproject(h) { let r = new VList(); for (let x of this) r.push(x.unproject(h)); return r; } // Returns the sum of this and other add(other) { console.assert (other instanceof VList); let r = new VList(); let i = 0, j = 0; while (i 0) r.push(other[j++]) else { let v = new Vertex(this[i].w+other[j].w,this[i].p) if (v.w != 0) r.push(v); i++; j++; } } while (i 0) { [pref,rem] = rem.split(); let coord = pref[0].lastCoord; let proj = pref.project(); o = o.add (proj); let transf = o.transform(f); let delta = transf.add(t.scale(-1)); for (let x of delta.unproject(coord)) r.push(x); t = transf; } return r } // Returns the decomposition of this list as a list of vlists, each one corresponding to // a single (hyper-)rectanble rectangles () { let r = []; if (this.length == 0) return r; console.assert(this[0].dim > 0); if (this[0].dim == 1) { let prevw = 0, prevx = Number.MINUS_INFINITY; for (let v of this) { if (prevw != 0) { r.push (new VList(new Vertex (prevw, [prevx]), new Vertex (-prevw, [v.p[0]]))); } prevw += v.w; prevx = v.p[0]; } } else { let rem = new VList(...this), pref = new VList(); let prevpref = new VList(), prevcoord; while (rem.length > 0) { [pref,rem] = rem.split(); let coord = pref[0].lastCoord; let s = prevpref.project(); for (let face of s.rectangles()) { let rect = face.unproject(prevcoord); for (let v of face) { let q = v.unproject(coord); q.w = -q.w; rect.push (q); } r.push (rect); } prevcoord = coord; prevpref = s.unproject(coord).add(pref); } } return r } // Returns the horizontal (scanline) faces of this field faces () { let r = []; if (this.length == 0) return r; console.assert(this[0].dim > 1); let rem = new VList(...this), pref = new VList(); while (rem.length > 0) { [pref,rem] = rem.split(); let coord = pref[0].lastCoord; for (let rect of pref.project().rectangles()) r.push(rect.unproject(coord)); } return r; } // Translates all vertices in list by vector u (in place) translate (u) { for (let v of this) v.translate(u); return this } } 34:[] 30:{"id":"bb011393da379978","slug":"vertex-lists","title":"Vertex Lists","thumbnail":"0971e4d507d64f18262a891ce0e492d77be09c0d0abd6a713969746ca3b61942","access_level":"public","create_time":"$D2018-11-11T15:55:43.686Z","update_time":"$D2018-11-20T22:23:19.698Z","view_time":null,"first_public_time":"$D2018-11-19T22:07:56.639Z","fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":395,"publish_version":395,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"6e2e99f12b8c9dbb","slug":"paper-implementations","title":"Paper implementations","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"title":"Vertex Lists","cells":[{"id":0,"value":"md`# Vertex Lists\n\nA crude implementation of [Vertex Lists (Esperança and Samet 1998)](http://www.cs.umd.edu/~hjs/pubs/esperancaVC98.pdf)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":327,"value":"md`## Main data structures`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":337,"value":"md`## Convenience functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":22,"value":"// A helper function to construct a vertex given its weight and coordinates\nvtx = function (w, ...p) {\n return new Vertex(w,p)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":118,"value":"// 2D Vertex list for a rectangle given two corner points\nvrect = function (x0,y0,x1,y1) {\n if (x0 > x1) [x0,x1] = [x1,x0];\n if (y0 > y1) [y0,y1] = [y1,y0];\n return new VList (vtx(1,x0,y0),vtx(-1,x1,y0),vtx(-1,x0,y1),vtx(1,x1,y1))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":344,"value":"md`## Examples`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":227,"value":"height = ~~(width * 3/4)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":261,"value":"example = {\n let l = vrect(100,100,200,200)\n .add(vrect(150,150,250,250))\n .add(vrect(50,50,300,300))\n .add(vrect(125,125,225,225));\n let l2 = l.clone().translate([400,0]).transform(d=>d>1?d:0)\n let l3 = l.clone().translate([0,300]).transform(d=>d<=2?d:0)\n let l4 = l.clone().translate([400,300]).transform(d=>d>0?4-d:0)\n return l.add(l2).add(l3).add(l4)\n}\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":229,"value":"rects = example.rectangles()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":265,"value":"faces = {\n let faces = example.faces();\n for (let f of example.rotAxesClock().faces()) faces.push(f.rotAxesCounter())\n return faces;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":386,"value":"md`## SVG rendering of the field`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":237,"value":"svg = DOM.svg(width,height)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":248,"value":"colorScale = d3.scaleOrdinal(d3.schemeCategory10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":231,"value":"plotRects = {\n let plotArea = d3.select(svg);\n plotArea.selectAll(\"rect,line\").remove()\n let join = plotArea.selectAll(\"rect\").data(rects);\n join.exit().remove();\n join.enter().append(\"rect\").merge(join)\n .attr(\"x\", d => d[0].p[0])\n .attr(\"y\", d => d[0].p[1])\n .attr(\"width\", d => d[1].p[0] - d[0].p[0])\n .attr(\"height\", d => d[2].p[1] - d[0].p[1])\n .attr(\"fill\", d=> colorScale(d[0].w))\n ;\n \n join = plotArea.selectAll(\"line\").data(faces);\n join.exit().remove();\n join.enter().append(\"line\").merge(join)\n .attr(\"x1\", d => d[0].p[0])\n .attr(\"y1\", d => d[0].p[1])\n .attr(\"x2\", d => d[1].p[0])\n .attr(\"y2\", d => d[1].p[1])\n .attr(\"stroke\", \"black\")\n .attr(\"stroke-width\", 2)\n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":389,"value":"md`## Canvas rendering of the field`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":377,"value":"canvas = {\n let ctx = DOM.context2d(width,height);\n \n for (let d of rects) {\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 \n ctx.strokeStyle = \"black\";\n ctx.lineWidth = 2;\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 \n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":368,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":233,"value":"d3 = require (\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 31:"$30:body"