Sutherland-Hodgman Clipping II

See d3-equidecompose.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.A {
  fill: none;
  stroke-width: 1px;
  stroke: #727272;
  stroke-dasharray: 5, 5;
}

.B {
  fill: none;
  fill-opacity: 0.5;
  stroke: #727272;
}

.intersection {
  fill-opacity: 0.5;
  stroke: #000;
}

</style>
<body>
<script src="https://d3js.org/d3-polygon.v0.2.min.js"></script>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>

// Copyright 2016, Brooks Mershon and Joy Patel
!function(t,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports,require("d3-polygon")):"function"==typeof define&&define.amd?define(["exports","d3-polygon"],n):n(t.partials=t.partials||{},t.d3_polygon)}(this,function(t,n){"use strict";function r(t,n){var r,o=0;if(t.length!=n.length)throw new Error("Invalid dimensions for dot product.");for(r=0;r<t.length;r++)o+=t[r]*n[r];return o}function o(t){return Math.sqrt(r(t,t))}function e(t,n){return[t*n[0],t*n[1]]}function a(t){return e(1/o(t),t)}function i(t,n,e){var i=a([n[0]-t[0],n[1]-t[1]]),s=a([e[0]-t[0],e[1]-t[1]]);return o(i)*o(s)==0?0:Math.acos(r(i,s))}function s(t,n,r){return n+r>t&&t>n-r}function u(t,n,r){var o,e=[];for(o=0;o<t.length;o++)e[o]=r(t[o],n[o]);return e}function f(t,n){return u(t,n,function(t,n){return t+n})}function c(t,n){return u(t,n,function(t,n){return t-n})}function l(t,n,r,o){var a,i,u,l=c(n,t),h=c(o,r),p=c(r,t),g=0;return a=l[0]*-h[1]- -h[0]*l[1],i=(p[0]*-h[1]- -h[0]*p[1])/a,u=(l[0]*p[1]-p[0]*l[1])/a,s(i,.5,.5+g)&&s(u,.5,.5+g)?f(t,e(i,l)):null}function h(t,n){return e(r(t,n)/r(n,n),n)}function p(t){return 180*t/Math.PI}function g(t){var n=t*Math.PI/180,r=Math.sin(n),o=Math.cos(n);return[[o,-1*r,0],[r,o,0],[0,0,1]]}function v(t){var n,r,o=[[0,0,0],[0,0,0],[0,0,0]];for(n=0;t>n;n++)for(r=0;t>r;r++)o[n][r]=0;for(n=0;t>n;n++)o[n][n]=1;return o}function y(t){var n=t[0],r=t[1],o=v(3);return o[0][2]=n,o[1][2]=r,o}function m(t,n){var r,o=[];for(r=0;r<t[0].length;r++)o[r]=t[n][r];return o}function d(t,n){var o,e=[],a=n.slice();for(o=0;o<3-n.length;o++)a.push(1);for(o=0;o<t.length;o++)e[o]=r(m(t,o),a);return e}function b(t,n){var r,o=[];for(r=0;r<t.length;r++)o[r]=t[r][n];return o}function O(t,n){var o,e,a=[[0,0,0],[0,0,0],[0,0,0]];if(t[0].length!=n.length)throw new Error("invalid dimensions");for(o=0;o<t.length;o++)for(e=0;e<n[0].length;e++)a[o][e]=r(m(t,o),b(n,e));return a}function M(t){this.transforms=[],this._matrix=v(3),this._origin=null}function j(){return n.polygonCentroid(this)}function C(t){return n.polygonContains(this,t)}function _(t){var n,r,o;for(n=0,o=this.length;o>n;n++)r=this[n],this[n]=[r[0]+t[0],r[1]+t[1]];return this}function q(t,n){var r,o,e=g(t);for(n&&this.translate([-n[0],-n[1]]),r=0,o=this.length;o>r;r++)this[r]=d(e,this[r]);return n&&this.translate(n),this}function E(){return this._origin?this._origin:(this._origin=this.accumulate(),this._origin)}function x(){var t,n,r=this.clone(),o=this.transforms.length,a=v(3);for(t=o-1;t>=0;t--)n=this.transforms[t],n.rotate&&n.pivot?(r.rotate(n.rotate,n.pivot),a=O(y(e(-1,n.pivot)),a),a=O(g(n.rotate),a),a=O(y(n.pivot),a)):n.translate&&(r.translate(n.translate),a=O(y(n.translate),a));return r._matrix=a,r}function P(){return w(JSON.parse(JSON.stringify(this.slice())))}function w(t){var n=new M;return n.push.apply(n,t),n}function I(t){var r,o,a,s,u,g,v,y,m,d,b,O,M,j,C,_,q,E,x,P,I=0,A=-(1/0);if(0==n.polygonArea(t))return[];for(P=0;3>P;P++)x=0,x=i(t[P%3],t[(P+1)%3],t[(P+2)%3]),x>A&&(A=x,I=P);return r=t[I],o=t[(I+1)%3],a=t[(I+2)%3],d=c(a,o),b=c(r,o),m=f(o,h(b,d)),u=f(r,e(.5,c(m,r))),O=c(o,m),M=c(a,m),j=c(u,m),v=f(m,f(O,j)),y=f(m,f(M,j)),s=l(u,v,r,o),g=l(u,y,r,a),C=w([o,a,g,s]),_=w([s,v,o]),q=w([g,a,y]),_.transforms.push({rotate:p(Math.PI),pivot:s}),q.transforms.push({rotate:p(-Math.PI),pivot:g}),E=[C,_,q],E.rectangle=[o,a,y,v],E}function A(t,n,r){for(var o,e,a=r.length,i=[],s=[],u=[],f=r[a-1],c=[],h=-1,p=[];++h<a;)if(o=f,f=r[h],e=t!==o&&n!==o||u.length&&Object.is(u[0],o)?t!==f&&n!==f||u.length&&!Object.is(u[0],f)?l(t,n,o,f):f:o){if(2==u.length)break;u.push(e),c.push(h)}if(2==u.length&&!Object.is(u[0],u[1])){for(i.push(u[0]),h=c[0];h!=c[1];)Object.is(u[0],r[h])||Object.is(u[1],r[h])||i.push(r[h]),h=(h+1)%a;for(i.push(u[1]),s.push(u[0]),s.push(u[1]),h=c[1];h!=c[0];)Object.is(u[0],r[h])||Object.is(u[1],r[h])||s.push(r[h]),h=(h+1)%a;p.push(w(i),w(s)),p.forEach(function(t){[].push.apply(t.transforms,r.transforms)})}return p}function S(t,n,r){var o,e,a,i=r.length,s=[],u=[];for(a=0;i>a;a++)o=r[a],e=A(t,n,o),2==e.length&&([].push.apply(u,e),s.push(a));return u=u.concat(r.filter(function(t,n){return-1===s.indexOf(n)}))}function J(t){var r,i,s,u,h,p,g,v,y,m,d,b,O,M,j,C,_,q,E,x,P,w,I,A,J,N,k=t.rectangle,R=1/0,T=[];for(b=Math.abs(n.polygonArea(k)),O=Math.sqrt(b),i=k[0],h=k[3],p=k[1],g=k[2],r=f(i,e(O,a(c(h,i)))),s=f(i,e(O,a(c(p,i)))),u=f(r,c(s,i)),R=o(c(i,p));R>2*O;){for(w=[],I=[],A=[],J=[],C=f(r,e(.5,c(p,i))),_=f(i,e(.5,c(p,i))),R=o(c(_,p)),q=[r,i,_,C],E=S(C,f(_,c(s,u)),t),P=c(h,i),x=c(i,_),E.forEach(function(t,r){N=n.polygonCentroid(t),t.forEach(function(t,n){Object.is(h,t)?(w.push(r),I.push(n)):Object.is(p,t)&&(A.push(r),J.push(n))}),n.polygonContains(q,N)?t.translate(P).transforms.push({translate:e(-1,P)}):t.translate(x).transforms.push({translate:e(-1,x)})}),h=E[w[0]][I[0]],p=E[A[0]][J[0]],M=1,j=J.length;j>M;M++)p=E[A[M]][J[M]]=E[A[M-1]][J[M-1]];t=E}return T=t,g=f(p,c(h,i)),v=l(r,p,h,g),y=l(r,p,u,s),d=[y,s,p],m=[r,p,g,u],T=S(r,p,T),T=S(u,f(s,e(1,c(s,u))),T),T.forEach(function(t){var o,a;o=n.polygonCentroid(t),n.polygonContains(d,o)?(a=c(r,y),t.translate(a).transforms.push({translate:e(-1,a)})):n.polygonContains(m,o)&&(a=c(r,v),t.translate(a).transforms.push({translate:e(-1,a)}))}),T.square=[i,s,u,r],T}function N(t,n,r){var o,e,i,s;return o=a([n[0]-t[0],n[1]-t[1]]),e=a([r[0]-t[0],r[1]-t[1]]),i=o[0]*e[1]-o[1]*e[0],s=[0,0,0],s[0]=s[1]=0,s[2]=i,s}function k(t,n,r,o){var a,i,s,u=c(n,t),l=c(o,r),h=c(t,r);return a=l[0]*-u[1]- -u[0]*l[1],i=(h[0]*-u[1]- -u[0]*h[1])/a,s=(l[0]*h[1]-h[0]*l[1])/a,s>=0&&1>=s?f(r,e(i,l)):[]}function R(t,n){var r=c(t,n[0]),o=c(n[1],n[0]),e=r[0]*o[1]-o[0]*r[1];return e>=0}function T(t){var n;return t.rotate&&t.pivot?n={rotate:-t.rotate,pivot:t.pivot}:t.translate&&(n={translate:e(-1,t.translate)}),n}function z(t,n){var r,o,e,a,i,s,u,f,c,l,h,p,g,v;for(r=w(n.reverse()),o=t.slice(0),i=0;i<r.length;i++)for(u=i+1==r.length?0:i+1,f=[r[i],r[u]],c=o.slice(0),o=[],l=c[c.length-1],s=0;s<c.length;s++)h=c[s],p=!R(h,f),g=!R(l,f),p?(g||(v=k(h,l,r[i],r[u]),v!=[]&&o.push(v)),o.push(h)):g&&(v=k(h,l,r[i],r[u]),v.length&&o.push(v)),l=h;return e=w(o),a=t.transforms.slice(),e.target=n.transforms.slice(0),a=a.concat(n.transforms.slice(0).reverse().map(T)),e.transforms=a,e}function B(t){var n=t.centroid();return t.sort(function(t,r){return Math.atan2(r[1]-n[1],r[0]-n[0])-Math.atan2(t[1]-n[1],t[0]-n[0])}),t}function D(t,n){var r,o,e,a=[];for(o=0;o<t.length;o++)for(e=0;e<n.length;e++)r=z(B(t[o]),B(n[e])),null!=r&&0!=r.length&&0!=r[0].length&&a.push(r);return a}function F(t,n){var r,a,s,u,f,l,h,g,h,v,y,m,d,b,O=1/0;for(r=J(I(t)),a=J(I(n)),s=w(r.square),u=w(a.square),f=s.centroid(),l=u.centroid(),h=[f[0]-l[0],f[1]-l[1]],u=u.clone().translate(h),m=0,d=0;4>m;m++)b=o(c(s[0],u[m])),O>b&&(O=b,d=m);return y=N(f,u[d],s[0])[2]>0?1:-1,v=y*p(i(f,u[d],s[0])),a.forEach(function(t){t.translate(h),t.transforms.push({translate:e(-1,h)}),t.rotate(v,f),t.transforms.push({rotate:-v,pivot:f})}),g=D(r,a),g=g.map(function(t){var n=t.clone();return n.transforms=t.target,n=n.origin(),n.transforms=t.transforms,n})}M.prototype=Object.create(Array.prototype),M.prototype.constructor=M,M.prototype.centroid=j,M.prototype.containsPoint=C,M.prototype.translate=_,M.prototype.rotate=q,M.prototype.accumulate=x,M.prototype.origin=E,M.prototype.clone=P,t.angle=i,t.intersect=l,t.triangle2Rectangle=I,t.cutPolygon=A,t.cutCollection=S,t.rectangle2Square=J,t.triangle2Triangle=F,t.clipCollection=D,t.polygon=w});

var svg,
    width = 960,
    height = 500,
    color,
    N = 100, vertices,
    triangles,
    clip, subject, intersection;

color = d3.scale.category10();

vertices = d3.range(N).map(function(d) {
  return [Math.random() * width, Math.random() * height];
});

svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

clip = [partials.polygon([[50, 50], [50, 450], [450, 450], [450, 50]]),
        partials.polygon([[700, 75], [700, 200], [850, 200], [850, 75]])];

subject = d3.geom.delaunay(vertices).map(function(d) { return partials.polygon(d); });
intersection = partials.clipCollection(subject, clip);

svg.selectAll(".A")
    .data(clip.map(function(d) { return "M" + d.join("L") + "Z"; }), String)  
  .enter().append("path")
    .attr("class", "A")
    .attr("d", String);

svg.selectAll(".B")
    .data(subject.map(function(d) { return "M" + d.join("L") + "Z"; }), String)  
  .enter().append("path")
    .attr("class", "B")
    .attr("d", String);

svg.selectAll(".C")
    .data(intersection.map(function(d) { return "M" + d.join("L") + "Z"; }), String)  
  .enter().append("path")
    .style("fill", function(d, i) { return color(i); })
    .attr("class", "intersection")
    .attr("d", String);
</script>

https://d3js.org/d3-polygon.v0.2.min.js

https://d3js.org/d3.v3.min.js