2d:null 2e:["$","title",null,{"children":"Hilbert Curve Packing | Volodymyr Agafonkin | Observable"}] 33:[] 31:{"id":"5110bb8ed6b97d74","slug":"hilbert-curve-packing","title":"Hilbert Curve Packing","thumbnail":"b0705cfa30a40bef43906d9f8a8927a78a537324867588489224024533687361","access_level":"public","create_time":"$D2018-02-23T16:35:28.478Z","update_time":"$D2018-03-23T07:32:38.697Z","view_time":null,"first_public_time":"$D2018-02-23T17:12:08.810Z","has_unpublished_edits":null,"fork":false,"stars":22,"starred":false,"owner":{"type":"team","id":"78f29d059906819a","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":"starter_2024"},"version":219,"publish_version":219,"role":null,"authored":false,"authors":[{"type":"individual","id":"3954cddf6608132f","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":null}],"members":[{"type":"individual","id":"3954cddf6608132f","login":"mourner","name":"Volodymyr Agafonkin","avatar_url":"https://avatars-next.observableusercontent.com/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":12,"collection":{"id":"05c3a5b5466d0c69","slug":"explorables","title":"Explorables","owner":{"id":"78f29d059906819a","login":"mourner","name":"Volodymyr Agafonkin"}},"type":"notebook","body":{"title":"Hilbert Curve Packing","cells":[{"id":0,"value":"md`\n# Hilbert Curve Packing\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md`Let's generate ${numPoints} random 2D points over the ${width}x${height} space and sort them by their Hilbert curve value:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"points = {\n const points = [];\n\n for (let i = 0; i < numPoints; i++) {\n const x = 1 + Math.floor(Math.random() * (width - 2));\n const y = 1 + Math.floor(Math.random() * (height - 2)); \n const h = hilbert(x, y);\n \n points.push([x, y, h]);\n }\n \n return points.sort((a, b) => a[2] - b[2]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":181,"value":"viewof nodeSize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"md`Now let's draw a rectangle over each block of consecutive ${nodeSize} points:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"{\n const ctx = DOM.context2d(width, height);\n ctx.beginPath();\n for (const p of points) {\n ctx.rect(p[0] - 1, p[1] - 1, 2, 2);\n }\n ctx.fillStyle = 'black';\n ctx.fill();\n \n ctx.strokeStyle = 'red';\n ctx.lineWidth = 1;\n ctx.fillStyle = 'rgba(255,255,0,0.1)';\n \n mutable hilbertOverhead = -1;\n\n for (let i = 0; i < points.length; i += nodeSize) {\n\tlet minX = Infinity;\n let minY = Infinity;\n let maxX = -Infinity;\n let maxY = -Infinity;\n for (let j = 0; j < nodeSize; j++) {\n if (i + j === points.length) break;\n const p = points[i + j];\n if (p[0] < minX) minX = p[0];\n if (p[1] < minY) minY = p[1];\n if (p[0] > maxX) maxX = p[0];\n if (p[1] > maxY) maxY = p[1];\n }\n const boxWidth = maxX - minX;\n const boxHeight = maxY - minY;\n ctx.fillRect(minX, minY, boxWidth, boxHeight);\n ctx.strokeRect(minX, minY, boxWidth, boxHeight);\n \n mutable hilbertOverhead += boxWidth * boxHeight / (width * height);\n }\n \n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"md`\nNotice how the rectangles don't overlap too much (in this case, ${Math.round(100 * hilbertOverhead)}% overhead) — points with similar Hilbert values stay relatively close to each other. This makes Hilbert curves very useful for indexing spatial data. \n\nFor example, we can take advantage of this to build an efficiently packed R-tree from these points. This is the core idea that allowed me to build [the fastest static 2D spatial index library in JavaScript called Flatbush](https://github.com/mourner/flatbush).\n\nLet's connect all points with a line to see how they are ordered:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"{\n const ctx = DOM.context2d(width, height);\n ctx.beginPath();\n ctx.strokeStyle = 'green';\n ctx.lineWidth = 1;\n ctx.moveTo(points[0][0], points[0][1]);\n for (let i = 1; i < points.length - 1; i++) {\n ctx.lineTo(points[i][0], points[i][1]);\n }\n ctx.stroke();\n\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"md`\nNow let's compare this to another popular type of space-filling curve — the Z-order (Morton) curve. We'll order the same points using z-order values and draw rectangles the same way:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"pointsZ = points\n .map((p) => [p[0], p[1], zOrder(p[0], p[1])])\n .sort((a, b) => a[2] - b[2])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"{ \n const ctx = DOM.context2d(width, height);\n ctx.beginPath();\n for (const p of pointsZ) {\n ctx.rect(p[0] - 1, p[1] - 1, 2, 2);\n }\n ctx.fillStyle = 'black';\n ctx.fill();\n\n ctx.strokeStyle = 'red';\n ctx.lineWidth = 1;\n ctx.fillStyle = 'rgba(255,255,0,0.1)';\n \n mutable zOverhead = -1;\n\n for (let i = 0; i < pointsZ.length; i += nodeSize) {\n\tlet minX = Infinity;\n let minY = Infinity;\n let maxX = -Infinity;\n let maxY = -Infinity;\n for (let j = 0; j < nodeSize; j++) {\n if (i + j === pointsZ.length) break;\n const p = pointsZ[i + j];\n if (p[0] < minX) minX = p[0];\n if (p[1] < minY) minY = p[1];\n if (p[0] > maxX) maxX = p[0];\n if (p[1] > maxY) maxY = p[1];\n }\n const boxWidth = maxX - minX;\n const boxHeight = maxY - minY;\n ctx.fillRect(minX, minY, boxWidth, boxHeight);\n ctx.strokeRect(minX, minY, boxWidth, boxHeight);\n \n mutable zOverhead += boxWidth * boxHeight / (width * height);\n }\n \n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"md`\nNotice how much more overlap the Z-order based rectangles have — ${Math.round(100 * zOverhead)}% to be exact, which will make queries much less efficient than a Hilbert-based index.\n\nHere's how a line connected through the points looks now:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"{\n const ctx = DOM.context2d(width, height);\n ctx.beginPath();\n ctx.strokeStyle = 'green';\n ctx.lineWidth = 1;\n ctx.moveTo(pointsZ[0][0], pointsZ[0][1]);\n for (let i = 1; i < pointsZ.length - 1; i++) {\n ctx.lineTo(pointsZ[i][0], pointsZ[i][1]);\n }\n ctx.stroke();\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"numPoints = 2000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"width = 800","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"mutable hilbertOverhead = -1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"mutable zOverhead = -1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"curveSize = Math.pow(2, Math.ceil(Math.log2(Math.max(width, height))))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"hilbert = (x, y) => {\n // map coordinates to Hilbert coordinate space\n x = Math.floor(x * curveSize / width);\n y = Math.floor(y * curveSize / height);\n\n var d = 0;\n for (var s = curveSize >> 1; s > 0; s >>= 1) {\n var rx = +((x & s) > 0);\n var ry = +((y & s) > 0);\n d += s * s * ((3 * rx) ^ ry);\n\n if (ry === 0) {\n if (rx === 1) {\n x = s - 1 - x;\n y = s - 1 - y;\n }\n var t = x;\n x = y;\n y = t;\n }\n }\n return d;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"zOrder = (x, y) => {\n // map coordinates to Z-order curve coordinate space\n x = Math.floor(x * curveSize / width);\n y = Math.floor(y * curveSize / height);\n \n x = (x | (x << 8)) & 0x00FF00FF;\n x = (x | (x << 4)) & 0x0F0F0F0F;\n x = (x | (x << 2)) & 0x33333333;\n x = (x | (x << 1)) & 0x55555555;\n\n y = (y | (y << 8)) & 0x00FF00FF;\n y = (y | (y << 4)) & 0x0F0F0F0F;\n y = (y | (y << 2)) & 0x33333333;\n y = (y | (y << 1)) & 0x55555555;\n\n return x | (y << 1);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 32:"$31:body"