This scissors module makes use of Mapbox's Earcut to triangulate polygons.
Equidecomposition is performed using Sutherland Hodgman clipping.
Last active
December 13, 2016 18:39
-
-
Save bmershon/671778fb88cf6c1e8bcb1b20ebb5a385 to your computer and use it in GitHub Desktop.
Square to Triangle Equidecomposition
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
| border: no | |
| license: MIT |
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> | |
| .source, .subject { | |
| stroke-width: 1px; | |
| stroke: #000; | |
| } | |
| </style> | |
| <svg width="960" height="500"></svg> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| <script src="https://d3js.org/d3-array.v1.min.js"></script> | |
| <script src="https://d3js.org/d3-polygon.v1.min.js"></script> | |
| <script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script> | |
| <script src="https://npmcdn.com/earcut@2.1.1/dist/earcut.min.js"></script> | |
| <script> | |
| // Copyright 2016, Brooks Mershon and Joy Patel. | |
| !function(t,r){"object"==typeof exports&&"undefined"!=typeof module?r(exports,require("d3-polygon"),require("d3-array"),require("earcut")):"function"==typeof define&&define.amd?define(["exports","d3-polygon","d3-array","earcut"],r):r(t.scissors=t.scissors||{},t.d3,t.d3,t.earcut)}(this,function(t,r,n,e){"use strict";function o(t,r){var n,e=0;if(t.length!=r.length)throw new Error("Invalid dimensions for dot product.");for(n=0;n<t.length;n++)e+=t[n]*r[n];return e}function a(t){return Math.sqrt(o(t,t))}function u(t,r){return[t*r[0],t*r[1]]}function s(t){return u(1/a(t),t)}function i(t,r,n){var e=s([r[0]-t[0],r[1]-t[1]]),u=s([n[0]-t[0],n[1]-t[1]]);return a(e)*a(u)==0?0:Math.acos(o(e,u))}function c(t,r,n){var e,o=[];for(e=0;e<t.length;e++)o[e]=n(t[e],r[e]);return o}function f(t,r){return c(t,r,function(t,r){return t-r})}function l(t,r,n){var e,o,a,u;return e=s([r[0]-t[0],r[1]-t[1]]),o=s([n[0]-t[0],n[1]-t[1]]),a=e[0]*o[1]-e[1]*o[0],u=[0,0,0],u[0]=u[1]=0,u[2]=a,u}function h(t){return 180*t/Math.PI}function p(t,r){return c(t,r,function(t,r){return t+r})}function g(t,r){return u(o(t,r)/o(r,r),r)}function v(t,r,n){return r+n>t&&t>r-n}function m(t,r,n,e){var o,a,s,i=f(r,t),c=f(e,n),l=f(n,t),h=0;return o=i[0]*-c[1]- -c[0]*i[1],a=(l[0]*-c[1]- -c[0]*l[1])/o,s=(i[0]*l[1]-l[0]*i[1])/o,v(a,.5,.5+h)&&v(s,.5,.5+h)?p(t,u(a,i)):null}function y(t){var r=t*Math.PI/180,n=Math.sin(r),e=Math.cos(r);return[[e,-1*n,0],[n,e,0],[0,0,1]]}function d(t){var r,n,e=[[0,0,0],[0,0,0],[0,0,0]];for(r=0;t>r;r++)for(n=0;t>n;n++)e[r][n]=0;for(r=0;t>r;r++)e[r][r]=1;return e}function q(t){var r=t[0],n=t[1],e=d(3);return e[0][2]=r,e[1][2]=n,e}function b(t,r){var n,e=[];for(n=0;n<t[0].length;n++)e[n]=t[r][n];return e}function O(t,r){var n,e=[],a=r.slice();for(n=0;n<3-r.length;n++)a.push(1);for(n=0;n<t.length;n++)e[n]=o(b(t,n),a);return e}function j(t,r){var n,e=[];for(n=0;n<t.length;n++)e[n]=t[n][r];return e}function M(t,r){var n,e,a=[[0,0,0],[0,0,0],[0,0,0]];if(t[0].length!=r.length)throw new Error("invalid dimensions");for(n=0;n<t.length;n++)for(e=0;e<r[0].length;e++)a[n][e]=o(b(t,n),j(r,e));return a}function E(){this.transforms=[],this._matrix=d(3),this._origin=null}function C(){return r.polygonCentroid(this)}function _(t){return r.polygonContains(this,t)}function x(t){var r,n,e;for(r=0,e=this.length;e>r;r++)n=this[r],this[r]=[n[0]+t[0],n[1]+t[1]];return this}function w(t,r){var n,e,o=y(t);for(r&&this.translate([-r[0],-r[1]]),n=0,e=this.length;e>n;n++)this[n]=O(o,this[n]);return r&&this.translate(r),this}function I(t){var r,n;for(r=0,n=this.length;n>r;r++)this[r]=u(t,this[r]);return this}function P(){return this._origin?this._origin:(this._origin=this.accumulate(),this._origin)}function A(){var t,r,n=this.clone(),e=this.transforms.length,o=d(3);for(t=e-1;t>=0;t--)r=this.transforms[t],r.rotate&&r.pivot?(n.rotate(r.rotate,r.pivot),o=M(q(u(-1,r.pivot)),o),o=M(y(r.rotate),o),o=M(q(r.pivot),o)):r.translate&&(n.translate(r.translate),o=M(q(r.translate),o));return n._matrix=o,n}function J(){var t=JSON.parse(JSON.stringify(this.slice(0)));return Object.assign(N(t),this)}function N(t){var r=new E;return r.push.apply(r,t),r}function S(t){var n,e,o,a,s,c,l,v,y,d,q,b,O,j,M,E,C,_,x,w,I=0,P=-(1/0);if(0==r.polygonArea(t))return[];for(w=0;3>w;w++)x=0,x=i(t[w%3],t[(w+1)%3],t[(w+2)%3]),x>P&&(P=x,I=w);return n=t[I],e=t[(I+1)%3],o=t[(I+2)%3],d=f(o,e),q=f(n,e),y=p(e,g(q,d)),s=p(n,u(.5,f(y,n))),b=f(e,y),O=f(o,y),j=f(s,y),l=p(y,p(b,j)),v=p(y,p(O,j)),a=m(s,l,n,e),c=m(s,v,n,o),M=N([e,o,c,a]),E=N([a,l,e]),C=N([c,o,v]),E.transforms.push({rotate:h(Math.PI),pivot:a}),C.transforms.push({rotate:h(-Math.PI),pivot:c}),_=[M,E,C],_.rectangle=[e,o,v,l],_}function k(t,r,n){for(var e,o,a=n.length,u=[],s=[],i=[],c=n[a-1],f=[],l=-1,h=[];++l<a;)if(e=c,c=n[l],o=t!==e&&r!==e||i.length&&Object.is(i[0],e)?t!==c&&r!==c||i.length&&!Object.is(i[0],c)?m(t,r,e,c):c:e){if(2==i.length)break;i.push(o),f.push(l)}if(2==i.length&&!Object.is(i[0],i[1])){for(u.push(i[0]),l=f[0];l!=f[1];)Object.is(i[0],n[l])||Object.is(i[1],n[l])||u.push(n[l]),l=(l+1)%a;for(u.push(i[1]),s.push(i[0]),s.push(i[1]),l=f[1];l!=f[0];)Object.is(i[0],n[l])||Object.is(i[1],n[l])||s.push(n[l]),l=(l+1)%a;h.push(N(u),N(s)),h.forEach(function(t){[].push.apply(t.transforms,n.transforms)})}return h}function z(t,r,n){var e,o,a,u=n.length,s=[],i=[];for(a=0;u>a;a++)e=n[a],o=k(t,r,e),2==o.length&&([].push.apply(i,o),s.push(a));return i=i.concat(n.filter(function(t,r){return-1===s.indexOf(r)}))}function B(t,n){var e,o,i,c,l,h,g,v,y,d,q,b,O,j,M,E,C,_,x,w,I,P,A,J,N,S,k=t.rectangle,B=1/0,F=[];for(b=Math.abs(r.polygonArea(k)),O=b/n,o=k[0],h=k[1],g=k[2],l=k[3],B=a(f(o,h)),n>B&&(n=O,O=b/n),e=p(o,u(O,s(f(l,o)))),i=p(o,u(n,s(f(h,o)))),c=p(e,f(i,o));B>2*n;){for(P=[],A=[],J=[],N=[],E=p(e,u(.5,f(h,o))),C=p(o,u(.5,f(h,o))),B=a(f(C,h)),_=[e,o,C,E],x=z(E,p(C,f(i,c)),t),I=f(l,o),w=f(o,C),x.forEach(function(t,n){S=r.polygonCentroid(t),t.forEach(function(t,r){Object.is(l,t)?(P.push(n),A.push(r)):Object.is(h,t)&&(J.push(n),N.push(r))}),r.polygonContains(_,S)?t.translate(I).transforms.push({translate:u(-1,I)}):t.translate(w).transforms.push({translate:u(-1,w)})}),l=x[P[0]][A[0]],h=x[J[0]][N[0]],j=1,M=N.length;M>j;j++)h=x[J[j]][N[j]]=x[J[j-1]][N[j-1]];t=x}return F=t,g=p(h,f(l,o)),v=m(e,h,l,g),y=m(e,h,c,i),q=[y,i,h],d=[e,h,g,c],F=z(e,h,F),F=z(c,p(i,u(1,f(i,c))),F),F.forEach(function(t){var n,o;n=r.polygonCentroid(t),r.polygonContains(q,n)?(o=f(e,y),t.translate(o).transforms.push({translate:u(-1,o)})):r.polygonContains(d,n)&&(o=f(e,v),t.translate(o).transforms.push({translate:u(-1,o)}))}),F.rectangle=D([o,i,c,e])?[o,i,c,e]:[i,c,e,o],F}function D(t){var r=t[3],n=t[0],e=t[1];return a(f(n,e))>a(f(n,r))}function F(t,r,n,e){var o,a,s=f(r,t),i=f(e,n),c=f(n,t);return o=s[0]*-i[1]- -i[0]*s[1],0===o?[ut,ut]:(a=(c[0]*-i[1]- -i[0]*c[1])/o,p(t,u(a,s)))}function G(t,r){return l(t,r[0],r[1])[2]<0}function H(t){var r=t.centroid();return G(r,t.slice(0,2))||t.reverse(),t}function K(t){var r;return t.rotate&&t.pivot?r={rotate:-t.rotate,pivot:t.pivot}:t.translate&&(r={translate:u(-1,t.translate)}),r}function L(t,r){var n,e,o,a,u,s,i,c,f,l,h,p,g,v,m;for(r=H(r.clone()).reverse(),H(t),e=t.slice(0),a=0,s=r.length;s>a;a++)for(i=(a+1)%s,c=[r[a],r[i]],n=e.slice(0),e=[],l=n[n.length-1],u=0;u<n.length;u++)f=n[u],h=!G(f,c),p=!G(l,c),h?(p||(g=F(l,f,r[a],r[i]),e.push(g)),e.push(f)):p&&(g=F(l,f,r[a],r[i]),e.push(g)),l=f;return o=N(e),m=t.transforms.slice(0),o.target=r.transforms.slice(0),v=r.transforms.slice(0).reverse(0).map(K),m=m.concat(v),o.transforms=m,o}function Q(t,r){var n,e,o,a=[];for(e=0;e<t.length;e++)for(o=0;o<r.length;o++)n=L(H(t[e]),H(r[o])),0!=n.length&&a.push(n);return a}function R(t){var r,n,e,o,a,s,c,p,g,v,m,y,d,q=[];if(t.length<2)return q=t.slice(),q.square=q[0].rectangle,q;for(r=t[0],q.push(r),g=1,v=t.length;v>g;g++)c=r.rectangle[3],n=t[g],p=n.rectangle[0],m=f(c,p),n.rectangle=N(n.rectangle).translate(m),y=l(c,r.rectangle[2],n.rectangle[1])[2]>0?1:-1,d=-1*y*h(i(c,r.rectangle[2],n.rectangle[1])),n.forEach(function(t){t.translate(m),t.transforms.push({translate:u(-1,m)}),t.rotate(d,c),t.transforms.push({rotate:-d,pivot:c})}),n.rectangle.rotate(d,c),q.push(n),r=n;return e=q[v-1].rectangle[3],o=q[0].rectangle[0],a=q[0].rectangle[1],s=q[v-1].rectangle[2],q.square=[o,a,s,e],q}function T(t,r){var n,e,o,s,c,p,g,v,m,y,d,q,b,O,j,M,E=0,C=0,_=1/0;for(t=t.map(function(t){return N(t)}),r=r.map(function(t){return N(t)}),j=X(t),M=Math.sqrt(j),O=Math.sqrt(j/X(r)),Y(O,r),o=R(t.map(function(t){return U(M,t)})),s=R(r.map(function(t){return U(M,t)})),n=V(o),e=V(s),n.square=o.square,e.square=s.square,c=N(n.square),p=N(e.square),g=c.centroid(),v=p.centroid(),m=[g[0]-v[0],g[1]-v[1]],p=p.clone().translate(m),E=0,C=0;4>E;E++)b=a(f(c[0],p[E])),_>b&&(_=b,C=E);return q=l(g,p[C],c[0])[2]>0?1:-1,d=q*h(i(g,p[C],c[0])),e.forEach(function(t){t.translate(m),t.transforms.push({translate:u(-1,m)}),t.rotate(d,g),t.transforms.push({rotate:-d,pivot:g})}),y=Q(n,e),y=y.map(function(t){var r=t.clone();return r.transforms=t.target,r=r.origin(),r.transforms=t.transforms,r}),y.scale=O,y}function U(t,r){return B(S(r),t)}function V(t){var r=[];return t.forEach(function(t){[].push.apply(r,t)}),r}function W(t){var r;return r=t.map(function(t){return N(t).centroid()}),1==r.length?r[0]:2==r.length?[(r[0][0]+r[1][0])/2,(r[0][1]+r[1][1])/2]:N(r).centroid()}function X(t){return n.sum(t,function(t){return r.polygonArea(t)})}function Y(t,r){var n=W(r);return r.forEach(function(r){r.translate(u(-1,n)),r.scale(t),r.translate(n)}),r}function Z(t,r){var n=T(t,r);return{source:function(){return n.map(function(t){return t.origin().slice(0)})},subject:function(){return n.map(function(t){return t.slice(0)})},scale:function(){return n.scale}}}function $(t){var r,n;return r=e(tt(t)),n=nt(rt(r,t))}function tt(t){var r,n,e=[];for(r=0,n=t.length;n>r;r++)e.push(t[r][0],t[r][1]);return e}function rt(t,r){return t.map(function(t){return r[t]})}function nt(t){var r,n,e=[];for(r=0,n=t.length;n>r;r+=3)e.push([t[r],t[r+1],t[r+2]]);return e}function et(t,r){return Z(ot($(t)),ot($(r)))}function ot(t){return t.map(function(t){return t.reverse()})}function at(t,r){return Z(t,r)}e="default"in e?e["default"]:e,E.prototype=Object.create(Array.prototype),E.prototype.constructor=E,E.prototype.centroid=C,E.prototype.containsPoint=_,E.prototype.translate=x,E.prototype.rotate=w,E.prototype.scale=I,E.prototype.accumulate=A,E.prototype.origin=P,E.prototype.clone=J;var ut=[1e12,1e12];t.equidecompose=et,t.equidecomposeMesh=at}); | |
| var svg = d3.select("svg"), | |
| width = +svg.attr("width"), | |
| height = +svg.attr("height"); | |
| n = 4, m = 3; | |
| r = 180; | |
| var color = function(i) { | |
| var n = d3.schemeSet3.length; | |
| return d3.schemeSet3[i % n]; | |
| } | |
| var P = d3.range(m).map(function(d, i) { | |
| var slice = 2 * Math.PI / m; | |
| return [width * 3/4 + (r * Math.cos(i * slice)), | |
| height / 2 + (r * Math.sin(i * slice))]; | |
| }); | |
| var Q = d3.range(n).map(function(d, i) { | |
| var slice = 2 * Math.PI / n; | |
| return [width / 4 + (r * Math.cos(i * slice)), | |
| height / 2 + (r * Math.sin(i * slice))]; | |
| }); | |
| var decomposition = scissors.equidecompose(P, Q); | |
| var subject = decomposition.subject(); | |
| var source = decomposition.source(); | |
| svg.selectAll(".source") | |
| .data(source.map(closedLine), String) | |
| .enter().append("path") | |
| .attr("class", "source") | |
| .attr("fill", "none") | |
| .attr("d", String) | |
| .attr("fill", function(d, i) { return color(i) }); | |
| svg.selectAll(".subject") | |
| .data(subject.map(closedLine), String) | |
| .enter().append("path") | |
| .attr("class", "subject") | |
| .attr("fill", "none") | |
| .attr("d", String) | |
| .attr("fill", function(d, i) { return color(i) }); | |
| function closedLine(points) { | |
| return "M" + points.join("L") + "Z"; | |
| } | |
| </script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment