25:["$","title",null,{"children":"Convex hull | Tom MacWright | Observable"}] 4c:T40c,# Convex hull My side project is related to some lightweight computational geometry and I'm trying not to use any libraries for ignorance - I want to be able to implement every algorithm under the hood and actually understand it. I've used convex hull libraries a lot in the past but never implemented it from scratch. It's a pleasingly nice algorithm: pretty intuitive once you get the [basic overview](https://en.wikipedia.org/wiki/Convex_hull), but the use of a cross product was new to me. I haven't really used cross products and don't have much intuition for how they work. My understanding of how they're used in this case is that they're essentially used to understand whether a line turns left or right: to get more into it, I'm tinkering with cross products in this notebook as well, below the convex hull demo. This is specifically [Andrew's monotone chain](https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain) algorithm. _You can double-click on the demo area to add another point_4d:T6ee,const width = 928; const height = 600; const svg = d3.create("svg") .attr("width", width) .attr("height", height) .attr("viewBox", [0, 0, width, height]) .attr("style", "max-width: 100%; height: auto; background: #dff;border:1px solid #0cc;"); let id = 0; const circles: Circle[] = [ {x: 180, y: 250, r: 10, id: id++}, {x: 400, y: 100, r: 10, id: id++}, {x: 400, y: 300, r: 10, id: id++} ]; const ring = svg.append("g").attr("class", "ring"); ring.append("path").attr("class", "ring-outer"); const gCircles = svg.append("g"); function update() { gCircles.selectAll(".circle") .data(circles, d => d.id) .join(enter => enter.append("g") .attr("class", "circle") .call(g => g.append("circle").attr("r", d => d.r)) .call(d3.drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended))) .attr("transform", ({x, y}) => `translate(${x},${y})`); const hull = convexHull(circles); if (!hull) { ring.attr("hidden", true); } else { ring.attr("hidden", null); const ctx = d3.path(); ctx.moveTo(hull[0].x, hull[0].y); for (const {x, y} of hull.slice(1)) ctx.lineTo(x, y); ctx.closePath(); ring.select(".ring-outer").attr("d", ctx.toString()); } } svg.on("dblclick", e => { e.preventDefault(); const [x, y] = d3.pointer(e, svg.node()); circles.push({x, y, r: 10, id: id++}); update(); }); function dragstarted(event) { d3.select(event.sourceEvent.target.closest(".circle")).raise(); svg.style("overflow", "visible"); } function dragged(event, d) { d.x = clamp(event.x, d.r, width - d.r); d.y = clamp(event.y, d.r, height - d.r); update(); } function dragended() { svg.style("overflow", null); } update(); display(svg.node());4e:T49c,## Cross product I didn't want to skim over the cross product in this algorithm because I didn't really understand what it was doing. It's pretty useful! The convex hull algorithm is trying to find an 'upper hull' and a 'lower hull' and the algorithm is throwing away points that are inside the hull. So, given three points, we want to know if the line has made a left or right turn, because for example, on the upper hull, if we just made a left turn, the middle point should be discarded because it's inside the hull. The cross product does this with arithmetic only, no trigonometry at all, which makes it super useful and fast. If I faced the same problem, I'd probably do `Math.atan2` of the angle before & after, but that's more complicated and slower. Also, it's interesting that he specific magnitude of the cross-product is the area of the positive parallelogram formed by the two edges, but many of the applications including this one only care about the sign of the value, to test whether we're looking at a left, right, or straight segment. Drag the vertices of the line around and see the orientation change! You can also double-click to add a vertex to the line.4f:T95e,const turnDemo = (() => { const width = 928; const height = 600; const svg = d3.create("svg") .attr("width", width) .attr("height", height) .attr("viewBox", [0, 0, width, height]) .attr("style", "max-width: 100%; height: auto; background: #dff;border:1px solid #0cc;"); let id = 0; const vertices: Vertex[] = [ {x: 180, y: 250, id: id++}, {x: 420, y: 100, id: id++}, {x: 500, y: 300, id: id++}, {x: 400, y: 300, id: id++}, {x: 400, y: 400, id: id++} ]; const route = svg.append("g").attr("class", "route-outer"); route.append("path").attr("class", "route"); const gCircles = svg.append("g"); function update() { for (const v of vertices) v.turn = undefined; for (let i = 2; i < vertices.length; i++) { vertices[i - 1].turn = cross(vertices[i - 2], vertices[i - 1], vertices[i]); } const node = gCircles.selectAll(".circle") .data(vertices, d => d.id) .join(enter => enter.append("g") .attr("class", "circle") .call(g => g.append("circle").attr("r", 10)) .call(g => g.append("text") .attr("x", 15) .attr("y", 4) .attr("fill", "#000") .attr("stroke", "none") .attr("pointer-events", "none")) .call(d3.drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended))) .attr("transform", ({x, y}) => `translate(${x},${y})`); node.select("circle") .attr("fill", d => d.turn > 0 ? "#8888E7" : d.turn < 0 ? "#E78888" : "white"); node.select("text") .text(d => d.turn > 0 ? "right" : d.turn < 0 ? "left" : ""); const ctx = d3.path(); ctx.moveTo(vertices[0].x, vertices[0].y); for (const {x, y} of vertices.slice(1)) ctx.lineTo(x, y); route.select(".route").attr("d", ctx.toString()); } svg.on("dblclick", e => { e.preventDefault(); const [x, y] = d3.pointer(e, svg.node()); vertices.push({x, y, id: id++}); update(); }); function dragstarted(event) { d3.select(event.sourceEvent.target.closest(".circle")).raise(); svg.style("overflow", "visible"); } function dragged(event, d) { d.x = clamp(event.x, 10, width - 10); d.y = clamp(event.y, 10, height - 10); update(); } function dragended() { svg.style("overflow", null); } update(); return svg.node(); })(); display(turnDemo);50:[] 48:{"id":"356767f4acbc61b5","slug":"convex-hull","title":"Convex hull","thumbnail":"d62d19117e605831a4a74183b6fef94d98e418a83ad581ac75b12307fa0a33b3","access_level":"public","create_time":"$D2026-11-06T12:58:50.383Z","update_time":"$D2026-11-06T14:46:38.000Z","view_time":null,"first_public_time":"$D2026-11-06T14:40:28.080Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"b47c3705cfcd7c1b","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":"starter_2024","bio":"hi!","followed_by_you":false,"follows_you":false},"version":214,"publish_version":214,"role":null,"authored":false,"authors":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"bio":"hi!","followed_by_you":false,"follows_you":false}],"members":[{"type":"team","id":"b47c3705cfcd7c1b","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Convex hull","cells":[{"id":1,"value":"$4c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"$4d","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$4e","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$4f","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"type Vertex = { x: number, y: number, id: number, turn?: number };","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"","pinned":true,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"function convexHull(circles: Circle[]) {\n if (circles.length < 3) return null;\n const sorted = circles.toSorted((a, b) => a.x - b.x || a.y - b.y);\n\n const upper: Circle[] = [];\n const lower: Circle[] = [];\n for (let i = 0; i < sorted.length; i++) {\n while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], sorted[i]) <= 0) {\n lower.pop();\n }\n lower.push(sorted[i]);\n }\n for (let i = sorted.length - 1; i >= 0; i--) {\n while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], sorted[i]) <= 0) {\n upper.pop();\n }\n upper.push(sorted[i]);\n }\n upper.pop();\n lower.pop();\n return [...lower, ...upper];\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"function clamp(x, lo, hi) {\n return x < lo ? lo : x > hi ? hi : x;\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"function cross(a, b, o) {\n return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"type Circle = { x: number, y: number, r: number, id: number };","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W50","stdlib":"2"}} 24:null