29:null 2a:["$","title",null,{"children":"QuickHull algorithm for the Convex Hull | Laurens Debackere | Observable"}] 2f:T46d,vl.layer( vl.markLine() .data(dataset.filter(v => v.x == min_x.x || v.x == max_x.x)) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('darkgray') ), vl.markPoint() .data(dataset) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('lightgray') ), vl.markPoint() .data(sets[side]) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('gray') ), vl.markPoint() .data([furthest]) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('orange') ), vl.markPoint() .data(sets[side].filter(v => determine_side(furthest, v2, v) == -1)) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value(side == 0 ?'blue':'red') ), vl.markPoint() .data(sets[side].filter(v => determine_side(furthest, v1, v) == 1)) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value(side == 0 ?'blue':'red') ), vl.markLine() .data([v1, furthest]) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('green') ), vl.markLine() .data([v2, furthest]) .encode( vl.x().fieldQ('x'), vl.y().fieldQ('y'), vl.color().value('green') ), ).render()30:[] 2d:{"id":"22f6dd811786a176","slug":"quickhull-algorithm-for-the-convex-hull","title":"QuickHull algorithm for the Convex Hull","thumbnail":"ea550dbb845b238b63923e38f3a6c0a9e93d3bb3e54867db54150ab6379c319d","access_level":"public","create_time":"$D2021-04-20T11:19:47.989Z","update_time":"$D2021-04-25T12:48:59.120Z","view_time":null,"first_public_time":"$D2021-04-22T08:51:44.092Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"d6b18c54f51ce9e2","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":"starter_2024"},"version":517,"publish_version":517,"role":null,"authored":false,"authors":[{"type":"individual","id":"8a9aa62b2bb093d9","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":null}],"members":[{"type":"individual","id":"8a9aa62b2bb093d9","login":"laurensdeb","name":"Laurens Debackere","avatar_url":"https://avatars-next.observableusercontent.com/7d15871f6e8319cd1c1a86deb6bb62ad15086e9cff56c7f9acceeaec0d900285","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"QuickHull algorithm for the Convex Hull","cells":[{"id":0,"value":"md`## Discrete Algorithms (2020-2021)\n# QuickHull algorithm for the Convex Hull\nThis notebook illustrates the workings of the [QuickHull algorithm](https://en.wikipedia.org/wiki/Quickhull) for determining the Convex Hull of a given dataset. We'll first start of by generating a random set of ${tex`N = ${N}`} points to illustrate the algoritm on.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"N = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"dataset = {\n let points = []\n let base = [Math.random()*50.0, Math.random()*50.0]\n let scale = [50 + Math.random()*100.0, 50 + Math.random()*100.0]\n for (let i = 0; i < N; i++){\n points.push({x: Math.random()*scale[0] + base[0], y: Math.random()*scale[1] + base[1]}) \n }\n return points\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"md`## Step 1: Searching for the leftmost and rightmost points along the X-axes\nThe first step in the initialization of the QuickHull algorithm is looking for the points with smallest and largest x-coordinate. In our case these are respectively **(${min_x.x.toPrecision(2)}, ${min_x.y.toPrecision(2)})** and **(${max_x.x.toPrecision(2)}, ${max_x.y.toPrecision(2)})**). **These points will have to be part of our convex hull.**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"min_x = dataset.reduce((acc, curr) => acc?(acc.x < curr.x?acc:curr):curr, {})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"max_x = dataset.reduce((acc, curr) => acc?(acc.x > curr.x?acc:curr):curr, {})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"md`*Next*, we'll split the dataset in a part to the left of an imaginary axes between these two points and a part to the right. We'll be performing our algorithm *recursively* on these two parts of the dataset.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"vl.layer(\nvl.markLine()\n.data(dataset.filter(v => v.x == min_x.x || v.x == max_x.x))\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('green')\n ),\n vl.markPoint()\n.data(leftSet)\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('blue')\n ),\n vl.markPoint()\n.data(rightSet)\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('red')\n ),\n vl.markPoint()\n.data(hull_step_1)\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('black')\n )\n ).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"hull_step_1 = new Set([min_x, max_x])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"leftSet = dataset.filter(v => determine_side(min_x, max_x, v) == -1);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"rightSet = dataset.filter(v => determine_side(min_x, max_x, v) == 1);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"sets = [leftSet, rightSet]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"md`## Step 2: Recursion\nNow that our dataset is split in two parts we'll highlight the **core idea** behind the recursive step of our algorithm. Through the toggle below you can respectively see the working of the algorithm for the left or right part of our dataset (in the first recursive step).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"viewof side = Select([0, 1], {sort: true, unique: true, format: x => x==0?\"Left\":\"Right\", label: \"Side\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":333,"value":"v1 = side == 0 ? min_x : max_x","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"v2 = side == 0 ? max_x : min_x","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"md`In our dataset we'll be looking for the furthest point from this imaginary axes (the one we've used in the previous step to split the dataset). **This point will most definitely be part of the convex hull.** And we'll be using it to recusively split the dataset again. As to determine the furthest point we'll be using the formula for the distance between a point and a line as shown below.\n\n${tex`\\mathbb dist(v_1, v_2, v) = (v.y - v_1.y) . (v_2.x - v_1.x) - (v_2.y - v_1.y) . (v.x - v_1.x)`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":341,"value":"furthest = sets[side].reduce((acc, curr) => distance(v1, v2, acc) > distance(v1, v2, curr)?acc:curr)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":486,"value":"md`Visually this looks something like this if we indicate the furthest point using an orange outline.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"vl.layer(\n vl.markPoint()\n.data(dataset)\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('gray')\n ),\nvl.markLine()\n.data(dataset.filter(v => v.x == min_x.x || v.x == max_x.x))\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('green')\n ),\n vl.markPoint()\n.data(sets[side])\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value(side == 0 ?'blue':'red')\n ),\n vl.markPoint()\n.data([furthest])\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('orange'),\nvl.size().value(100)\n ),\n ).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"value":"md`So, how do we use this new point to split our dataset again? Well, if we connect this new point to the edge points of our previous axes we notice a triangle, the part of our dataset within the triangle will most definitely not be on the convex hull so we'll consider the parts to the left and right, highlighted in the figure.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":396,"value":"md`Below we'll be showing the step by step results of a full recursion. Use the slider to go through all of the steps to see new points being added to the hull.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":407,"value":"viewof step = Scrubber(Array.from(result).reduce((acc, curr) => acc.add(curr.step), new Set()), {delay: 1000, loopDelay: 10000})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":382,"value":"vl.layer(\nvl.markPoint()\n.data(dataset)\n.encode(\nvl.x().fieldQ('x'),\nvl.y().fieldQ('y'),\nvl.color().value('gray')\n),\n vl.markPoint()\n.data(Array.from(result).filter(v => v.step <= step))\n.encode(\nvl.x({title: 'x'}).fieldQ('point.x'),\nvl.y({title: 'y'}).fieldQ('point.y'),\nvl.color().value('green'),\nvl.size().value(100)\n)\n ).render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"d = (v1, v2, v) => (v.y - v1.y) * (v2.x - v1.x) - (v2.y - v1.y) * (v.x - v1.x)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"distance = (v1, v2, v) => Math.abs((v.y - v1.y) * (v2.x - v1.x) - (v2.y - v1.y) * (v.x - v1.x))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"determine_side = (v1, v2, v) => Math.sign(d(v1, v2, v))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":228,"value":"function quickhull (points) {\n let hull = new Set();\n \n let leftmost = points.reduce((acc, curr) => acc.x < curr.x?acc:curr, points[0]);\n let rightmost = points.reduce((acc, curr) => acc.x > curr.x?acc:curr, points[0]);\n \n let leftSet = points.filter(v => determine_side(min_x, max_x, v) == -1);\n let rightSet = points.filter(v => determine_side(min_x, max_x, v) == 1);\n \n hull.add({point: leftmost, step: 1});\n hull.add({point: rightmost, step: 1});\n let step_l = quickhull_r(leftSet,leftmost, rightmost, hull, 2);\n quickhull_r(rightSet, rightmost, leftmost, hull, step_l);\n return hull;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"result = quickhull(dataset)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"function quickhull_r (points, v1, v2, hull, step) {\n if (points.length == 0)\n return step;\n if (points.length == 1)\n {\n hull.add({point: points[0], step: step});\n return step + 1;\n }\n\n let furthest = points.reduce((acc, curr) => distance(v1, v2, acc) > distance(v1, v2, curr)?acc:curr)\n \n hull.add({point: furthest, step: step});\n step += 1;\n \n let leftSet = points.filter(v => determine_side(furthest, v1, v) == 1);\n let rightSet = points.filter(v => determine_side(furthest, v2, v) == -1);\n\n let step_l = quickhull_r(leftSet, v1, furthest, hull, step);\n return quickhull_r(rightSet, furthest, v2, hull, step_l);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"import {Select} from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"import { vl } from \"@vega/vega-lite-api\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":404,"value":"import {Scrubber} from \"@mbostock/scrubber\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"color_scale = Object({domain: ['darkgray', 'lightgray', 'green', 'orange', 'black', 'red', 'blue'], range: ['darkgray', 'lightgray', 'green', 'orange', 'black', 'red', 'blue']})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"