2e:null 2f:["$","title",null,{"children":"To Infinity and Back Again | Mike Bostock | Observable"}] 34:T545,{ const l = 40; const {points, v0, vn} = polygon; const p0 = points[0]; const pn = points[points.length - 1]; return html``; }35:T598,{ const l = 40; const {points, v0, vn} = polygon; const p0 = points[0], p_1 = project(p0, v0); const pn_1 = points[points.length - 1], pn = project(pn_1, vn); return html``; }36:T7c0,{ const l = 40; const {points, v0, vn} = polygon; const p0 = points[0]; const pn = points[points.length - 1]; return html``; }37:T449,html``38:T4ce,function clipInfinite(polygon) { let P = polygon.points.slice(), p, n; if (p = project(P[0], polygon.v0)) P.unshift(p); if (p = project(P[P.length - 1], polygon.vn)) P.unshift(p); if (n = (P = clip(P)).length) { for (let i = 0, c0, c1 = sidecode(P[n - 1]); i < n; ++i) { c0 = c1, c1 = sidecode(P[i]); if (c0 && c1) { while (c0 !== c1) { let c; switch (c0) { case 0b0101: c0 = 0b0100; continue; // top-left case 0b0100: c0 = 0b0110, c = [xmax, ymin]; break; // top case 0b0110: c0 = 0b0010; continue; // top-right case 0b0010: c0 = 0b1010, c = [xmax, ymax]; break; // right case 0b1010: c0 = 0b1000; continue; // bottom-right case 0b1000: c0 = 0b1001, c = [xmin, ymax]; break; // bottom case 0b1001: c0 = 0b0001; continue; // bottom-left case 0b0001: c0 = 0b0101, c = [xmin, ymin]; break; // left } if (contains(polygon, c)) { P.splice(i, 0, c), ++n, ++i; } } } } } else if (contains(polygon, [(xmin + xmax) / 2, (ymin + ymax) / 2])) { P.push([xmin, ymin], [xmax, ymin], [xmax, ymax], [xmin, ymax]); } return P; }39:[{"id":"476489e94d6c5901826a84b618dad2eaf8546ccce06c7e7436ae5e832d3c8011c6b6247a3b0c18b7cdfa5122e84f66fcbc6e7a3759011a6cfb1b0066c73354ce","href":"https://static.observableusercontent.com/files/476489e94d6c5901826a84b618dad2eaf8546ccce06c7e7436ae5e832d3c8011c6b6247a3b0c18b7cdfa5122e84f66fcbc6e7a3759011a6cfb1b0066c73354ce","name":"image.png","type":"image/png","lastModified":1573258765930.845,"size":949631},{"id":"a9d06264afded21cabbee5d6294dd6b410539a9ea0c1dade7f3e3e8d8f814f6f576609879bf70fb54eccd6e02e3749d60bc8d8bf51676ea17aa73473c5790887","href":"https://static.observableusercontent.com/files/a9d06264afded21cabbee5d6294dd6b410539a9ea0c1dade7f3e3e8d8f814f6f576609879bf70fb54eccd6e02e3749d60bc8d8bf51676ea17aa73473c5790887","name":"infinity.png","type":"image/png","lastModified":1573258854244.836,"size":495262}] 32:{"id":"d876926431d89758","slug":"to-infinity-and-back-again","title":"To Infinity and Back Again","thumbnail":"451e92e31ad47ab04e020f0ece177d258401564838bc8b46d3b2e284df191def","access_level":"public","create_time":"$D2018-03-18T00:25:46.674Z","update_time":"$D2019-11-09T00:20:55.011Z","view_time":null,"first_public_time":"$D2018-03-18T00:25:54.211Z","has_unpublished_edits":null,"fork":true,"stars":28,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":2668,"publish_version":2668,"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,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"b0b8183de839aa32","slug":"algorithms","title":"Algorithms","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"title":"To Infinity and Back Again","cells":[{"id":0,"value":"md`# To Infinity and Back Again\n\nWhen dealing with polygons in computer graphics, we often worry only about *finite* polygons: a two-dimensional polygon ${tex`P`} represented as a sequence of points ${tex`[p_0, p_1, ..., p_{n-1}]`} where ${tex`p_i = [x_i,y_i]`}. Various standard algorithms—area, centroid, point-in-polygon, clipping, *etc.*—assume this representation.\n\nBut sometimes a polygon is *infinite*, such as a cell on the exterior of a [Voronoi diagram](/@mbostock/voronoi-particles). This diagram shows the area of the plane closest to each given *site* (point). For a site on the convex hull, the corresponding cell extends forever.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2024,"value":"FileAttachment(\"infinity.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2026,"value":"md`To show a Voronoi diagram, then, we need a way to clip infinite polygons to the viewport; we can’t directly pass them to a standard graphics API such as Canvas or SVG. And this presents a challenge, as it is not obvious how to apply finite algorithms such as [Sutherland–Hodgman](/@mbostock/sutherland-hodgman-clipping) to infinite polygons.\n\nThe first step to solving any problem is to describe it, so let’s first define this type of infinite convex polygon. In addition to the sequence of points ${tex`[p_0, p_1, ..., p_{n-1}]`}, we need two vectors ${tex`v_0 = [\\Delta x_0,\\Delta y_0]`} and ${tex`v_n = [\\Delta x_n,\\Delta y_n]`}. The start edge is incoming to ${tex`p_0`} along ${tex`-v_0`} and the end edge is outgoing from ${tex`p_{n-1}`} along ${tex`+v_n`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1876,"value":"polygon = {\n const a0 = (now / 30000) % 2 * Math.PI;\n const an = a0 + Math.PI / 2 + Math.sin(now / 5000);\n const cx = (xmin + xmax) / 2;\n const cy = (ymin + ymax) / 2;\n const r = (xmax - xmin) / 3;\n const P = [];\n for (let i = 0, n = 8; i < n; ++i) {\n const a = a0 + i / (n - 1) * (an - a0);\n P.push([cx + Math.cos(a) * r, cy + Math.sin(a) * r]);\n }\n return {\n points: P,\n v0: [Math.sin(a0), -Math.cos(a0)],\n vn: [-Math.sin(an), Math.cos(an)] \n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":815,"value":"md`The infinite start and end edges are known as [*rays*](http://mathworld.wolfram.com/Ray.html). Each contains all points on the “half-infinite” line starting at ${tex`p`} and extending forever in the direction of ${tex`v`}:\n\n${tex.block`\\overrightarrow{pv} = p + tv \\; \\forall t\\in[0,\\infty]`}\n\nWe also need to define our viewport. It is an axis-aligned rectangle where a given point ${tex`p = [x, y]`} is inside if and only if four conditions are met:\n\n${tex.block`\\begin{aligned}\nx &\\geq x_{min} \\\\\nx &\\leq x_{max} \\\\\ny &\\geq y_{min} \\\\\ny &\\leq y_{max}\n\\end{aligned}`}\n\nNow let’s consider how the rays interact with the viewport, starting with the right side. One possibility is that the ray starts inside the viewport, and points right-ish:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2235,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2237,"value":"md`Clearly, we’ll need to compute the intersection between the ray and the right side of the viewport, and we can ignore the left side. But a left-ish ray can *also* be pointing up-ish, in which case it may intersect with the top side of the viewport first; or it may also be down-ish and we’ll need to test the bottom side. So we must test at most two sides to determine which is closest.\n\nWhat if the ray is instead pointing left-ish?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2240,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2259,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2275,"value":"md`If the ray starts inside the viewport, it can’t intersect the right side of the viewport. If the ray starts outside, it *can* intersect with the right side, but we don’t care! It’ll *also* intersect with another side of the viewport, and it’s that other intersection that we care about. A left-ish ray never needs testing against the right side.\n\nFinally, what of a right-pointing ray that starts outside the viewport?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2242,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2269,"value":"md`Here not only does the ray not intersect the right side of the viewport, it can’t intersect *any* side of the viewport, so we can cut short our tests. Putting it all together, here is the code for projecting a ray against the viewport:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":821,"value":"function project([x0, y0], [vx, vy]) {\n let t = Infinity, c, x, y;\n if (vy < 0) { // top\n if (y0 <= ymin) return;\n if ((c = (ymin - y0) / vy) < t) y = ymin, x = x0 + (t = c) * vx;\n } else if (vy > 0) { // bottom\n if (y0 >= ymax) return;\n if ((c = (ymax - y0) / vy) < t) y = ymax, x = x0 + (t = c) * vx;\n }\n if (vx > 0) { // right\n if (x0 >= xmax) return;\n if ((c = (xmax - x0) / vx) < t) x = xmax, y = y0 + (t = c) * vy;\n } else if (vx < 0) { // left\n if (x0 <= xmin) return;\n if ((c = (xmin - x0) / vx) < t) x = xmin, y = y0 + (t = c) * vy;\n }\n return [x, y];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2345,"value":"md`Projecting the start and end edges produces (at most) two new points:\n\n${tex.block`\\begin{aligned}\np_{-1} &= p_0 + t_0v_0 \\\\\np_n &= p_{n-1} + t_nv_n\n\\end{aligned}`}\n\nThe resulting finite polygon ${tex`P' = [p_{-1}, p_0, ..., p_{n-1}, p_n]`} is clippable, but it’s missing something. Can you guess what?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2354,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1630,"value":"md`The viewport corners!\n\nAfter clipping ${tex`P'`}, we need to add back any corner ${tex`c`} of the viewport that was inside the original infinite polygon ${tex`P`}. And this requires a point-in-polygon test for infinite polygons. Fortunately our infinite polygon is convex, so we simply need to test that every triangle ${tex`\\overline{cab}`} is clockwise for all polygon edges ${tex`\\overline{ab}`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1566,"value":"function contains({points, v0, vn}, p) {\n let n = points.length, p0, p1 = points[0];\n if (clockwise(p, [p1[0] + v0[0], p1[1] + v0[1]], p1)) return false;\n for (let i = 1; i < n; ++i) if (clockwise(p, p0 = p1, p1 = points[i])) return false;\n if (clockwise(p, p1, [p1[0] + vn[0], p1[1] + vn[1]])) return false;\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1562,"value":"function clockwise([x0, y0], [x1, y1], [x2, y2]) {\n return (x1 - x0) * (y2 - y0) < (y1 - y0) * (x2 - x0);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2396,"value":"md`Here again is our polygon, with the corners of the viewport highlighted. If the corner is inside the polygon, it is filled ; otherwise it is empty .`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1774,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2403,"value":"md`We’re close now—we know all the points in the final polygon! But there’s a wrinkle: we don’t know *where* in the sequence of points to insert the corners.\n\nRather than checking each corner separately, observe that corners only need to be added when the clipped polygon contains an edge that “jumps” from one side of the viewport to another. For example, if there’s an edge from the left side to the top side, we may need to add the top-left corner of the viewport to the polygon.\n\nTo identify these jumps, we’ll adapt a technique from the [Cohen–Sutherland algorithm](https://en.wikipedia.org/wiki/Cohen–Sutherland_algorithm) and assign a four-bit code to points based on which side of the viewport they lie; any point that is not exactly on the edge of the viewport has the code 0000. Here, for example, is a left-to-top (0001-to-0100) jump:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2533,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2433,"value":"function sidecode([x, y]) {\n return (x === xmin ? 1\n : x === xmax ? 2 : 0)\n | (y === ymin ? 4\n : y === ymax ? 8 : 0);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2592,"value":"md`When there’s a jump, we need to test the corners that are *between* the jumped sides in clockwise order. So, when jumping from left to top, we check the top-left corner. But when jumping from left to bottom, we check three corners: top-left, top-right, and bottom-right.\n\nThe end is now in sight, but like any good story, there’s one last challenge. Our clipped, projected polygon could be completely empty, as when neither the points nor the rays of the infinite polygon intersect the viewport. But the infinite polygon could still surround the viewport entirely! So when the clipped polygon is empty, we test whether the viewport centroid is inside the infinite polygon. If it is, the polygon covers the viewport entirely.\n\nPutting it all together, the complete code:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2437,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2625,"value":"md`At last, our clipped polygon! 🎉\n\nWe made it to infinity… and back again.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1703,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":727,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"xmin = 0.75","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"ymin = 0.75","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"xmax = 639.25","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"ymax = 499.25","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1743,"value":"function centroid(polygon) {\n var i = -1,\n n = polygon.length,\n x = 0,\n y = 0,\n a,\n b = polygon[n - 1],\n c,\n k = 0;\n\n while (++i < n) {\n a = b;\n b = polygon[i];\n k += c = a[0] * b[1] - b[0] * a[1];\n x += (a[0] + b[0]) * c;\n y += (a[1] + b[1]) * c;\n }\n\n return k *= 3, [x / k, y / k];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"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","output":"$undefined","database":"$undefined"},{"id":11,"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","output":"$undefined","database":"$undefined"},{"id":3,"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","output":"$undefined","database":"$undefined"},{"id":444,"value":"clip = {\n const top = clipper(inside.top, intersect.top);\n const right = clipper(inside.right, intersect.right);\n const bottom = clipper(inside.bottom, intersect.bottom);\n const left = clipper(inside.left, intersect.left);\n return function clip(subject) {\n return left(bottom(right(top(subject))));\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 33:"$32:body"