The Sutherland-Hodgman clipping algorithm is used here to compute the intersection of two Delaunay triangulations with one another. Sutherland-Hodgman implementation by Joy Patel.
This algorithm can be used to intersect the decomposition of one triangle with a decomposition coming from another triangle of equal area.
For a decomposition of two triangles of equal area that uses Sutherland-Hodgman clipping, see this example.
See d3-equidecompose.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| path { | |
| fill: #fafafa; | |
| stroke: #727272; | |
| } | |
| .A { | |
| fill: #EB9394; | |
| fill-opacity: 0.5; | |
| } | |
| .B { | |
| fill: #8FBBDA; | |
| fill-opacity: 0.5; | |
| } | |
| .intersection { | |
| fill: #96D096; | |
| } | |
| </style> | |
| <body> | |
| <script src="https://d3js.org/d3-polygon.v0.2.min.js"></script> | |
| <script src="partials.js"></script> | |
| <script src="https://d3js.org/d3.v3.min.js"></script> | |
| <script> | |
| // Copyright 2016, Brooks Mershon and Joy Patel (minified partial build of d3-equidecompose) | |
| !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,e){var a=[n[0]-t[0],n[1]-t[1]],i=[e[0]-t[0],e[1]-t[1]];return o(a)*o(i)==0?0:Math.acos(Math.max(Math.min(1,r(a,i)/(o(a)*o(i))),-1))}function a(t,n,r){return n+r>t&&t>n-r}function i(t,n,r){var o,e=[];for(o=0;o<t.length;o++)e[o]=r(t[o],n[o]);return e}function s(t,n){return i(t,n,function(t,n){return t+n})}function u(t,n){return i(t,n,function(t,n){return t-n})}function f(t,n){return[t*n[0],t*n[1]]}function c(t){return f(1/o(t),t)}function l(t,n,r,o){var e,i,c,l=u(n,t),h=u(o,r),p=u(r,t),g=0;return e=l[0]*-h[1]- -h[0]*l[1],i=(p[0]*-h[1]- -h[0]*p[1])/e,c=(l[0]*p[1]-p[0]*l[1])/e,a(i,.5,.5+g)&&a(c,.5,.5+g)?s(t,f(i,l)):null}function h(t,n){return f(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 M(t,n){var r,o=[];for(r=0;r<t.length;r++)o[r]=t[r][n];return o}function b(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),M(n,e));return a}function O(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 P(){var t,n,r=this.clone(),o=this.transforms.length,e=v(3);for(t=o-1;t>=0;t--)n=this.transforms[t],n.rotate&&n.pivot?(r.rotate(n.rotate,n.pivot),e=b(y(f(-1,n.pivot)),e),e=b(g(n.rotate),e),e=b(y(n.pivot),e)):n.translate&&(r.translate(n.translate),e=b(y(n.translate),e));return r._matrix=e,r}function x(){return I(JSON.parse(JSON.stringify(this.slice())))}function I(t){var n=new O;return n.push.apply(n,t),n}function w(t){var r,o,a,i,c,g,v,y,m,d,M,b,O,j,C,_,q,E,P,x,w=0,A=-(1/0);if(0==n.polygonArea(t))return[];for(x=0;3>x;x++)P=0,P=e(t[x%3],t[(x+1)%3],t[(x+2)%3]),P>A&&(A=P,w=x);return r=t[w],o=t[(w+1)%3],a=t[(w+2)%3],d=u(a,o),M=u(r,o),m=s(o,h(M,d)),c=s(r,f(.5,u(m,r))),b=u(o,m),O=u(a,m),j=u(c,m),v=s(m,s(b,j)),y=s(m,s(O,j)),i=l(c,v,r,o),g=l(c,y,r,a),C=I([o,a,g,i]),_=I([i,v,o]),q=I([g,a,y]),_.transforms.push({rotate:p(Math.PI),pivot:i}),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(I(i),I(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!s.includes(n)}))}function J(t){var r,e,a,i,h,p,g,v,y,m,d,M,b,O,j,C,_,q,E,P,x,I,w=t.rectangle,A=1/0,J=[],N=[],k=[],R=[],T=[];for(M=Math.abs(n.polygonArea(w)),b=Math.sqrt(M),e=w[0],h=w[3],p=w[1],g=w[2],r=s(e,f(b,c(u(h,e)))),a=s(e,f(b,c(u(p,e)))),i=s(r,u(a,e)),A=o(u(e,p));A>2*b;){for(C=s(r,f(.5,u(p,e))),_=s(e,f(.5,u(p,e))),A=o(u(_,p)),q=[r,e,_,C],E=S(C,s(_,u(a,i)),t),x=u(h,e),P=u(e,_),E.forEach(function(t,r){I=n.polygonCentroid(t),t.forEach(function(t,n){Object.is(h,t)?(N.push(r),k.push(n)):Object.is(p,t)&&(R.push(r),T.push(n))}),n.polygonContains(q,I)?t.translate(x).transforms.push({translate:f(-1,x)}):t.translate(P).transforms.push({translate:f(-1,P)})}),h=E[N[0]][k[0]],p=E[R[0]][T[0]],O=1,j=T.length;j>O;O++)p=E[R[O]][T[O]]=E[R[O-1]][T[O-1]];t=E}return J=t,g=s(p,u(h,e)),v=l(r,p,h,g),y=l(r,p,i,a),d=[y,a,p],m=[r,p,g,i],J=S(r,p,J),J=S(i,s(a,f(1,u(a,i))),J),J.forEach(function(t){var o,e;o=n.polygonCentroid(t),n.polygonContains(d,o)?(e=u(r,y),t.translate(e).transforms.push({translate:f(-1,e)})):n.polygonContains(m,o)&&(e=u(r,v),t.translate(e).transforms.push({translate:f(-1,e)}))}),J.square=[r,e,a,i],J}function N(t,n,r,o){var e,a,i,c=u(n,t),l=u(o,r),h=u(t,r);return e=l[0]*-c[1]- -c[0]*l[1],a=(h[0]*-c[1]- -c[0]*h[1])/e,i=(l[0]*h[1]-h[0]*l[1])/e,i>=0&&1>=i?s(r,f(a,l)):[]}function k(t,n){var r=u(t,n[0]),o=u(n[1],n[0]),e=r[0]*o[1]-o[0]*r[1];return e>=0}function R(t){var n;return t.rotate&&t.pivot?n={rotate:-t.rotate,pivot:t.pivot}:t.translate&&(n={translate:f(-1,t.translate)}),n}function T(t,n){var r,o,e,a,i,s,u,f,c,l,h,p,g,v;for(r=I(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=!k(h,f),g=!k(l,f),p?(g||(v=N(h,l,r[i],r[u]),v!=[]&&o.push(v)),o.push(h)):g&&(v=N(h,l,r[i],r[u]),v.length&&o.push(v)),l=h;return e=I(o),a=t.transforms.slice(),e.target=n.transforms.slice(0),a=a.concat(n.transforms.slice(0).reverse().map(R)),e.transforms=a,e}function z(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 B(t,n){var r,o,e,a=[];for(o=0;o<t.length;o++)for(e=0;e<n.length;e++)r=T(z(t[o]),z(n[e])),null!=r&&0!=r.length&&0!=r[0].length&&a.push(r);return a}function D(t,r){var o,e,a,i,s,u,f;return o=J(w(t)),e=J(w(r)),a=I(o.square),i=I(e.square),u=n.polygonCentroid(a),f=n.polygonCentroid(i),e.forEach(function(t){t.translate([u[0]-f[0],u[1]-f[1]]),t.transforms.push({translate:[-(u[0]-f[0]),-(u[1]-f[1])],type:"alignment"}),t.rotate(F(a,i),u),t.transforms.push({rotate:-F(a,i),pivot:u,type:"alignment"})}),s=B(o,e),s=s.map(function(t){var n=t.clone();return n.transforms=t.target,n=n.origin(),n.transforms=t.transforms,n})}function F(t,n){var r,o;return r=t[0],o=s(n[0],u(t.centroid(),n.centroid())),180/Math.PI*e(t.centroid(),r,o)}O.prototype=Object.create(Array.prototype),O.prototype.constructor=O,O.prototype.centroid=j,O.prototype.containsPoint=C,O.prototype.translate=_,O.prototype.rotate=q,O.prototype.accumulate=P,O.prototype.origin=E,O.prototype.clone=x,t.angle=e,t.intersect=l,t.triangle2Rectangle=w,t.cutPolygon=A,t.cutCollection=S,t.rectangle2Square=J,t.triangle2Triangle=D,t.clipCollection=B,t.polygon=I}); | |
| var width = 960, | |
| height = 500, | |
| N = 25, | |
| triangles, | |
| polgyons; | |
| var vertices = d3.range(N).map(function(d) { | |
| return [Math.random() * width, Math.random() * height]; | |
| }); | |
| var svg = d3.select("body").append("svg") | |
| .attr("width", width) | |
| .attr("height", height) | |
| // geometry | |
| A = d3.geom.delaunay(vertices.slice(0, 10)).map((d) => partials.polygon(d)); // array of triangles | |
| B = d3.geom.delaunay(vertices.slice(10, N)).map((d) => partials.polygon(d)); // another array of triangles | |
| C = partials.clipCollection(A, B); | |
| // rendering | |
| var alpha = svg.selectAll(".A") | |
| .data(A.map(function(d) { return "M" + d.join("L") + "Z"; }), String) | |
| .enter().append("path") | |
| .attr("class", "A") | |
| .attr("d", String); | |
| var beta = svg.selectAll(".B") | |
| .data(B.map(function(d) { return "M" + d.join("L") + "Z"; }), String) | |
| .enter().append("path") | |
| .attr("class", "B") | |
| .attr("d", String); | |
| var intersection = svg.selectAll(".C") | |
| .data(C.map(function(d) { return "M" + d.join("L") + "Z"; }), String) | |
| .enter().append("path") | |
| .attr("class", "intersection") | |
| .attr("d", String); | |
| </script> |
