Scissor congruence between two triangles of equal area.
See scissors (previously d3-equidecompose).
Last active
August 20, 2016 20:57
-
-
Save bmershon/42759de90c9a7fb22963df19a4f4d613 to your computer and use it in GitHub Desktop.
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
| license: gpl-3.0 | |
| height: 500 | |
| border: no |
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> | |
| .Q { | |
| fill: none; | |
| stroke-dasharray: 5, 5; | |
| stroke-width: 2px; | |
| stroke: #000; | |
| } | |
| .figure { | |
| pointer-events: none; | |
| stroke-width: 1px; | |
| stroke: #000; | |
| fill: none; | |
| } | |
| </style> | |
| <svg width="960" height="500">g</svg> | |
| <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.v4.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"),require("d3-array")):"function"==typeof define&&define.amd?define(["exports","d3-polygon","d3-array"],n):n(t.scissors=t.scissors||{},t.d3,t.d3)}(this,function(t,n,r){"use strict";function e(t,n){var r,e=0;if(t.length!=n.length)throw new Error("Invalid dimensions for dot product.");for(r=0;r<t.length;r++)e+=t[r]*n[r];return e}function o(t){return Math.sqrt(e(t,t))}function a(t,n){return[t*n[0],t*n[1]]}function s(t){return a(1/o(t),t)}function u(t,n,r){var a=s([n[0]-t[0],n[1]-t[1]]),u=s([r[0]-t[0],r[1]-t[1]]);return o(a)*o(u)==0?0:Math.acos(e(a,u))}function i(t,n,r){var e,o=[];for(e=0;e<t.length;e++)o[e]=r(t[e],n[e]);return o}function c(t,n){return i(t,n,function(t,n){return t-n})}function f(t,n,r){var e,o,a,u;return e=s([n[0]-t[0],n[1]-t[1]]),o=s([r[0]-t[0],r[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 l(t){return 180*t/Math.PI}function h(t,n){return i(t,n,function(t,n){return t+n})}function p(t,n){return a(e(t,n)/e(n,n),n)}function g(t,n,r){return n+r>t&&t>n-r}function v(t,n,r,e){var o,s,u,i=c(n,t),f=c(e,r),l=c(r,t),p=0;return o=i[0]*-f[1]- -f[0]*i[1],s=(l[0]*-f[1]- -f[0]*l[1])/o,u=(i[0]*l[1]-l[0]*i[1])/o,g(s,.5,.5+p)&&g(u,.5,.5+p)?h(t,a(s,i)):null}function m(t){var n=t*Math.PI/180,r=Math.sin(n),e=Math.cos(n);return[[e,-1*r,0],[r,e,0],[0,0,1]]}function y(t){var n,r,e=[[0,0,0],[0,0,0],[0,0,0]];for(n=0;t>n;n++)for(r=0;t>r;r++)e[n][r]=0;for(n=0;t>n;n++)e[n][n]=1;return e}function d(t){var n=t[0],r=t[1],e=y(3);return e[0][2]=n,e[1][2]=r,e}function q(t,n){var r,e=[];for(r=0;r<t[0].length;r++)e[r]=t[n][r];return e}function b(t,n){var r,o=[],a=n.slice();for(r=0;r<3-n.length;r++)a.push(1);for(r=0;r<t.length;r++)o[r]=e(q(t,r),a);return o}function O(t,n){var r,e=[];for(r=0;r<t.length;r++)e[r]=t[r][n];return e}function j(t,n){var r,o,a=[[0,0,0],[0,0,0],[0,0,0]];if(t[0].length!=n.length)throw new Error("invalid dimensions");for(r=0;r<t.length;r++)for(o=0;o<n[0].length;o++)a[r][o]=e(q(t,r),O(n,o));return a}function M(){this.transforms=[],this._matrix=y(3),this._origin=null}function E(){return n.polygonCentroid(this)}function C(t){return n.polygonContains(this,t)}function _(t){var n,r,e;for(n=0,e=this.length;e>n;n++)r=this[n],this[n]=[r[0]+t[0],r[1]+t[1]];return this}function x(t,n){var r,e,o=m(t);for(n&&this.translate([-n[0],-n[1]]),r=0,e=this.length;e>r;r++)this[r]=b(o,this[r]);return n&&this.translate(n),this}function w(t){var n,r;for(n=0,r=this.length;r>n;n++)this[n]=a(t,this[n]);return this}function I(){return this._origin?this._origin:(this._origin=this.accumulate(),this._origin)}function P(){var t,n,r=this.clone(),e=this.transforms.length,o=y(3);for(t=e-1;t>=0;t--)n=this.transforms[t],n.rotate&&n.pivot?(r.rotate(n.rotate,n.pivot),o=j(d(a(-1,n.pivot)),o),o=j(m(n.rotate),o),o=j(d(n.pivot),o)):n.translate&&(r.translate(n.translate),o=j(d(n.translate),o));return r._matrix=o,r}function A(){var t=JSON.parse(JSON.stringify(this.slice(0)));return Object.assign(J(t),this)}function J(t){var n=new M;return n.push.apply(n,t),n}function N(t){var r,e,o,s,i,f,g,m,y,d,q,b,O,j,M,E,C,_,x,w,I=0,P=-(1/0);if(0==n.polygonArea(t))return[];for(w=0;3>w;w++)x=0,x=u(t[w%3],t[(w+1)%3],t[(w+2)%3]),x>P&&(P=x,I=w);return r=t[I],e=t[(I+1)%3],o=t[(I+2)%3],d=c(o,e),q=c(r,e),y=h(e,p(q,d)),i=h(r,a(.5,c(y,r))),b=c(e,y),O=c(o,y),j=c(i,y),g=h(y,h(b,j)),m=h(y,h(O,j)),s=v(i,g,r,e),f=v(i,m,r,o),M=J([e,o,f,s]),E=J([s,g,e]),C=J([f,o,m]),E.transforms.push({rotate:l(Math.PI),pivot:s}),C.transforms.push({rotate:l(-Math.PI),pivot:f}),_=[M,E,C],_.rectangle=[e,o,m,g],_}function S(t,n,r){for(var e,o,a=r.length,s=[],u=[],i=[],c=r[a-1],f=[],l=-1,h=[];++l<a;)if(e=c,c=r[l],o=t!==e&&n!==e||i.length&&Object.is(i[0],e)?t!==c&&n!==c||i.length&&!Object.is(i[0],c)?v(t,n,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(s.push(i[0]),l=f[0];l!=f[1];)Object.is(i[0],r[l])||Object.is(i[1],r[l])||s.push(r[l]),l=(l+1)%a;for(s.push(i[1]),u.push(i[0]),u.push(i[1]),l=f[1];l!=f[0];)Object.is(i[0],r[l])||Object.is(i[1],r[l])||u.push(r[l]),l=(l+1)%a;h.push(J(s),J(u)),h.forEach(function(t){[].push.apply(t.transforms,r.transforms)})}return h}function k(t,n,r){var e,o,a,s=r.length,u=[],i=[];for(a=0;s>a;a++)e=r[a],o=S(t,n,e),2==o.length&&([].push.apply(i,o),u.push(a));return i=i.concat(r.filter(function(t,n){return-1===u.indexOf(n)}))}function T(t,r){var e,u,i,f,l,p,g,m,y,d,q,b,O,j,M,E,C,_,x,w,I,P,A,J,N,S,T=t.rectangle,B=1/0,D=[];for(b=Math.abs(n.polygonArea(T)),O=b/r,u=T[0],p=T[1],g=T[2],l=T[3],B=o(c(u,p)),r>B&&(r=O,O=b/r),e=h(u,a(O,s(c(l,u)))),i=h(u,a(r,s(c(p,u)))),f=h(e,c(i,u));B>2*r;){for(P=[],A=[],J=[],N=[],E=h(e,a(.5,c(p,u))),C=h(u,a(.5,c(p,u))),B=o(c(C,p)),_=[e,u,C,E],x=k(E,h(C,c(i,f)),t),I=c(l,u),w=c(u,C),x.forEach(function(t,r){S=n.polygonCentroid(t),t.forEach(function(t,n){Object.is(l,t)?(P.push(r),A.push(n)):Object.is(p,t)&&(J.push(r),N.push(n))}),n.polygonContains(_,S)?t.translate(I).transforms.push({translate:a(-1,I)}):t.translate(w).transforms.push({translate:a(-1,w)})}),l=x[P[0]][A[0]],p=x[J[0]][N[0]],j=1,M=N.length;M>j;j++)p=x[J[j]][N[j]]=x[J[j-1]][N[j-1]];t=x}return D=t,g=h(p,c(l,u)),m=v(e,p,l,g),y=v(e,p,f,i),q=[y,i,p],d=[e,p,g,f],D=k(e,p,D),D=k(f,h(i,a(1,c(i,f))),D),D.forEach(function(t){var r,o;r=n.polygonCentroid(t),n.polygonContains(q,r)?(o=c(e,y),t.translate(o).transforms.push({translate:a(-1,o)})):n.polygonContains(d,r)&&(o=c(e,m),t.translate(o).transforms.push({translate:a(-1,o)}))}),D.rectangle=z([u,i,f,e])?[u,i,f,e]:[i,f,e,u],D}function z(t){var n=t[3],r=t[0],e=t[1];return o(c(r,e))>o(c(r,n))}function B(t,n,r,e){var o,s,u=c(n,t),i=c(e,r),f=c(r,t);return o=u[0]*-i[1]- -i[0]*u[1],0===o?[1/0,1/0]:(s=(f[0]*-i[1]- -i[0]*f[1])/o,h(t,a(s,u)))}function D(t,n){return f(t,n[0],n[1])[2]<0}function F(t){var n;return t.rotate&&t.pivot?n={rotate:-t.rotate,pivot:t.pivot}:t.translate&&(n={translate:a(-1,t.translate)}),n}function G(t,n){var r,e,o,a,s,u,i,c,f,l,h,p,g,v,m;for(n=n.clone().reverse(),e=t.slice(0),a=0,u=n.length;u>a;a++)for(i=(a+1)%u,c=[n[a],n[i]],r=e.slice(0),e=[],l=r[r.length-1],s=0;s<r.length;s++)f=r[s],h=!D(f,c),p=!D(l,c),h?(p||(g=B(l,f,n[a],n[i]),e.push(g)),e.push(f)):p&&(g=B(l,f,n[a],n[i]),e.push(g)),l=f;return o=J(e),m=t.transforms.slice(0),o.target=n.transforms.slice(0),v=n.transforms.slice(0).reverse(0).map(F),m=m.concat(v),o.transforms=m,o}function H(t){var n=t.centroid();return D(n,t.slice(0,2))||t.reverse(),t}function K(t,n){var r,e,o,a=[];for(e=0;e<t.length;e++)for(o=0;o<n.length;o++)r=G(H(t[e]),H(n[o])),0!=r.length&&a.push(r);return a}function L(t){var n,r,e,o,s,i,h,p,g,v,m,y,d,q=[];if(t.length<2)return q=t.slice(),q.square=q[0].rectangle,q;for(n=t[0],q.push(n),g=1,v=t.length;v>g;g++)h=n.rectangle[3],r=t[g],p=r.rectangle[0],m=c(h,p),r.rectangle=J(r.rectangle).translate(m),y=f(h,n.rectangle[2],r.rectangle[1])[2]>0?1:-1,d=-1*y*l(u(h,n.rectangle[2],r.rectangle[1])),r.forEach(function(t){t.translate(m),t.transforms.push({translate:a(-1,m)}),t.rotate(d,h),t.transforms.push({rotate:-d,pivot:h})}),r.rectangle.rotate(d,h),q.push(r),n=r;return e=q[v-1].rectangle[3],o=q[0].rectangle[0],s=q[0].rectangle[1],i=q[v-1].rectangle[2],q.square=[o,s,i,e],q}function Q(t,n){var r,e,s,i,h,p,g,v,m,y,d,q,b,O,j,M,E=0,C=0,_=1/0;for(t=t.map(function(t){return J(t)}),n=n.map(function(t){return J(t)}),j=W(t),M=Math.sqrt(j),O=Math.sqrt(j/W(n)),X(O,n),s=L(t.map(function(t){return R(M,t)})),i=L(n.map(function(t){return R(M,t)})),r=U(s),e=U(i),r.square=s.square,e.square=i.square,h=J(r.square),p=J(e.square),g=h.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=o(c(h[0],p[E])),_>b&&(_=b,C=E);return q=f(g,p[C],h[0])[2]>0?1:-1,d=q*l(u(g,p[C],h[0])),e.forEach(function(t){t.translate(m),t.transforms.push({translate:a(-1,m)}),t.rotate(d,g),t.transforms.push({rotate:-d,pivot:g})}),y=K(r,e),y=y.map(function(t){var n=t.clone();return n.transforms=t.target,n=n.origin(),n.transforms=t.transforms,n}),y.scale=O,y}function R(t,n){return T(N(n),t)}function U(t){var n=[];return t.forEach(function(t){[].push.apply(n,t)}),n}function V(t){var n;return n=t.map(function(t){return J(t).centroid()}),1==n.length?n[0]:2==n.length?[(n[0][0]+n[1][0])/2,(n[0][1]+n[1][1])/2]:J(n).centroid()}function W(t){return r.sum(t,function(t){return n.polygonArea(t)})}function X(t,n){var r=V(n);return n.forEach(function(n){n.translate(a(-1,r)),n.scale(t),n.translate(r)}),n}function Y(t,n){var r=Q(t,n);return{source:function(){return r.map(function(t){return t.origin().slice(0)})},subject:function(){return r.map(function(t){return t.slice(0)})},scale:function(){return r.scale}}}function Z(t){var r,e;return r=null,e=r.triangles(t).filter(function(r){return n.polygonContains(t,n.polygonCentroid(r))})}function $(t,n){return Y(Z(t),Z(n))}function tt(t,n){return Y(t,n)}function nt(t,n){return Y(t,n)}M.prototype=Object.create(Array.prototype),M.prototype.constructor=M,M.prototype.centroid=E,M.prototype.containsPoint=C,M.prototype.translate=_,M.prototype.rotate=x,M.prototype.scale=w,M.prototype.accumulate=P,M.prototype.origin=I,M.prototype.clone=A,t.equidecompose=$,t.equidecomposeMesh=tt,t.equidecomposeTopology=nt}); | |
| var svg = d3.select("svg"), | |
| width = +svg.attr("width"), | |
| height = +svg.attr("height"); | |
| var color = d3.scaleOrdinal(d3.schemeCategory20); | |
| var P = [[500, 150], [890, 420], [700, 160]]; | |
| var Q = [[20, 190], [500, 350], [390, 20]]; | |
| // Source and subject shapes are "collections" of a single triangle each. | |
| var decomposition = scissors.equidecomposeMesh([P], [Q]); | |
| var subject = decomposition.subject(); | |
| var source = decomposition.source(); | |
| svg.selectAll(".Q") | |
| .data([Q].map(closedLine), keyed) | |
| .enter().append("path") | |
| .attr("class", "Q") | |
| .attr("d", String); | |
| svg.selectAll(".subject") | |
| .data(subject.map(closedLine), keyed) | |
| .enter().append("path") | |
| .attr("class", "figure") | |
| .style("fill", function(d, i) { return color(i); }) | |
| .attr("d", String); | |
| svg.selectAll(".source") | |
| .data(source.map(closedLine), keyed) | |
| .enter().append("path") | |
| .attr("class", "figure") | |
| .style("fill", function(d, i) { return color(i); }) | |
| .attr("d", String); | |
| function closedLine(points) { | |
| return "M" + points.join("L") + "Z"; | |
| } | |
| function keyed(a, b) { | |
| return a === b; | |
| } | |
| </script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment