See d3-equidecompose.
Last active
August 10, 2016 06:03
-
-
Save bmershon/78f156a1a372c6001b52f0bb13a25514 to your computer and use it in GitHub Desktop.
Sutherland-Hodgman Clipping II
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| license: gpl-3.0 | |
| border: yes |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment