2b:null 2c:["$","title",null,{"children":"Sutherland–Hodgman Clipping | Mike Bostock | Observable"}] 31:T6b3,viewof subject = { const subject = [[279, 200], [466, 100], [652, 200], [559, 450], [372, 420]]; const svg = d3.select(DOM.svg(Math.min(640, width), Math.min(width, 500))) .property("value", subject) .attr("viewBox", [(932 - 500) / 2, 0, 500, 500]) .style("height", "auto"); const path = svg.append("path") .attr("fill", "blue") .attr("fill-opacity", 0.1) .attr("stroke", "blue"); svg.append("rect") .attr("fill", "red") .attr("fill-opacity", 0.1) .attr("stroke", "red") .attr("x", xmin) .attr("y", ymin) .attr("width", xmax - xmin) .attr("height", ymax - ymin); const clipPath = svg.append("path") .attr("fill", "lightgray") .attr("stroke", "black") .attr("stroke-width", 1.5); const point = svg.append("g") .attr("cursor", "move") .attr("pointer-events", "all") .attr("fill", "blue") .attr("stroke", "transparent") .attr("stroke-width", 30) .selectAll("circle") .data(subject) .enter().append("circle") .attr("r", 4) .call(d3.drag() .subject(([x, y]) => ({x, y})) .on("drag", dragged)); update(); function dragged(d) { d[0] = d3.event.x; d[1] = d3.event.y; update(); svg.dispatch("input") } function update() { point.attr("cx", d => d[0]).attr("cy", d => d[1]); path.attr("d", `M${subject.join("L")}Z`); clipPath.attr("d", `M${clipBox(subject).join("L")}Z`); } function clipBox(points) { points = clip.top(points); points = clip.right(points); points = clip.bottom(points); points = clip.left(points); return points; } return svg.node(); }32:Td13,function* animation(subject, mode) { const svg = d3.create("svg") .attr("viewBox", [(932 - 500) / 2, 0, 500, 500]) .attr("width", Math.min(640, width)) .attr("height", Math.min(500, width)) .style("height", "auto"); svg.append("path") .attr("fill", "blue") .attr("fill-opacity", 0.1) .attr("stroke", "blue") .attr("d", `M${subject.join("L")}Z`); svg.append("rect") .attr("fill", "red") .attr("fill-opacity", 0.1) .attr("stroke", "red") .attr("x", mode === "left" ? xmin : -1) .attr("y", mode === "top" ? ymin : -1) .attr("width", mode === "right" ? xmax : 1001) .attr("height", mode === "bottom" ? ymax : 1001); if (!subject.length) { yield svg.node(); return; } const clipped = svg.append("g"); do { let p0, p1 = subject[subject.length - 1], t0, t1 = inside[mode](p1), P = []; clipped.selectAll("*").remove(); yield svg.node(); for (let i = 0; i < subject.length; ++i) { p0 = p1, t0 = t1, p1 = subject[i], t1 = inside[mode](p1); yield Promises.delay(1000, svg.node()); clipped.append("circle") .attr("fill", t1 ? "black" : "none") .attr("stroke", t1 ? "none" : "black") .attr("r", 0) .attr("cx", p1[0]) .attr("cy", p1[1]) .transition() .delay(t0 !== t1 ? 500 : 250) .attr("r", 4); if (t0 !== t1) { let p = intersect[mode](p0, p1); if (P.length) clipped.insert("line", "circle") .attr("x1", P[P.length - 1][0]) .attr("y1", P[P.length - 1][1]) .attr("x2", P[P.length - 1][0]) .attr("y2", P[P.length - 1][1]) .attr("stroke", "black") .attr("stroke-width", 1.5) .transition() .attr("x2", p[0]) .attr("y2", p[1]); clipped.append("circle") .attr("fill", "red") .attr("r", 0) .attr("cx", p[0]) .attr("cy", p[1]) .transition() .delay(250) .attr("r", 4); P.push(p); } if (t1) { if (P.length) clipped.insert("line", "circle") .attr("x1", P[P.length - 1][0]) .attr("y1", P[P.length - 1][1]) .attr("x2", P[P.length - 1][0]) .attr("y2", P[P.length - 1][1]) .attr("stroke", "black") .attr("stroke-width", 1.5) .transition() .delay(t0 !== t1 ? 250 : 0) .attr("x2", p1[0]) .attr("y2", p1[1]); P.push(p1); } } yield Promises.delay(1000, svg.node()); if (P.length) clipped.append("line") .attr("x1", P[P.length - 1][0]) .attr("y1", P[P.length - 1][1]) .attr("x2", P[P.length - 1][0]) .attr("y2", P[P.length - 1][1]) .attr("stroke", "black") .attr("stroke-width", 1.5) .transition() .attr("x2", P[0][0]) .attr("y2", P[0][1]); clipped.insert("path", "*") .attr("fill", "lightgray") .attr("fill-opacity", 0) .attr("d", `M${clip[mode](subject).join("L")}Z`) .transition() .attr("fill-opacity", 1); yield Promises.delay(5000, svg.node()); } while (loop); }33:[] 2f:{"id":"9114981c05c2d393","slug":"sutherland-hodgman-clipping","title":"Sutherland–Hodgman Clipping","thumbnail":"c1c85a33379a7f2ad292e50a32779a52346399c5ae34f249fdd1d8028a59b54d","access_level":"public","create_time":"$D2018-01-22T16:57:46.095Z","update_time":"$D2020-08-01T16:49:49.052Z","view_time":null,"first_public_time":"$D2018-01-22T17:30:10.345Z","fork":false,"stars":21,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"starter_2024"},"version":913,"publish_version":913,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":16,"collection":{"id":"b0b8183de839aa32","slug":"algorithms","title":"Algorithms","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"title":"Sutherland–Hodgman Clipping","cells":[{"id":0,"value":"md`# Sutherland–Hodgman Clipping\n\nThe Sutherland–Hodgman algorithm clips a *subject* polygon (shown in blue below) to a convex *clip* polygon (red). Try dragging the subject’s points; the resulting clipped polygon (gray) is the intersection between the subject and clip polygons.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":500,"value":"md`To understand how the algorithm works, let’s consider a simpler problem first: how can we clip the subject polygon against the top edge of the clip polygon? In other words, let’s just shave a little off the top.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":559,"value":"{\n const svg = d3.select(DOM.svg(Math.min(640, width), Math.min(width, 500)))\n .property(\"value\", subject)\n .attr(\"viewBox\", [(932 - 500) / 2, 0, 500, 500])\n .style(\"height\", \"auto\");\n \n svg.append(\"path\")\n .attr(\"fill\", \"blue\")\n .attr(\"fill-opacity\", 0.1)\n .attr(\"stroke\", \"blue\")\n .attr(\"d\", `M${subject.join(\"L\")}Z`);\n \n svg.append(\"rect\")\n .attr(\"fill\", \"red\")\n .attr(\"fill-opacity\", 0.1)\n .attr(\"stroke\", \"red\")\n .attr(\"x\", 0)\n .attr(\"y\", ymin)\n .attr(\"width\", 1000)\n .attr(\"height\", 1000);\n \n svg.append(\"path\")\n .attr(\"fill\", \"lightgray\")\n .attr(\"stroke\", \"black\")\n .attr(\"stroke-width\", 1.5)\n .attr(\"d\", `M${clip.top(subject).join(\"L\")}Z`);\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":557,"value":"md`The clip region is defined by ${tex`y_{min}`}. Any point ${tex`[x,y]`} where ${tex`y \\geq y_{min}`} (*i.e.*, where the point is below the red line above) is inside the clip region.\n\nThe subject polygon is defined by a sequence of points ${tex`[p_0, p_1, ..., p_{n-1}]`} where each point ${tex`p_i = [x_i, y_i]`}. A small but important detail is that this is an *open* definition of a polygon, which means that the first point ${tex`p_0`} and last point ${tex`p_{n-1}`} are not the same. Some geometry representations, such as GeoJSON, instead use closed definitions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":153,"value":"subject","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":614,"value":"md`Now here’s the Sutherland–Hodgman algorithm:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":26,"value":"function clipper(inside, intersect) {\n return function(subject) {\n const P = [], n = subject.length;\n if (!n) return P;\n let p0, p1 = subject[n - 1];\n let t0, t1 = inside(p1);\n for (let i = 0; i < n; ++i) {\n p0 = p1, p1 = subject[i];\n t0 = t1, t1 = inside(p1);\n if (t1 !== t0) P.push(intersect(p0, p1));\n if (t1) P.push(p1);\n }\n return P;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":626,"value":"md`The algorithm iterates over the subject polygon’s points, testing whether each point ${tex`p_i`} is inside the clip region; any point that is inside is included in the result. And, if the “insideness” of ${tex`p_i`} is *different* than the previous point ${tex`p_{i-1}`} (that is, if ${tex`p_i`} is inside, but ${tex`p_{i-1}`} is outside, or *vice versa*), then the intersection between the line segment ${tex`\\overline{p_{i-1}p_i}`} and the clip region is also added to the result.\n\nReading code can be tricky for humans, so here’s the process animated:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":649,"value":"animation(subject, \"top\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":682,"value":"md`If you moved the subject polygon around at the top of this notebook, your changes will be reflected in these animations! For best results, it helps if the subject polygon intersects all four sides of the clip region. You can reload to reset the subject polygon back to its original position.\n\nThese animations are looped. If this is too distracting, uncheck this box:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":862,"value":"viewof loop = {\n const form = html`

Loop animation`;\n form.i.onclick = () => {\n form.value = form.i.checked;\n form.dispatchEvent(new CustomEvent(\"input\"));\n };\n form.value = form.i.checked;\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":865,"value":"md`Now that we’ve successfully clipped the *top* of the subject polygon, it’s a simple matter of clipping the remaining three sides. We take the top-clipped polygon from above and clip the right side:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":724,"value":"animation(clip.top(subject), \"right\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":732,"value":"md`And then the bottom:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":735,"value":"animation(clip.right(clip.top(subject)), \"bottom\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":768,"value":"md`And lastly the left:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":771,"value":"animation(clip.bottom(clip.right(clip.top(subject))), \"left\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":714,"value":"md`And that’s it!\n\nHere are the implementations of *inside* and *intersect* used by this notebook. This a specialized implementation of the Sutherland–Hodgman algorithm: it only allows clipping against an axis-aligned bounding box. This is a common use case, such as clipping to the viewport.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":668,"value":"inside = ({\n top: ([x, y]) => y >= ymin,\n right: ([x, y]) => x <= xmax,\n bottom: ([x, y]) => y <= ymax,\n left: ([x, y]) => x >= xmin\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":672,"value":"intersect = ({\n top: ([x0, y0], [x1, y1]) => [x0 + (x1 - x0) * (ymin - y0) / (y1 - y0), ymin],\n right: ([x0, y0], [x1, y1]) => [xmax, y0 + (y1 - y0) * (xmax - x0) / (x1 - x0)],\n bottom: ([x0, y0], [x1, y1]) => [x0 + (x1 - x0) * (ymax - y0) / (y1 - y0), ymax],\n left: ([x0, y0], [x1, y1]) => [xmin, y0 + (y1 - y0) * (xmin - x0) / (x1 - x0)]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":829,"value":"md`The algorithm extends to any convex clip polygon, however, provided you implement the *inside* and *intersection* functions accordingly. Try forking this notebook to explore these alternatives.\n\nThanks for reading! You can send me feedback or questions on [Twitter](https://twitter.com/mbostock).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":833,"value":"md`---\n\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":753,"value":"clip = ({\n top: clipper(inside.top, intersect.top),\n right: clipper(inside.right, intersect.right),\n bottom: clipper(inside.bottom, intersect.bottom),\n left: clipper(inside.left, intersect.left)\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":641,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":158,"value":"xmin = 310","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":419,"value":"xmax = 620","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":417,"value":"ymin = 120","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":421,"value":"ymax = 400","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":135,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"