2c:null 2d:["$","title",null,{"children":"Sutherland–Hodgman clipping to a triangle | Kelley van Evert | Observable"}] 32:T700,viewof svg = { const W = 600 const H = 400 const svg = d3.select(DOM.svg(W, H)) fill_textures.forEach(t => svg.call(t)) const tg = svg.append('g').attr('class', 'triangle_layer') const ig = svg.append('g').attr('class', 'intersect_layer') const hg = svg.append('g').attr('class', 'handle_layer') function update () { const t = tg.selectAll('g').data(mutable polygons) const t_add = t.enter().append('g') t_add.append('path').attr('class', 'fill').attr('fill', fill_textures[0].url()) t_add.append('path').attr('class', 'edge').attr('stroke-width', 1.5).attr('stroke', '#333') const t_upd = t_add.merge(t) t_upd.select('path.fill') .attr('d', tr => line(tr) + 'z') t_upd.select('path.edge') .attr('fill', 'none') .attr('d', tr => line(tr) + 'z') const points = flatten(mutable polygons) const h = hg.selectAll('g').data(points, pt => pt[2]) const h_add = h.enter().append('g'); h_add.append('circle').attr('r', 6) .attr('fill', '#000') .attr('class', P => 'pt ' + P[2]) .style('cursor', 'pointer') .call(d3.drag().on('drag', drag_handle)) h_add.append('text').attr('y', -14).text(P => P[2]) .attr('font-family', 'monospace') const h_upd = h_add.merge(h) h_upd.select('circle').attr('cx', P => P[0]).attr('cy', P => P[1]) h_upd.select('text').attr('x', P => P[0]).attr('y', P => P[1]-15) //h_upd.attr('transform', P => `translate(${P[0]-3} ${P[1]-3})`) } function drag_handle (P) { P[0] = constrain(d3.event.x, 8, W-8-5); P[1] = constrain(d3.event.y, 8+30, H-8); mutable polygons = mutable polygons update(); svg.node().dispatchEvent(new CustomEvent('input')) } update() svg.node().value = svg return svg.node() }33:T1632,// https://riccardoscalco.github.io/textures/ textures = { var t=function(){return(Math.random().toString(36)+"00000000000000000").replace(/[^a-z]+/g,"").slice(0,5)};return{circles:function(){var r=20,n="",e=2,a=!1,u="#343434",i="#343434",c=0,l=t(),o=function(t){var o=t.append("defs").append("pattern").attr("id",l).attr("patternUnits","userSpaceOnUse").attr("width",r).attr("height",r);n&&o.append("rect").attr("width",r).attr("height",r).attr("fill",n),o.append("circle").attr("cx",r/2).attr("cy",r/2).attr("r",e).attr("fill",u).attr("stroke",i).attr("stroke-width",c),a&&[[0,0],[0,r],[r,0],[r,r]].forEach(function(t){o.append("circle").attr("cx",t[0]).attr("cy",t[1]).attr("r",e).attr("fill",u).attr("stroke",i).attr("stroke-width",c)})};return o.heavier=function(t){return 0===arguments.length?e*=2:e*=2*t,o},o.lighter=function(t){return 0===arguments.length?e/=2:e/=2*t,o},o.thinner=function(t){return 0===arguments.length?r*=2:r*=2*t,o},o.thicker=function(t){return 0===arguments.length?r/=2:r/=2*t,o},o.background=function(t){return n=t,o},o.size=function(t){return r=t,o},o.complement=function(t){return a=0===arguments.length||t,o},o.radius=function(t){return e=t,o},o.fill=function(t){return u=t,o},o.stroke=function(t){return i=t,o},o.strokeWidth=function(t){return c=t,o},o.id=function(t){return 0===arguments.length?l:(l=t,o)},o.url=function(){return"url(#"+l+")"},o},lines:function(){var r=20,n="#343434",e=2,a="",u=t(),i=["diagonal"],c="auto",l=function(t){var n=r;switch(t){case"0/8":case"vertical":return"M "+n/2+", 0 l 0, "+n;case"1/8":return"M "+n/4+",0 l "+n/2+","+n+" M "+-n/4+",0 l "+n/2+","+n+" M "+3*n/4+",0 l "+n/2+","+n;case"2/8":case"diagonal":return"M 0,"+n+" l "+n+","+-n+" M "+-n/4+","+n/4+" l "+n/2+","+-n/2+" M "+.75*n+","+5/4*n+" l "+n/2+","+-n/2;case"3/8":return"M 0,"+.75*n+" l "+n+","+-n/2+" M 0,"+n/4+" l "+n+","+-n/2+" M 0,"+5*n/4+" l "+n+","+-n/2;case"4/8":case"horizontal":return"M 0,"+n/2+" l "+n+",0";case"5/8":return"M 0,"+-n/4+" l "+n+","+n/2+"M 0,"+n/4+" l "+n+","+n/2+" M 0,"+3*n/4+" l "+n+","+n/2;case"6/8":return"M 0,0 l "+n+","+n+" M "+-n/4+","+.75*n+" l "+n/2+","+n/2+" M "+3*n/4+","+-n/4+" l "+n/2+","+n/2;case"7/8":return"M "+-n/4+",0 l "+n/2+","+n+" M "+n/4+",0 l "+n/2+","+n+" M "+3*n/4+",0 l "+n/2+","+n;default:return"M "+n/2+", 0 l 0, "+n}},o=function(t){var o=t.append("defs").append("pattern").attr("id",u).attr("patternUnits","userSpaceOnUse").attr("width",r).attr("height",r);a&&o.append("rect").attr("width",r).attr("height",r).attr("fill",a),i.forEach(function(t){o.append("path").attr("d",l(t)).attr("stroke-width",e).attr("shape-rendering",c).attr("stroke",n).attr("stroke-linecap","square")})};return o.heavier=function(t){return 0===arguments.length?e*=2:e*=2*t,o},o.lighter=function(t){return 0===arguments.length?e/=2:e/=2*t,o},o.thinner=function(t){return 0===arguments.length?r*=2:r*=2*t,o},o.thicker=function(t){return 0===arguments.length?r/=2:r/=2*t,o},o.background=function(t){return a=t,o},o.size=function(t){return r=t,o},o.orientation=function(){for(var t=arguments.length,r=Array(t),n=0;n pt[2]).join('')\n return tex.block`\\text{intersect}(${triangle.map(pt => pt[2]).join('')}, ${subject.map(pt => pt[2]).join('')}) = ${U || `\\\\varnothing`}`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1414,"value":"md`Drag the black-filled vertices around to adjust the position and shape of the clipping triangle (${tex`${triangle.map(pt => pt[2]).join('')}`}) and the polygon subject to clipping (${tex`${subject.map(pt => pt[2]).join('')}`}).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1276,"value":"{\n const ig = svg.select('g.intersect_layer')\n ig.selectAll('*').remove()\n \n // intersection area\n ig.append('path').attr('class', 'area').attr('fill', fill_textures[1].url())\n .attr('d', line(clipped) + 'z')\n // intersection edge\n ig.append('path').attr('class', 'edge').attr('stroke-width', 2)\n .attr('stroke', '#000').attr('fill', 'none')\n .attr('d', line(clipped) + 'z')\n \n ig.selectAll('circle').data(new_points)\n .enter().append('circle')\n .attr('r', 6)\n .attr('fill', '#fff').attr('stroke', '#000').attr('stroke-width', 1.5)\n .attr('cx', P => P[0]).attr('cy', P => P[1])\n \n // ...and their labels\n ig.selectAll('text').data(new_points)\n .enter().append('text')\n .text(P => P[2])\n .attr('font-family', 'monospace')\n .attr('x', P => P[0]).attr('y', P => P[1]-15)\n \n return md`**[Clip polygon updating code]**`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1370,"value":"new_points = {\n // label new points\n const labels = 'HIJKLMNOPQRSTUVWXYZ'.split('')\n const new_points = clipped.filter(pt => !pt[2])\n new_points.forEach(pt => pt[2] = labels.shift())\n return new_points\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1243,"value":"clipped = clip_to_triangle(triangle, subject).reverse()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1410,"value":"triangle = polygons[0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1408,"value":"subject = polygons[1]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1304,"value":"mutable polygons = [\n [ // triangle to which we'll be clipping\n [59, 270, 'A'],\n [180, 60, 'B'],\n [570, 310, 'C'],\n ],\n [ // subject polygon\n [300, 50, 'D'],\n [80, 160, 'E'],\n [270, 210, 'F'],\n [200, 240, 'G'],\n ],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1299,"value":"function clip_to_triangle (tr, subject) {\n if (lineside(tr[0], tr[1], tr[2]) > 0) {\n tr = tr.reverse()\n }\n \n const inside = inside_triangle(tr)\n const intersect = intersect_triangle(tr)\n \n var points = subject\n points = clipper(inside['AB'], intersect['AB'])(points)\n points = clipper(inside['BC'], intersect['BC'])(points)\n points = clipper(inside['CA'], intersect['CA'])(points)\n \n return points\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1201,"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":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1204,"value":"// line [x1,y1] -> [x2,y2]\n// point [x,y]\n// lies left of line if sign = +1\n// lies right of line if sign = -1\n// lies on line if 0\nfunction lineside ([x1,y1], [x2,y2], [x,y]) {\n return (x-x1)*(y2-y1)-(y-y1)*(x2-x1)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1203,"value":"// triangle must be specified in clockwise order\ninside_triangle = ([A,B,C]) => ({\n AB: P => lineside(A, B, P) <= 0,\n BC: P => lineside(B, C, P) <= 0,\n CA: P => lineside(C, A, P) <= 0,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1217,"value":"intersect_triangle = ([A,B,C]) => ({\n AB: (P, Q) => intersect_lines(A, B, P, Q),\n BC: (P, Q) => intersect_lines(B, C, P, Q),\n CA: (P, Q) => intersect_lines(C, A, P, Q),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":703,"value":"md``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":700,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":697,"value":"md`The rest is just implementation details.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1236,"value":"function intersect_lines ([x1,y1,l1],[x2,y2,l2], [x3,y3,l3],[x4,y4,l4]) {\n const eps = 0.000001\n const x = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))\n const y = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))\n if (isNaN(x) || isNaN(y)) {\n return false\n }\n var label = undefined\n if (Math.abs(x - x1) < eps && Math.abs(y - y1) < eps) label = l1\n if (Math.abs(x - x2) < eps && Math.abs(y - y2) < eps) label = l2\n if (Math.abs(x - x3) < eps && Math.abs(y - y3) < eps) label = l3\n if (Math.abs(x - x4) < eps && Math.abs(y - y4) < eps) label = l4\n return [x, y, label]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"constrain = (x, min, max) => Math.max(Math.min(x, max), min)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":445,"value":"fill_textures = [\n textures.circles().lighter().thicker().fill('#999'),\n textures.circles().heavier().thicker().fill('#333'),\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":716,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":842,"value":"html`[styling]