30:Ta83,md` ----- # Algorithm There is actually a pretty nice way to computate the convex hull that has a asymptotic runtime of ${tex`O(n\space log\space n)`} called Graham scan. Which I will try to explain. ## pre thoughts ### x-coordinate The point that has the smallest x-coordinate is **always** part of the convex hull. That is, because all points with bigger x-coordinate can never be more to the left than the point with the smallest x-coordinate. ${smallest()} ### convex What does it mean for a polygon to be convex? You may ask (i certainly did). This is _definitly_ **not** the mathematical definition. A polygon can be imagined as a path from one point to another. Like every path it can have a direction. In plane geometry there is only left, right and on the same line. If the point is on the same line (colinear), we dont care about the point for now. So there is only left and right. As we already now that the point with the smallest x-coordinate is on the convex hull it makes sense to start from "left". Now we can find out that the polygon through some points is convex, if it never changes the direction of the path. ${direction()} ### calculate direction For humans it is actually really simple to decide in which direction a connected path of three arrows is pointing. To make it comparable simple for a computer we have to use the determinante of a 3x3 Matrix, where ${tex`(x1,y1)`} = point1, ${tex`(x2,y2)`} = point2 and ${tex`(x3,y3)`} = point3 ${tex`\begin{vmatrix} 1 & x1 & y1 \\ 1 & x2 & y2 \\ 1 & x3 & y3 \end{vmatrix} = \begin{vmatrix} 1 & x1 & y1 \\ 0 & x2 - x1 & y2 - y1 \\ 0 & x3 - x1 & y3 -y3 \end{vmatrix} = \begin{vmatrix} x2 - x1 & y2 - y1 \\ x3 - x1 & y3 - y1 \end{vmatrix} = (x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)`} This gives us: ${tex`\begin{cases} <0 &\text{if path goes left}\\ \quad0&\text{if path is straight} \\ >0&\text{if path goes right} \end{cases}`} (Ref: https://de.wikipedia.org/wiki/Graham_Scan) So to recap, if the value of det3 is smaller or equal to zero the path that goes through the input points does not go in the right direction. Unfortunatly the polygon somewhere turns around. To handle this, we first compute the "upper hull" and later go from the last point to the first and compute the "lower hull" ## Pseudocode 1. First we start by sorting all points depending on their x-coordinate. 2. Create a list "upper" and append first and second of the sorted points. 3. While the list has more than 2 elements and the path does not make a right turn: - remove the middle point from the list 4. add the current point to the list. 5. do the same but reverse the List first 6. concat upper and lower (remove duplicates)`31:[] 2e:{"title":"convex hull","cells":[{"id":0,"value":"md`# convex hull\n\nA convex hull is the smallest polygon around a set of points, that includes all the points. It is a well studied algorithm in computational geometry. And i read about in the first chapter of this book (https://www.springer.com/de/book/9783540779735). \nI also stole some inspiration from here: https://github.com/AndriiHeonia/hull\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":516,"value":"md`#### (feel free to click on the canvas)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"{\n const context = DOM.context2d(width, width);\n const pts = [];\n for (let i = 0; i < n; ++i) {\n const pt = [\n offset / 2 + Math.floor(Math.random() * (width - offset)),\n offset / 2 + Math.floor(Math.random() * (width - offset))\n ];\n pts.push(pt);\n }\n\n function drawPoints(pts) {\n pts.forEach(p => circle([...p, 2], context));\n }\n\n drawPoints(pts);\n let hull = convexHull2D(pts);\n drawHull(hull, context);\n\n const can = context.canvas;\n can.addEventListener(\"click\", ({ layerX, layerY }) => {\n context.clearRect(0, 0, width, width);\n pts.push([layerX, layerY]);\n drawPoints(pts);\n hull = convexHull2D(pts);\n drawHull(hull, context);\n });\n return can;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":464,"value":"viewof n = slider({\n title: \"n\",\n min: 2,\n max: 1000,\n step: 1,\n value: 150\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":483,"value":"viewof offset = slider({\n title: \"offset\",\n min: 2,\n max: 600,\n step: 1,\n value: 350\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":521,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":533,"value":"function smallest() {\n const context = DOM.context2d(width / 2, width / 2);\n const offset = 200;\n const pts = [];\n for (let i = 0; i < 20; ++i) {\n const p = [\n offset / 2 + Math.floor(Math.random() * (width / 2 - offset)),\n offset / 2 + Math.floor(Math.random() * (width / 2 - offset))\n ];\n pts.push(p);\n circle([...p, 2], context);\n }\n const smallest = pts.reduce((acc, cur) => {\n if (acc.length === 0) return cur;\n return cur[0] < acc[0] ? cur : acc;\n });\n circle([...smallest, 5], context, { color: \"red\" });\n context.font = \"16px sans-serif\";\n context.fillStyle = \"black\";\n context.fillText(\n \"always on the convex hull\",\n smallest[0] - 10,\n smallest[1] + 25\n );\n\n const hull = convexHull2D(pts);\n\n for (let i = 1; i < hull.length; ++i) {\n line(hull[i], hull[i - 1], context, {\n dash: [5, 10],\n color: \"rgba(0,0,0,0.5)\"\n });\n }\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":591,"value":"function direction() {\n const context = DOM.context2d(width / 2, width / 2);\n const offset = 200;\n const pts = [[100, 300], [150, 250], [290, 190], [420, 220]];\n pts.forEach((p, i) => circle([...p, 2], context));\n for (let i = 0; i < pts.length - 1; ++i) {\n const d = getAlphaBetweenPoints(pts[i], pts[i + 1]);\n arrow(pts[i], pts[i + 1], context);\n lineThrough(pts[i], d, context, {\n dash: [5, 10],\n color: \"rgba(0,0,0,0.5)\"\n });\n }\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"function convexHull2D(p) {\n const p_ = p.slice();\n const sorted = p_.sort((a, b) => sortByX(a, b));\n const upper = upperHull(sorted);\n const lower = lowerHull(sorted);\n return [...upper, ...lower];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":290,"value":"function upperHull(p) {\n const n = p.length;\n const u = [];\n for (let i = 0; i < n; ++i) {\n while (u.length >= 2 && det3(u[u.length - 2], u[u.length - 1], p[i]) <= 0) {\n u.pop();\n }\n u.push(p[i]);\n }\n return u;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":303,"value":"function lowerHull(p) {\n const n = p.length;\n const b = p.slice().reverse();\n const l = [];\n for (let i = 0; i < b.length; ++i) {\n while (l.length >= 2 && det3(l[l.length - 2], l[l.length - 1], b[i]) <= 0) {\n l.pop();\n }\n l.push(b[i]);\n }\n l.shift();\n return l;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":753,"value":"function drawHull(hull, context) {\n const hl = hull.length;\n hull.forEach((p, i) => line(p, hull[(i + 1) % hl], context));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":441,"value":"function sortByX(a, b) {\n if (a[0] < b[0]) return -1;\n if (a[0] === b[0]) {\n if (a[1] < b[1]) return -1;\n }\n return 1;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"function det3([x1, y1], [x2, y2], [x3, y3]) {\n return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":624,"value":"function arrow([fromx, fromy], [tox, toy], context) {\n var headlen = 10; // length of head in pixels\n var angle = Math.atan2(toy - fromy, tox - fromx);\n context.beginPath();\n context.moveTo(fromx, fromy);\n context.lineTo(tox, toy);\n context.lineTo(\n tox - headlen * Math.cos(angle - Math.PI / 6),\n toy - headlen * Math.sin(angle - Math.PI / 6)\n );\n context.moveTo(tox, toy);\n context.lineTo(\n tox - headlen * Math.cos(angle + Math.PI / 6),\n toy - headlen * Math.sin(angle + Math.PI / 6)\n );\n context.strokeStyle = \"black\";\n context.setLineDash([0, 0]);\n context.stroke();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"import {\n circle,\n getAlphaBetweenPoints,\n line,\n lineThrough,\n} from '@timhau/geometry'","pinned":false,"hidden":false,"mode":"ojs"},{"id":466,"value":"import { slider } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}