Equidecomposition II

Scissors congruence between two triangles of equal area.

This scissors module makes use of Mapbox's Earcut to triangulate polygons before carrying out an equidecomposition algorithm.

Equidecomposition involves clipping polygons against one another using Sutherland-Hodgeman clipping after collections of polygons taken from a source and subject have been cut and aligned to form squares of equal area.

Done naively, it is this clipping stage which gives rise to numerical instability as degeneracies and floating point arithmetic plague efforts to make the equidecomposition algorithm robust.

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

.source, .subject {
  stroke-width: 1px;
  stroke: #aaa;
}

</style>
<svg width="960" height="500"></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://npmcdn.com/earcut@2.1.1/dist/earcut.min.js"></script>
<script src="https://d3js.org/d3.v4.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 = 6;
    r = 180;

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);

svg.selectAll(".subject")
    .data(subject.map(closedLine), String)  
  .enter().append("path")
    .attr("class", "subject")
    .attr("fill", "none")
    .attr("d", String);

d3.selectAll("path").transition()
    .delay(function(d, i) { return (i % subject.length) * 1000; })
    .on("start", function repeat() {
        d3.active(this)
            .style("fill", "rgba(240,0,0,1)")
          .transition().duration(1000)
            .style("fill", "#fff")
          .transition().delay(subject.length * 1000)
          .on("start", repeat);
      });

function closedLine(points) {
  return "M" + points.join("L") + "Z";
}

</script>

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

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

https://npmcdn.com/earcut@2.1.1/dist/earcut.min.js

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