Skip to content

Instantly share code, notes, and snippets.

@bmershon

bmershon/.block

Last active May 1, 2017 23:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/cb3570d6ec20be163fdac4f79adf8da4 to your computer and use it in GitHub Desktop.
Save bmershon/cb3570d6ec20be163fdac4f79adf8da4 to your computer and use it in GitHub Desktop.
Download ZIP
Triangle to Rectangle Decomposition
Raw
.block
license: gpl-3.0
border: no
height: 960
Raw
README.md

Debugging Triangle to rectangle decomposition for equidecomposition of two polygons of equal area.

Raw
index.html
<!DOCTYPE html>
<style>
circle {
cursor: move;
fill: #fff;
stroke: #000;
stroke-width: 1px;
}
circle.active {
stroke: #000;
stroke-width: 2px;
}
path.subject {
fill: none;
stroke: rgba(0, 0, 0, 0.3);
stroke-width: 2px;
}
path.canonicalRectangle {
fill: none;
stroke: rgba(0, 0, 240, 1);
stroke-width: 2px;
}
path.canonicalSquare {
fill: none;
fill: rgba(240, 0, 0, 0.1);
stroke-dasharray: 5, 5;
stroke: rgba(240, 0, 0, 1);
stroke-width: 2px;
}
</style>
<svg width="960" height="960"></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://npmcdn.com/earcut@2.1.1/dist/earcut.min.js"></script>
<script src="scissors.debug.js"></script>
<script>
var svg = d3.select("svg"),
width = svg.attr("width"),
height = svg.attr("height");
var color = d3.scaleOrdinal(d3.schemeCategory20);
// Counter-clockwise orientation.
var subject = [[width / 2, height / 5],
[width / 5, 3 * height / 5],
[3 * width / 5, 3 * height / 5]];
var subjectPolygon = svg.append("path")
.datum(subject)
.attr("class", "subject");
// Control points for the subject polygon.
var circle = svg.selectAll("circle")
.data(subject);
var origin = [0, 0];
circle.enter()
.append("circle")
.attr("r", 9)
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; })
.call(d3.drag()
.on("start", dragstarted)
.on("drag", dragged)
.on("end", dragended));
update();
// Redraw polygons in response to control point movement.
function update() {
let sideLength = Math.sqrt(Math.abs(d3.polygonArea(subject))),
canonicalRectangle = scissors.triangle2Rectangle(subject),
canonicalSquare = scissors.rectangle2Rectangle(canonicalRectangle, sideLength);
// Ensure subject polygon has counter-clockwise orientation.
if (!ccw(subject)) subject.reverse();
subjectPolygon.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
svg.selectAll(".canonicalRectangle").remove();
svg.selectAll(".canonicalSquare").remove();
rectangle = svg.selectAll(".canonicalRectangle")
.data(canonicalRectangle); // Key on Object reference.
rectangle.enter().insert("path")
.attr("class", "canonicalRectangle")
.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
square = svg.selectAll(".canonicalSquare")
.data(canonicalSquare); // Key on Object reference.
square.enter().insert("path")
.attr("fill", function(d, i) { return color(i); })
.attr("class", "canonicalSquare")
.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
// Circles drawn on top of all other SVG elements.
d3.selectAll("circle").raise();
}
function dragstarted(d) {
d3.select(this).classed("active", true);
}
function dragged(d) {
d3.select(this)
.attr("cx", d[0] = d3.event.x)
.attr("cy", d[1] = d3.event.y)
update();
}
function dragended(d, i) {
d3.select(this).classed("active", false);
}
function polygonClone(polygon) {
var cloned = [],
i,
n;
for (i = 0, n = polygon.length; i < n; i++) {
cloned.push([polygon[i][0], polygon[i][1]]);
}
return cloned;
}
// Returns true of the given polygon has counter-clockwise orientation.
function ccw(polygon) {
function polygonInside(p, a, b) {
return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
}
return polygonInside(d3.polygonCentroid(polygon), polygon[0], polygon[1]);
}
</script>
Raw
scissors.debug.js
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-polygon'), require('d3-array'), require('earcut')) :
typeof define === 'function' && define.amd ? define(['exports', 'd3-polygon', 'd3-array', 'earcut'], factory) :
(factory((global.scissors = global.scissors || {}),global.d3,global.d3,global.earcut));
}(this, function (exports,d3Polygon,d3Array,earcut) { 'use strict';
earcut = 'default' in earcut ? earcut['default'] : earcut;
// Computes the dot product between 2 vectors.
function dot(a, b) {
var res = 0.0, i;
if (a.length != b.length){
throw new Error("Invalid dimensions for dot product.");
}
for (i = 0; i < a.length; i++) {
res += a[i] * b[i];
}
return res;
}
function length(u) {
return Math.sqrt(dot(u, u));
}
function scale(s, a) {
return [s * a[0], s * a[1]];
}
function normalize(a) {
return scale(1 / length(a), a);
}
// Returns angle in radians between AB and AC, where a, b, c
// are specified in counter-clockwise order.
function angle(a, b, c) {
var u = normalize([b[0] - a[0], b[1] - a[1]]),
v = normalize([c[0] - a[0], c[1] - a[1]]);
if ((length(u) * length(v)) == 0) return 0;
return Math.acos(dot(u, v));
}
// Returns a vector pointing along the z-axis with length ||AB x AC||.
function cross(a, b, c) {
var u, v, z, res;
u = normalize([b[0] - a[0], b[1] - a[1]]),
v = normalize([c[0] - a[0], c[1] - a[1]]),
z = u[0] * v[1] - u[1] * v[0],
res = [0, 0, 0];
res[0] = res[1] = 0;
res[2] = z;
return res;
}
// Tests if point is to the right of an edge (CCW order).
function right(point, edge) {
return cross(point, edge[0], edge[1])[2] < 0;
}
// Sort points in-place to produce counterclockwise winding order.
function ccw(P) {
var C = P.centroid();
if (!right(C, P.slice(0, 2))) P.reverse();
return P;
}
function pairwise(a, b, operation){
var res = [], i;
for(i = 0; i < a.length; i++){
res[i] = operation(a[i], b[i]);
}
return res;
}
function add(a, b) {
return pairwise(a, b, function(x, y){
return x + y;
});
}
function sub(a, b) {
return pairwise(a, b, function(x, y){
return x - y;
});
}
var infinity = [1e12, 1e12];
// Returns point of intersection of AB and CD,
// possibly occuring at infinity.
function infiniteIntersect(a, b, c, d) {
var u = sub(b, a),
v = sub(d, c),
q = sub(c, a),
denom, s;
// Cramer's Rule
denom = u[0] * (-v[1]) - (-v[0]) * u[1];
// Check for parallel lines
if (denom === 0) return [infinity, infinity];
s = (q[0] * (-v[1]) - (-v[0]) * q[1]) / (denom);
return add(a, scale(s, u));
}
function identity(n) {
var i, j,
eye = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]];
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
eye[i][j] = 0.0;
}
}
for (i = 0; i < n; i++){
eye[i][i] = 1.0;
}
return eye;
}
function row(a, row) {
var res = [], i;
for (i = 0; i < a[0].length; i++){
res[i] = a[row][i];
}
return res;
}
// Multiplies matrix A by vector b and returns the resulting vector.
function multiply(A, b) {
var res = [],
i,
x = b.slice();
// Pad for homogenous coordinates.
for (i = 0; i < 3 - b.length; i++) {
x.push(1);
}
for(i = 0; i < A.length; i++){
res[i] = dot(row(A, i), x);
}
return res;
}
// Returns column col from matrix a.
function column(a, col) {
var res = [], i;
for (i = 0; i < a.length; i++){
res[i] = a[i][col];
}
return res;
}
// Multiplies matrix A by matrix B and returns the resulting matrix.
function Multiply(A, B) {
var i, j,
res = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]];
if(A[0].length != B.length){
throw new Error("invalid dimensions");
}
for(i = 0; i < A.length; i++){
for(j = 0; j < B[0].length; j++){
res[i][j] = dot(row(A, i), column(B, j));
}
}
return res;
}
function rotation(theta) {
var rad = theta * Math.PI / 180.0;
var s = Math.sin(rad);
var c = Math.cos(rad);
return [[c, -1.0 * s, 0],
[s, c, 0],
[0, 0, 1]];
}
function translation(delta) {
var dx = delta[0];
var dy = delta[1];
var res = identity(3);
res[0][2] = dx;
res[1][2] = dy;
return res;
}
// Polygon constructor
function Polygon() {
this.transforms = [];
this._matrix = identity(3);
this._origin = null;
}
Polygon.prototype = Object.create(Array.prototype); // subclass Array
Polygon.prototype.constructor = Polygon;
Polygon.prototype.centroid = centroid;
Polygon.prototype.containsPoint = containsPoint;
Polygon.prototype.translate = translate;
Polygon.prototype.rotate = rotate;
Polygon.prototype.scale = resize;
Polygon.prototype.accumulate = accumulate;
Polygon.prototype.origin = origin;
Polygon.prototype.clone = clone;
function centroid() {
return d3Polygon.polygonCentroid(this);
}
function containsPoint(point){
return d3Polygon.polygonContains(this, point);
}
function translate(T) {
var i, v, n;
for (i = 0, n = this.length; i < n; i++) {
v = this[i];
this[i] = [v[0] + T[0], v[1] + T[1]];
}
return this;
}
function rotate(theta, pivot) {
var R = rotation(theta), i, n;
if (pivot) {
this.translate([-pivot[0], -pivot[1]]);
}
for (i = 0, n = this.length; i < n; i++) {
this[i] = multiply(R, this[i]);
}
if (pivot) {
this.translate(pivot);
}
return this;
}
function resize(factor) {
var i, n;
for (i = 0, n = this.length; i < n; i++) {
this[i] = scale(factor, this[i]);
}
return this;
}
// Returns a clone of this polygon with transform history applied.
function origin() {
if (this._origin) return this._origin;
this._origin = this.accumulate();
return this._origin;
}
// Apply transform history to a clone of polygon.
function accumulate() {
var P = this.clone(),
n = this.transforms.length,
M = identity(3),
i, transform;
// Most recent transforms are pushed to end of array.
for (i = n - 1; i >= 0; i--) {
transform = this.transforms[i];
if (transform.rotate && transform.pivot) { // pivot required
P.rotate(transform.rotate, transform.pivot);
M = Multiply(translation(scale(-1, transform.pivot)), M);
M = Multiply(rotation(transform.rotate), M);
M = Multiply(translation(transform.pivot), M);
} else if (transform.translate) {
P.translate(transform.translate);
M = Multiply(translation(transform.translate), M);
}
}
P._matrix = M;
return P;
}
// Produces deep copy of vertex positions, shallow copy of other attributes
function clone() {
var positions = JSON.parse(JSON.stringify(this.slice(0)));
return Object.assign(polygon(positions), this);
}
// Create new Polygon from array of position tuples.
function polygon(positions) {
var P = new Polygon();
P.push.apply(P, positions);
return P;
}
// Returns the undo operation for a translation or rotation about a pivot.
function undo(transform){
var undone;
if (transform.rotate && transform.pivot) {
undone = {rotate: -transform.rotate, pivot: transform.pivot};
} else if (transform.translate) {
undone = {translate: scale(-1, transform.translate)};
}
return undone;
}
// Sutherland-Hodgeman algorithm for convex subject and clip polygons.
function clipPolygon(subject, clip){
var inputList, outputList,
clipped,
i, j, n,
end, edge,
E, S, // Two subject vertices.
eInside, sInside,
intersection,
undone, transforms;
// Ensure clip polygon is traversed in clockwise order.
clip = ccw(clip.clone()).reverse();
ccw(subject);
outputList = subject.slice(0);
for (i = 0, n = clip.length; i < n; i++) {
end = (i + 1) % n;
edge = [clip[i], clip[end]];
inputList = outputList.slice(0);
outputList = [];
S = inputList[inputList.length - 1];
for (j = 0; j < inputList.length; j++) {
E = inputList[j];
eInside = !right(E, edge);
sInside = !right(S, edge);
if (eInside){
if (!sInside){ // exit clip region
intersection = infiniteIntersect(S, E, clip[i], clip[end]);
outputList.push(intersection);
}
outputList.push(E);
} else if (sInside) { // enter clip region
intersection = infiniteIntersect(S, E, clip[i], clip[end]);
outputList.push(intersection);
}
S = E;
}
}
clipped = polygon(outputList);
// Subject polygon's original transform history.
transforms = subject.transforms.slice(0);
// Append reversed (and undone) transfer history of clip polygon.
clipped.target = clip.transforms.slice(0);
undone = clip.transforms.slice(0).reverse(0).map(undo);
transforms = transforms.concat(undone);
clipped.transforms = transforms;
return clipped;
}
// Takes in arrays of polygons and returns intersection between the
// collections using the Sutherland-Hodgeman algorithm.
function clipCollection(A, B){
var result = [], clipped, i, j;
// Clip every polygon in A against every polygon in B.
for (i = 0; i < A.length; i++) {
for (j = 0; j < B.length; j++) {
clipped = clipPolygon(ccw(A[i]), ccw(B[j]));
if (clipped.length > 2) result.push(clipped);
}
}
return result;
}
function degree(rad) {
return rad * 180 / Math.PI;
}
function inDelta(actual, expected, epsilon) {
return actual < expected + epsilon && actual > expected - epsilon;
}
// Returns point of intersection of AB and CD
// or null if segments do not intersect.
function intersect(a, b, c, d) {
var u = sub(b, a),
v = sub(d, c),
q = sub(c, a),
denom, s, t,
epsilon = 0.0;
// Cramer's Rule
denom = u[0] * (-v[1]) - (-v[0]) * u[1];
s = (q[0] * (-v[1]) - (-v[0]) * q[1]) / (denom);
t = (u[0] * q[1] - q[0] * u[1]) / (denom);
return (inDelta(s, 0.5, 0.5 + epsilon) && inDelta(t, 0.5, 0.5 + epsilon))
? add(a, scale(s, u))
: null;
}
// Returns array of polygons resulting from cutting
// convex polygon P by segment ab. If the polygon is
// not cut, an empty array is returned.
function cutPolygon(a, b, P) {
var n = P.length,
_P = [],
P_ = [],
points = [],
e,
f = P[n - 1],
bounds = [],
i = -1,
polygons = [],
x;
// walk through polygon edges, attempting intersections
// with exact vertices or line segments
while (++i < n) {
e = f;
f = P[i];
// compare floating-point positions by reference
if ((a === e || b === e) && !(points.length && Object.is(points[0], e)))
x = e;
else if ((a === f || b === f) && !(points.length && !Object.is(points[0], f)))
x = f;
else
x = intersect(a, b, e, f);
if (!x) continue; // no intersection
if (points.length == 2) break;
points.push(x);
bounds.push(i);
}
// stitch together two generated polygons
if (points.length == 2 && !Object.is(points[0], points[1])) {
// stitch half of polygon
_P.push(points[0]);
i = bounds[0];
while (i != bounds[1]) {
// check point is not an EXACT intersection
if (!Object.is(points[0], P[i]) && ! Object.is(points[1], P[i]))
_P.push(P[i]);
i = (i + 1) % n;
}
_P.push(points[1]);
// stitch other half of polygon
P_.push(points[0]);
P_.push(points[1]);
i = bounds[1];
while (i != bounds[0]) {
// check point is not an EXACT intersection
if (!Object.is(points[0], P[i]) && ! Object.is(points[1], P[i]))
P_.push(P[i]);
i = (i + 1) % n;
}
polygons.push(polygon(_P), polygon(P_));
// transfer parent properties
polygons.forEach(function(d) {
[].push.apply(d.transforms, P.transforms);
});
}
return polygons;
}
function cutCollection(a, b, collection) {
var N = collection.length,
indices = [],
polygons = [],
P, generated,
i;
for (i = 0; i < N; i++) {
P = collection[i];
generated = cutPolygon(a, b, P);
if (generated.length == 2) {
[].push.apply(polygons, generated);
indices.push(i);
}
}
// include polygons that were not cut into two new polygons
polygons = polygons.concat(collection.filter(function(d, i) {
return indices.indexOf(i) === -1;
}));
return polygons;
}
// Takes in a collection of polygons forming a rectangle and produces
// a new collection forming a rectangle of the given width.
function rectangle2Rectangle(collection, width) {
var A, B, C, D, E, F, G, J, K, // follows Tralie's labeling
AFGD, KCF,
area, height,
rectangle = collection.rectangle, // bounding rectangle
l = Infinity,
polygons = [],
i, n, a, b, left, halved, slideLeft, slideUp,
E_Polygon, E_Vertex, F_Polygon, F_Vertex,
centroid;
area = Math.abs(d3Polygon.polygonArea(rectangle));
height = area / width; // square side length
collection = collection.map(function(d) {
return d.clone();
});
// Bounding rectangle for incoming collection.
B = rectangle[0];
F = rectangle[1];
G = rectangle[2];
E = rectangle[3];
l = length(sub(B, F));
if (width > l) {
width = height;
height = area / width;
}
// The rectangle to be produced, defined by [A, B, C, D].
A = add(B, scale(height, normalize(sub(E, B))));
C = add(B, scale(width, normalize(sub(F, B))));
D = add(A, sub(C, B));
// halving the canonical rectangle for the escalator method
while (l > 2 * width) {
E_Polygon = [], E_Vertex = [], F_Polygon = [], F_Vertex = [];
a = add(A, scale(0.5, sub(F, B)));
b = add(B, scale(0.5, sub(F, B)));
l = length(sub(b, F));
left = [A, B, b, a];
// "overshoot" cut segment endpoints to ensure intersection
halved = cutCollection(a, add(b, sub(C, D)), collection);
slideUp = sub(E, B);
slideLeft = sub(B, b);
// translate polgons resulting from the cut (i.e., "stacking the two halves")
halved.forEach(function(d, j) {
centroid = d3Polygon.polygonCentroid(d);
// update exact references to vertices used in exact intersections
d.forEach(function(V, k) { // scan vertices
if (Object.is(E, V)) {
E_Polygon.push(j);
E_Vertex.push(k);
} else if (Object.is(F, V)) {
F_Polygon.push(j);
F_Vertex.push(k);
}
});
if (d3Polygon.polygonContains(left, centroid)) { // slide "up"
d.translate(slideUp).transforms.push({translate: scale(-1, slideUp)}); // undo translate
} else { // slide "left"
d.translate(slideLeft).transforms.push({translate: scale(-1, slideLeft)}); // undo translate
}
});
E = halved[E_Polygon[0]][E_Vertex[0]];
F = halved[F_Polygon[0]][F_Vertex[0]];
// Make all vertices at F share the same reference.
for (i = 1, n = F_Vertex.length; i < n; i++) {
F = halved[F_Polygon[i]][F_Vertex[i]] = halved[F_Polygon[i - 1]][F_Vertex[i - 1]];
}
collection = halved;
}
polygons = collection;
// The "elevator method" assumes rectangle length < (2 x square height).
G = add(F, sub(E, B));
J = intersect(A, F, E, G);
K = intersect(A, F, D, C);
KCF = [K, C, F]; // used to locate elevator pieces
AFGD = [A, F, G, D];
polygons = cutCollection(A, F, polygons);
polygons = cutCollection(D, add(C, scale(1, sub(C, D))), polygons);
// Slide new polygons using elevator method.
polygons.forEach(function(d) {
var centroid,
T;
centroid = d3Polygon.polygonCentroid(d);
if (d3Polygon.polygonContains(KCF, centroid)) {
T = sub(A, K);
d.translate(T).transforms.push({translate: scale(-1, T)});
} else if (d3Polygon.polygonContains(AFGD, centroid)) {
T = sub(A, J);
d.translate(T).transforms.push({translate: scale(-1, T)});
}
});
polygons.rectangle = (isWide([B, C, D, A])) ? [B, C, D, A] : [C, D, A, B];
return polygons;
}
// Assumes BCDA orientation, where a rectangle is wide if
// side BC is longer than BA.
function isWide(rectangle) {
var A = rectangle[3],
B = rectangle[0],
C = rectangle[1];
return length(sub(B, C)) > length(sub(B, A));
}
// Takes in a list of polygon collections, each arranged in a rectangle
// of equal width and returns a list of polygon collections that have been
// arranged to fit in a square.
// The returned list of collections has property `square` which
// denotes the bounding vertices for the stacked collections.
function stack(boxes) {
var previous, current,
A, B, C, D,
pivot, snap,
stacked = [],
i, n,
T, direction, theta;
if (boxes.length < 2) {
stacked = boxes.slice();
stacked.square = stacked[0].rectangle;
return stacked;
}
previous = boxes[0];
stacked.push(previous);
for (i = 1, n = boxes.length; i < n; i++) {
pivot = previous.rectangle[3];
current = boxes[i];
snap = current.rectangle[0];
T = sub(pivot, snap);
current.rectangle = polygon(current.rectangle).translate(T);
direction = cross(pivot, previous.rectangle[2], current.rectangle[1])[2] > 0
? -1
: 1;
theta = degree(angle(pivot, previous.rectangle[2], current.rectangle[1]));
theta *= direction;
// Translate collection of polygons forming a rectangle of a given width.
// Align a vertex and pivot rectangle to fit flush with previous collection.
current.forEach(function(d) {
d.translate(T);
d.transforms.push({
translate: scale(-1, T)
});
d.rotate(theta, pivot);
d.transforms.push({
rotate: -theta,
pivot: pivot,
});
});
current.rectangle.rotate(theta, pivot);
stacked.push(current);
previous = current;
}
A = stacked[n - 1].rectangle[3];
B = stacked[0].rectangle[0];
C = stacked[0].rectangle[1];
D = stacked[n - 1].rectangle[2];
stacked.square = [B, C, D, A];
return stacked;
}
function project(u, v) {
return scale(dot(u, v) / dot(v, v), v);
}
function triangle2Rectangle(P) {
var index = 0,
A, B, C, D, E, F, G, H, M,
BC, BA, MB, MC, ME,
BCFD, DGB, FCH,
maxAngle = -Infinity,
polygons,
theta, i;
if (d3Polygon.polygonArea(P) == 0) return [];
// Find largest angle in triangle T.
for (i = 0; i < 3; i++) {
theta = 0;
theta = angle(P[i % 3], P[(i + 1) % 3], P[(i + 2) % 3]);
if (theta > maxAngle) {
maxAngle = theta;
index = i;
}
}
A = P[index];
B = P[(index + 1) % 3];
C = P[(index + 2) % 3];
BC = sub(C, B);
BA = sub(A, B);
M = add(B, project(BA, BC));
E = add(A, scale(0.5, sub(M, A)));
MB = sub(B, M);
MC = sub(C, M);
ME = sub(E, M);
G = add(M, add(MB, ME));
H = add(M, add(MC, ME));
D = intersect(E, G, A, B); // pivot
F = intersect(E, H, A, C); // pivot
BCFD = polygon([B, C, F, D]);
DGB = polygon([D, G, B]);
FCH = polygon([F, C, H]);
// transforms to return polygons to previous positions
DGB.transforms.push({rotate: degree(Math.PI), pivot: D});
FCH.transforms.push({rotate: degree(-Math.PI), pivot: F});
polygons = [BCFD, DGB, FCH];
polygons.rectangle = [B, C, H, G];
return polygons;
}
// Takes in source and subject meshes, returns a decomposition layout.
function decompose(source, subject) {
var A, B,
sourceStack, subjectStack,
squareA, squareB,
centroid, target, T,
clipped, theta, direction,
i = 0, j = 0, distance, min = Infinity,
factor, area, width;
source = source.map(function(d) { return polygon(d); });
subject = subject.map(function(d) { return polygon(d); });
area = collectionArea(source);
width = Math.sqrt(area);
factor = Math.sqrt(area / collectionArea(subject) );
scaleCollection(factor, subject);
sourceStack = stack(source.map(function(d) {return stackable(width, d); }));
subjectStack = stack(subject.map(function(d) {return stackable(width, d); }));
A = flatten(sourceStack);
B = flatten(subjectStack);
A.square = sourceStack.square;
B.square = subjectStack.square;
squareA = polygon(A.square);
squareB = polygon(B.square);
centroid = squareA.centroid();
target = squareB.centroid();
T = [(centroid[0] - target[0]), (centroid[1] - target[1])];
squareB = squareB.clone().translate(T);
// find nearest vertex coorespondence in Q for first vertex in P
for (i = 0, j = 0; i < 4; i++) {
distance = length(sub(squareA[0], squareB[i]));
if (distance < min) {
min = distance;
j = i;
}
}
// rotate through a minimal angle, in the correct direction
direction = cross(centroid, squareB[j], squareA[0])[2] > 0 ? 1 : -1;
theta = direction * degree(angle(centroid, squareB[j], squareA[0]));
// center collection B on collection A
B.forEach(function(d) {
d.translate(T);
d.transforms.push({
translate: scale(-1, T),
});
d.rotate(theta, centroid);
d.transforms.push({
rotate: -theta,
pivot: centroid,
});
});
clipped = clipCollection(A, B);
clipped = clipped.map(function(d) {
var p = d.clone();
p.transforms = d.target;
p = p.origin(); // place in subject triangle
p.transforms = d.transforms; // restore joined transform history
return p;
});
clipped.scale = factor;
return clipped;
}
function stackable(width, triangle) {
return rectangle2Rectangle(triangle2Rectangle(triangle), width);
}
function flatten(groups) {
var flattened = [];
groups.forEach(function(d) {
[].push.apply(flattened, d);
});
return flattened;
}
function collectionCentroid(collection) {
var centroids;
centroids = collection.map(function(d) {
return polygon(d).centroid();
});
if (centroids.length == 1) {
return centroids[0];
}
if (centroids.length == 2) {
return [(centroids[0][0] + centroids[1][0]) / 2,
(centroids[0][1] + centroids[1][1]) / 2];
}
return polygon(centroids).centroid();
}
function collectionArea(collection) {
return d3Array.sum(collection, function(d) { return d3Polygon.polygonArea(d); });
}
function scaleCollection(factor, collection) {
var C = collectionCentroid(collection);
collection.forEach(function(d) {
d.translate(scale(-1, C));
d.scale(factor);
d.translate(C);
});
return collection;
}
function decomposition(source, subject) {
var polygons = decompose(source, subject);
return {
source: function() {
return polygons.map(function(d) {
return d.origin().slice(0);
});
},
subject: function() {
return polygons.map(function(d) {
return d.slice(0);
});
},
scale: function() {
return polygons.scale;
}
}
}
// External Mapbox earcut module.
function triangulate(vertices) {
var indices,
triangles;
indices = earcut(flattenCoordinates(vertices));
triangles = unflattenTriangles(decodeIndices(indices, vertices));
return triangles;
}
function flattenCoordinates(points) {
var i, n,
flattened = [];
for (i = 0, n = points.length; i < n; i++) {
flattened.push(points[i][0], points[i][1]);
}
return flattened;
}
function decodeIndices(indices, points) {
return indices.map(function(i) { return points[i]; });
}
function unflattenTriangles(points) {
var i, n,
decoded = [];
for (i = 0, n = points.length; i < n; i += 3) {
decoded.push([points[i], points[i + 1], points[i + 2]]);
}
return decoded;
}
function equidecompose(source, subject) {
var sourceTriangles = orient(triangulate(source)),
subjectTriangles = orient(triangulate(subject));
return decomposition(sourceTriangles, subjectTriangles);
}
// In-place reversal of clockwise winding produced by earcut.
function orient(triangles) {
return triangles.map(function(d) { return d.reverse(); });
}
function equidecomposeMesh(source, subject) {
return decomposition(source, subject);
}
exports.equidecompose = equidecompose;
exports.equidecomposeMesh = equidecomposeMesh;
exports.triangle2Rectangle = triangle2Rectangle;
exports.rectangle2Rectangle = rectangle2Rectangle;
}));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment