This project was developed by Brooks Mershon and Joy Patel for Chris Tralie's Digital 3D Geometry (MATH 290) course taught at Duke University during Spring 2016.
Note: Numerical precision related bugs persist. See the issues to find out more.
The scissors module implements the equidecomposition of one simple polygon into another simple polygon of equal area. A decomposition for two such polygons produces polygons which can be rearranged by rigid translation and rotation to form either polygon. Such a decomposition is also known as scissors congruence.
To install development and runtime dependences, run the following command in the root directory:
npm install
The node_modules/ directory is created by the node package manager to hold all the dependences for the project.
There are two targets that can be built from the files in the src/ directory:
- The file build/foo.js is built from foo.js and defines exports used for testing partial functionality on a global module
foo. - The file build/scissors.js is built from index.js and defines exports for this module's default global
scissors.
The file foo.js defines all the exports to be included in a global called foo. This module makes available functionality that would not otherwise be exported in the d3-equidecompose module. For development purposes, this global lets foo functionality be tested.
Using a developmental build of the scissors functions.
<script src="evscript>
var foo = foo.bar;
To rebuild foo.js:
npm run foo
The file index.js defines all the exports to be included in a scissors global module.
Using the scissors module.
<script src="scissors.js"></script>
var A = [a, b, c, e, f, g, h, i, j];
var B = [k, l, m, n]; // same area as A
var decomposition = scissors.equidecompose(A, B);
var source = decomposition.source(); // polygons placed in source polygon A
var subject = decompositon.subject(); // polygons placed in subject polygon BTo rebuild scissors.js:
npm run pretest
# scissors.equidecompose(source, subject)
Creates a decomposition of the specified source polygon into the subject polygon with the same area. Input polygons are triangulated using the earcut method.
If the subject polygon does not have the same area as the subject polygon, the decomposition will be computed as if the subject were scaled about its centroid so that the source and subject are of equal area.
# scissors.equidecomposeMesh(source, subject)
Creates a decomposition of the specified source mesh into the subject mesh with the same area. Input meshes are assumed to be triangulations of polygons with counterclockwise winding.
If the subject polygon does not have the same area as the subject polygon, the decomposition will be computed as if the subject were scaled about its centroid so that the source and subject are of equal area.
# decomposition.source()
Returns an array of polygons with counterclockwise winding represented as arrays of positions. Each polygon is positioned within the source polygon used to create a decomposition, and its index within the returned array matches the corresponding index of the subject polygon.
# decomposition.subject()
Returns an array of polygons with counterclockwise winding represented as arrays of positions. Each polygon is positioned within the subject polygon used to create a decomposition, and its index within the returned array matches the corresponding index of the source polygon.
# decomposition.sort([comparator])
A comparator function which takes two input arrays representing the respective positions of two polygons may be passed into decomposition.filter() in order to change the output ordering of subject and source polygons. Subject and source polygons will remain in correspondence with one another regardless of the provided comparator function. If no comparator is passed in, the current comparator is returned.
var source = decomposition
.sort(comparator)
.source();
// Polygons returned in descending order of area.
function comparator(a, b) {
return -(d3.polygonArea(a) - d3.polygonArea(b));
}