Equidecomposition

Scissor congruence between two triangles of equal area.

See scissors (previously d3-equidecompose).

<!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>

https://d3js.org/d3-array.v1.min.js

https://d3js.org/d3-polygon.v1.min.js

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