30:T658,viewof subject = { const subject = [[79, 200], [266, 100], [452, 200], [359, 450], [172, 420]]; const svg = d3.create("svg") .attr("viewBox", [0, 0, width, 500]) .style("overflow", "visible") .property("value", subject); const subjectPath = svg.append("path") .attr("fill", "blue") .attr("fill-opacity", 0.1) .attr("stroke", "blue"); const clipPath = svg.append("path") .attr("fill", "red") .attr("fill-opacity", 0.1) .attr("stroke", "red"); const clippedPath = 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("stroke", "transparent") .attr("stroke-width", 30) .selectAll("circle") .data(subject.concat(clip)) .join("circle") .attr("fill", (_, i) => i < subject.length ? "blue" : "red") .attr("r", 4) .call( d3.drag() .subject((event, [x, y]) => ({ x, y })) .on("drag", dragged) ); update(); function dragged(event, d) { d[0] = event.x; d[1] = event.y; update(); svg.dispatch("input"); } function update() { const clipped = polygonClip(clip, subject); point.attr("cx", d => d[0]).attr("cy", d => d[1]); subjectPath.attr("d", `M${subject.join("L")}Z`); clipPath.attr("d", `M${clip.join("L")}Z`); clippedPath.attr("d", clipped && `M${clipped.join("L")}Z`); clipPath.attr("stroke-dasharray", polygonConvex(clip) ? null : [4, 4]); } return svg.node(); }31:[] 2e:{"title":"Polygon clipping","cells":[{"id":0,"value":"# Polygon clipping\n\nThe Sutherland–Hodgman algorithm clips a *subject* polygon (shown in blue below) to a convex *clip* polygon (red). Try dragging the clip’s or the subject’s points; the resulting clipped polygon (gray) is the intersection between the subject and clip polygons. Note what happens when the *clip* polygon is not convex. See [Sutherland–Hodgman Clipping](/@mbostock/sutherland-hodgman-clipping) for more.","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":1215,"value":"polygonClip(clip, subject)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1213,"value":"subject","pinned":true,"hidden":false,"mode":"ojs"},{"id":1208,"value":"clip = [[210, 90], [110, 400], [420, 400], [490, 250]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":1218,"value":"Given a convex, counterclockwise polygon *clip* and another polygon *subject*, both represented as a sequence of points, *polygonClip* returns the intersection of the two polygons. If the two polygons do not intersect, returns null. This assumes that none of the points in each polygon are coincident, with the possible exception of the first and last point (for “closed” polygons).","pinned":false,"hidden":false,"mode":"md"},{"id":903,"value":"function polygonClip(clip, subject) {\n const closed = polygonClosed(subject);\n const n = clip.length - polygonClosed(clip);\n subject = subject.slice(); // copy before mutate\n for (let i = 0, a = clip[n - 1], b, c, d; i < n; ++i) {\n const input = subject.slice();\n const m = input.length - closed;\n subject.length = 0;\n b = clip[i];\n c = input[m - 1];\n for (let j = 0; j < m; ++j) {\n d = input[j];\n if (lineOrient(d, a, b)) {\n if (!lineOrient(c, a, b)) {\n subject.push(lineIntersect(c, d, a, b));\n }\n subject.push(d);\n } else if (lineOrient(c, a, b)) {\n subject.push(lineIntersect(c, d, a, b));\n }\n c = d;\n }\n if (closed) subject.push(subject[0]);\n a = b;\n }\n return subject.length ? subject : null;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1103,"value":"Given a point ${tex`p`} and an infinite line through the points ${Object.assign(tex`\\overrightarrow{ab}`, {style: \"display: inline-block; margin-top: -6px;\"})}, the *lineOrient* function returns true if the ${tex`p`} is on one side of the line, and false if it is on the other side or intersects. This is not a [robust predicate](https://github.com/mourner/robust-predicates), and assumes that the points ${tex`a`} and ${tex`b`} are not coincident.","pinned":false,"hidden":false,"mode":"md"},{"id":1089,"value":"function lineOrient([px, py], [ax, ay], [bx, by]) {\n return (bx - ax) * (py - ay) < (by - ay) * (px - ax);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1129,"value":"Given two infinite lines, one through the points ${Object.assign(tex`\\overrightarrow{ab}`, {style: \"display: inline-block; margin-top: -6px;\"})} and the other through the points ${Object.assign(tex`\\overrightarrow{cd}`, {style: \"display: inline-block; margin-top: -6px;\"})}, the *lineIntersect* function returns the point ${tex`p`} at which the two lines intersect. This assumes that the lines are not parallel.","pinned":false,"hidden":false,"mode":"md"},{"id":1086,"value":"function lineIntersect([ax, ay], [bx, by], [cx, cy], [dx, dy]) {\n const bax = bx - ax, bay = by - ay, dcx = dx - cx, dcy = dy - cy;\n const k = (bax * (cy - ay) - bay * (cx - ax)) / (bay * dcx - bax * dcy);\n return [cx + k * dcx, cy + k * dcy];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1154,"value":"The *polygonClosed* function returns true if the specified sequence of *points* represent a closed polygon, *i.e.* one where the first and last point are coicident.","pinned":false,"hidden":false,"mode":"md"},{"id":1083,"value":"function polygonClosed(points) {\n const [ax, ay] = points[0], [bx, by] = points[points.length - 1];\n return ax === bx && ay === by;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1159,"value":"The *polygonConvex* function returns true if the specified sequence of *points* represent a convex polygon, *i.e.* one in which no line segment between two points on the boundary ever goes outside the polygon. This assumes that the given sequence contains at least three points, and that the points are in counterclockwise order assuming a coordinate system where ${tex`+y`} points down and ${tex`+x`} points right.","pinned":false,"hidden":false,"mode":"md"},{"id":991,"value":"function polygonConvex(points) {\n const n = points.length;\n const [rx, ry] = points[n - 2];\n let [qx, qy] = points[n - 1];\n let vx = rx - qx, vy = ry - qy;\n for (let i = 0; i < n; ++i) {\n const [px, py] = points[i];\n const wx = qx - px, wy = qy - py;\n if (wx * vy < wy * vx) return false;\n if (wx || wy) vx = wx, vy = wy;\n qx = px, qy = py;\n }\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}