Skip to content

Instantly share code, notes, and snippets.

@wereHamster

wereHamster/.gitignore

Last active February 20, 2019 01:42
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wereHamster/13f3e76d621e9cbaafff3398c0e8a2c7 to your computer and use it in GitHub Desktop.
Save wereHamster/13f3e76d621e9cbaafff3398c0e8a2c7 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
.gitignore
index.js
index.d.ts
example.js
example.d.ts
node_modules/
Raw
README.md

Simple Square Packing Algorithm

Raw
bundle.js
(function () {
'use strict';
var xhtml = "http://www.w3.org/1999/xhtml";
var namespaces = {
svg: "http://www.w3.org/2000/svg",
xhtml: xhtml,
xlink: "http://www.w3.org/1999/xlink",
xml: "http://www.w3.org/XML/1998/namespace",
xmlns: "http://www.w3.org/2000/xmlns/"
};
var namespace = function(name) {
var prefix = name += "", i = prefix.indexOf(":");
if (i >= 0 && (prefix = name.slice(0, i)) !== "xmlns") name = name.slice(i + 1);
return namespaces.hasOwnProperty(prefix) ? {space: namespaces[prefix], local: name} : name;
};
function creatorInherit(name) {
return function() {
var document = this.ownerDocument,
uri = this.namespaceURI;
return uri === xhtml && document.documentElement.namespaceURI === xhtml
? document.createElement(name)
: document.createElementNS(uri, name);
};
}
function creatorFixed(fullname) {
return function() {
return this.ownerDocument.createElementNS(fullname.space, fullname.local);
};
}
var creator = function(name) {
var fullname = namespace(name);
return (fullname.local
? creatorFixed
: creatorInherit)(fullname);
};
var matcher = function(selector) {
return function() {
return this.matches(selector);
};
};
if (typeof document !== "undefined") {
var element = document.documentElement;
if (!element.matches) {
var vendorMatches = element.webkitMatchesSelector
|| element.msMatchesSelector
|| element.mozMatchesSelector
|| element.oMatchesSelector;
matcher = function(selector) {
return function() {
return vendorMatches.call(this, selector);
};
};
}
}
var matcher$1 = matcher;
var filterEvents = {};
var event = null;
if (typeof document !== "undefined") {
var element$1 = document.documentElement;
if (!("onmouseenter" in element$1)) {
filterEvents = {mouseenter: "mouseover", mouseleave: "mouseout"};
}
}
function filterContextListener(listener, index, group) {
listener = contextListener(listener, index, group);
return function(event) {
var related = event.relatedTarget;
if (!related || (related !== this && !(related.compareDocumentPosition(this) & 8))) {
listener.call(this, event);
}
};
}
function contextListener(listener, index, group) {
return function(event1) {
var event0 = event; // Events can be reentrant (e.g., focus).
event = event1;
try {
listener.call(this, this.__data__, index, group);
} finally {
event = event0;
}
};
}
function parseTypenames(typenames) {
return typenames.trim().split(/^|\s+/).map(function(t) {
var name = "", i = t.indexOf(".");
if (i >= 0) name = t.slice(i + 1), t = t.slice(0, i);
return {type: t, name: name};
});
}
function onRemove(typename) {
return function() {
var on = this.__on;
if (!on) return;
for (var j = 0, i = -1, m = on.length, o; j < m; ++j) {
if (o = on[j], (!typename.type || o.type === typename.type) && o.name === typename.name) {
this.removeEventListener(o.type, o.listener, o.capture);
} else {
on[++i] = o;
}
}
if (++i) on.length = i;
else delete this.__on;
};
}
function onAdd(typename, value, capture) {
var wrap = filterEvents.hasOwnProperty(typename.type) ? filterContextListener : contextListener;
return function(d, i, group) {
var on = this.__on, o, listener = wrap(value, i, group);
if (on) for (var j = 0, m = on.length; j < m; ++j) {
if ((o = on[j]).type === typename.type && o.name === typename.name) {
this.removeEventListener(o.type, o.listener, o.capture);
this.addEventListener(o.type, o.listener = listener, o.capture = capture);
o.value = value;
return;
}
}
this.addEventListener(typename.type, listener, capture);
o = {type: typename.type, name: typename.name, value: value, listener: listener, capture: capture};
if (!on) this.__on = [o];
else on.push(o);
};
}
var selection_on = function(typename, value, capture) {
var typenames = parseTypenames(typename + ""), i, n = typenames.length, t;
if (arguments.length < 2) {
var on = this.node().__on;
if (on) for (var j = 0, m = on.length, o; j < m; ++j) {
for (i = 0, o = on[j]; i < n; ++i) {
if ((t = typenames[i]).type === o.type && t.name === o.name) {
return o.value;
}
}
}
return;
}
on = value ? onAdd : onRemove;
if (capture == null) capture = false;
for (i = 0; i < n; ++i) this.each(on(typenames[i], value, capture));
return this;
};
function none() {}
var selector = function(selector) {
return selector == null ? none : function() {
return this.querySelector(selector);
};
};
var selection_select = function(select) {
if (typeof select !== "function") select = selector(select);
for (var groups = this._groups, m = groups.length, subgroups = new Array(m), j = 0; j < m; ++j) {
for (var group = groups[j], n = group.length, subgroup = subgroups[j] = new Array(n), node, subnode, i = 0; i < n; ++i) {
if ((node = group[i]) && (subnode = select.call(node, node.__data__, i, group))) {
if ("__data__" in node) subnode.__data__ = node.__data__;
subgroup[i] = subnode;
}
}
}
return new Selection(subgroups, this._parents);
};
function empty() {
return [];
}
var selectorAll = function(selector) {
return selector == null ? empty : function() {
return this.querySelectorAll(selector);
};
};
var selection_selectAll = function(select) {
if (typeof select !== "function") select = selectorAll(select);
for (var groups = this._groups, m = groups.length, subgroups = [], parents = [], j = 0; j < m; ++j) {
for (var group = groups[j], n = group.length, node, i = 0; i < n; ++i) {
if (node = group[i]) {
subgroups.push(select.call(node, node.__data__, i, group));
parents.push(node);
}
}
}
return new Selection(subgroups, parents);
};
var selection_filter = function(match) {
if (typeof match !== "function") match = matcher$1(match);
for (var groups = this._groups, m = groups.length, subgroups = new Array(m), j = 0; j < m; ++j) {
for (var group = groups[j], n = group.length, subgroup = subgroups[j] = [], node, i = 0; i < n; ++i) {
if ((node = group[i]) && match.call(node, node.__data__, i, group)) {
subgroup.push(node);
}
}
}
return new Selection(subgroups, this._parents);
};
var sparse = function(update) {
return new Array(update.length);
};
var selection_enter = function() {
return new Selection(this._enter || this._groups.map(sparse), this._parents);
};
function EnterNode(parent, datum) {
this.ownerDocument = parent.ownerDocument;
this.namespaceURI = parent.namespaceURI;
this._next = null;
this._parent = parent;
this.__data__ = datum;
}
EnterNode.prototype = {
constructor: EnterNode,
appendChild: function(child) { return this._parent.insertBefore(child, this._next); },
insertBefore: function(child, next) { return this._parent.insertBefore(child, next); },
querySelector: function(selector) { return this._parent.querySelector(selector); },
querySelectorAll: function(selector) { return this._parent.querySelectorAll(selector); }
};
var constant = function(x) {
return function() {
return x;
};
};
var keyPrefix = "$"; // Protect against keys like “__proto__”.
function bindIndex(parent, group, enter, update, exit, data) {
var i = 0,
node,
groupLength = group.length,
dataLength = data.length;
// Put any non-null nodes that fit into update.
// Put any null nodes into enter.
// Put any remaining data into enter.
for (; i < dataLength; ++i) {
if (node = group[i]) {
node.__data__ = data[i];
update[i] = node;
} else {
enter[i] = new EnterNode(parent, data[i]);
}
}
// Put any non-null nodes that don’t fit into exit.
for (; i < groupLength; ++i) {
if (node = group[i]) {
exit[i] = node;
}
}
}
function bindKey(parent, group, enter, update, exit, data, key) {
var i,
node,
nodeByKeyValue = {},
groupLength = group.length,
dataLength = data.length,
keyValues = new Array(groupLength),
keyValue;
// Compute the key for each node.
// If multiple nodes have the same key, the duplicates are added to exit.
for (i = 0; i < groupLength; ++i) {
if (node = group[i]) {
keyValues[i] = keyValue = keyPrefix + key.call(node, node.__data__, i, group);
if (keyValue in nodeByKeyValue) {
exit[i] = node;
} else {
nodeByKeyValue[keyValue] = node;
}
}
}
// Compute the key for each datum.
// If there a node associated with this key, join and add it to update.
// If there is not (or the key is a duplicate), add it to enter.
for (i = 0; i < dataLength; ++i) {
keyValue = keyPrefix + key.call(parent, data[i], i, data);
if (node = nodeByKeyValue[keyValue]) {
update[i] = node;
node.__data__ = data[i];
nodeByKeyValue[keyValue] = null;
} else {
enter[i] = new EnterNode(parent, data[i]);
}
}
// Add any remaining nodes that were not bound to data to exit.
for (i = 0; i < groupLength; ++i) {
if ((node = group[i]) && (nodeByKeyValue[keyValues[i]] === node)) {
exit[i] = node;
}
}
}
var selection_data = function(value, key) {
if (!value) {
data = new Array(this.size()), j = -1;
this.each(function(d) { data[++j] = d; });
return data;
}
var bind = key ? bindKey : bindIndex,
parents = this._parents,
groups = this._groups;
if (typeof value !== "function") value = constant(value);
for (var m = groups.length, update = new Array(m), enter = new Array(m), exit = new Array(m), j = 0; j < m; ++j) {
var parent = parents[j],
group = groups[j],
groupLength = group.length,
data = value.call(parent, parent && parent.__data__, j, parents),
dataLength = data.length,
enterGroup = enter[j] = new Array(dataLength),
updateGroup = update[j] = new Array(dataLength),
exitGroup = exit[j] = new Array(groupLength);
bind(parent, group, enterGroup, updateGroup, exitGroup, data, key);
// Now connect the enter nodes to their following update node, such that
// appendChild can insert the materialized enter node before this node,
// rather than at the end of the parent node.
for (var i0 = 0, i1 = 0, previous, next; i0 < dataLength; ++i0) {
if (previous = enterGroup[i0]) {
if (i0 >= i1) i1 = i0 + 1;
while (!(next = updateGroup[i1]) && ++i1 < dataLength);
previous._next = next || null;
}
}
}
update = new Selection(update, parents);
update._enter = enter;
update._exit = exit;
return update;
};
var selection_exit = function() {
return new Selection(this._exit || this._groups.map(sparse), this._parents);
};
var selection_merge = function(selection) {
for (var groups0 = this._groups, groups1 = selection._groups, m0 = groups0.length, m1 = groups1.length, m = Math.min(m0, m1), merges = new Array(m0), j = 0; j < m; ++j) {
for (var group0 = groups0[j], group1 = groups1[j], n = group0.length, merge = merges[j] = new Array(n), node, i = 0; i < n; ++i) {
if (node = group0[i] || group1[i]) {
merge[i] = node;
}
}
}
for (; j < m0; ++j) {
merges[j] = groups0[j];
}
return new Selection(merges, this._parents);
};
var selection_order = function() {
for (var groups = this._groups, j = -1, m = groups.length; ++j < m;) {
for (var group = groups[j], i = group.length - 1, next = group[i], node; --i >= 0;) {
if (node = group[i]) {
if (next && next !== node.nextSibling) next.parentNode.insertBefore(node, next);
next = node;
}
}
}
return this;
};
var selection_sort = function(compare) {
if (!compare) compare = ascending;
function compareNode(a, b) {
return a && b ? compare(a.__data__, b.__data__) : !a - !b;
}
for (var groups = this._groups, m = groups.length, sortgroups = new Array(m), j = 0; j < m; ++j) {
for (var group = groups[j], n = group.length, sortgroup = sortgroups[j] = new Array(n), node, i = 0; i < n; ++i) {
if (node = group[i]) {
sortgroup[i] = node;
}
}
sortgroup.sort(compareNode);
}
return new Selection(sortgroups, this._parents).order();
};
function ascending(a, b) {
return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
}
var selection_call = function() {
var callback = arguments[0];
arguments[0] = this;
callback.apply(null, arguments);
return this;
};
var selection_nodes = function() {
var nodes = new Array(this.size()), i = -1;
this.each(function() { nodes[++i] = this; });
return nodes;
};
var selection_node = function() {
for (var groups = this._groups, j = 0, m = groups.length; j < m; ++j) {
for (var group = groups[j], i = 0, n = group.length; i < n; ++i) {
var node = group[i];
if (node) return node;
}
}
return null;
};
var selection_size = function() {
var size = 0;
this.each(function() { ++size; });
return size;
};
var selection_empty = function() {
return !this.node();
};
var selection_each = function(callback) {
for (var groups = this._groups, j = 0, m = groups.length; j < m; ++j) {
for (var group = groups[j], i = 0, n = group.length, node; i < n; ++i) {
if (node = group[i]) callback.call(node, node.__data__, i, group);
}
}
return this;
};
function attrRemove(name) {
return function() {
this.removeAttribute(name);
};
}
function attrRemoveNS(fullname) {
return function() {
this.removeAttributeNS(fullname.space, fullname.local);
};
}
function attrConstant(name, value) {
return function() {
this.setAttribute(name, value);
};
}
function attrConstantNS(fullname, value) {
return function() {
this.setAttributeNS(fullname.space, fullname.local, value);
};
}
function attrFunction(name, value) {
return function() {
var v = value.apply(this, arguments);
if (v == null) this.removeAttribute(name);
else this.setAttribute(name, v);
};
}
function attrFunctionNS(fullname, value) {
return function() {
var v = value.apply(this, arguments);
if (v == null) this.removeAttributeNS(fullname.space, fullname.local);
else this.setAttributeNS(fullname.space, fullname.local, v);
};
}
var selection_attr = function(name, value) {
var fullname = namespace(name);
if (arguments.length < 2) {
var node = this.node();
return fullname.local
? node.getAttributeNS(fullname.space, fullname.local)
: node.getAttribute(fullname);
}
return this.each((value == null
? (fullname.local ? attrRemoveNS : attrRemove) : (typeof value === "function"
? (fullname.local ? attrFunctionNS : attrFunction)
: (fullname.local ? attrConstantNS : attrConstant)))(fullname, value));
};
var defaultView = function(node) {
return (node.ownerDocument && node.ownerDocument.defaultView) // node is a Node
|| (node.document && node) // node is a Window
|| node.defaultView; // node is a Document
};
function styleRemove(name) {
return function() {
this.style.removeProperty(name);
};
}
function styleConstant(name, value, priority) {
return function() {
this.style.setProperty(name, value, priority);
};
}
function styleFunction(name, value, priority) {
return function() {
var v = value.apply(this, arguments);
if (v == null) this.style.removeProperty(name);
else this.style.setProperty(name, v, priority);
};
}
var selection_style = function(name, value, priority) {
var node;
return arguments.length > 1
? this.each((value == null
? styleRemove : typeof value === "function"
? styleFunction
: styleConstant)(name, value, priority == null ? "" : priority))
: defaultView(node = this.node())
.getComputedStyle(node, null)
.getPropertyValue(name);
};
function propertyRemove(name) {
return function() {
delete this[name];
};
}
function propertyConstant(name, value) {
return function() {
this[name] = value;
};
}
function propertyFunction(name, value) {
return function() {
var v = value.apply(this, arguments);
if (v == null) delete this[name];
else this[name] = v;
};
}
var selection_property = function(name, value) {
return arguments.length > 1
? this.each((value == null
? propertyRemove : typeof value === "function"
? propertyFunction
: propertyConstant)(name, value))
: this.node()[name];
};
function classArray(string) {
return string.trim().split(/^|\s+/);
}
function classList(node) {
return node.classList || new ClassList(node);
}
function ClassList(node) {
this._node = node;
this._names = classArray(node.getAttribute("class") || "");
}
ClassList.prototype = {
add: function(name) {
var i = this._names.indexOf(name);
if (i < 0) {
this._names.push(name);
this._node.setAttribute("class", this._names.join(" "));
}
},
remove: function(name) {
var i = this._names.indexOf(name);
if (i >= 0) {
this._names.splice(i, 1);
this._node.setAttribute("class", this._names.join(" "));
}
},
contains: function(name) {
return this._names.indexOf(name) >= 0;
}
};
function classedAdd(node, names) {
var list = classList(node), i = -1, n = names.length;
while (++i < n) list.add(names[i]);
}
function classedRemove(node, names) {
var list = classList(node), i = -1, n = names.length;
while (++i < n) list.remove(names[i]);
}
function classedTrue(names) {
return function() {
classedAdd(this, names);
};
}
function classedFalse(names) {
return function() {
classedRemove(this, names);
};
}
function classedFunction(names, value) {
return function() {
(value.apply(this, arguments) ? classedAdd : classedRemove)(this, names);
};
}
var selection_classed = function(name, value) {
var names = classArray(name + "");
if (arguments.length < 2) {
var list = classList(this.node()), i = -1, n = names.length;
while (++i < n) if (!list.contains(names[i])) return false;
return true;
}
return this.each((typeof value === "function"
? classedFunction : value
? classedTrue
: classedFalse)(names, value));
};
function textRemove() {
this.textContent = "";
}
function textConstant(value) {
return function() {
this.textContent = value;
};
}
function textFunction(value) {
return function() {
var v = value.apply(this, arguments);
this.textContent = v == null ? "" : v;
};
}
var selection_text = function(value) {
return arguments.length
? this.each(value == null
? textRemove : (typeof value === "function"
? textFunction
: textConstant)(value))
: this.node().textContent;
};
function htmlRemove() {
this.innerHTML = "";
}
function htmlConstant(value) {
return function() {
this.innerHTML = value;
};
}
function htmlFunction(value) {
return function() {
var v = value.apply(this, arguments);
this.innerHTML = v == null ? "" : v;
};
}
var selection_html = function(value) {
return arguments.length
? this.each(value == null
? htmlRemove : (typeof value === "function"
? htmlFunction
: htmlConstant)(value))
: this.node().innerHTML;
};
function raise() {
if (this.nextSibling) this.parentNode.appendChild(this);
}
var selection_raise = function() {
return this.each(raise);
};
function lower() {
if (this.previousSibling) this.parentNode.insertBefore(this, this.parentNode.firstChild);
}
var selection_lower = function() {
return this.each(lower);
};
var selection_append = function(name) {
var create = typeof name === "function" ? name : creator(name);
return this.select(function() {
return this.appendChild(create.apply(this, arguments));
});
};
function constantNull() {
return null;
}
var selection_insert = function(name, before) {
var create = typeof name === "function" ? name : creator(name),
select = before == null ? constantNull : typeof before === "function" ? before : selector(before);
return this.select(function() {
return this.insertBefore(create.apply(this, arguments), select.apply(this, arguments) || null);
});
};
function remove() {
var parent = this.parentNode;
if (parent) parent.removeChild(this);
}
var selection_remove = function() {
return this.each(remove);
};
var selection_datum = function(value) {
return arguments.length
? this.property("__data__", value)
: this.node().__data__;
};
function dispatchEvent(node, type, params) {
var window = defaultView(node),
event = window.CustomEvent;
if (event) {
event = new event(type, params);
} else {
event = window.document.createEvent("Event");
if (params) event.initEvent(type, params.bubbles, params.cancelable), event.detail = params.detail;
else event.initEvent(type, false, false);
}
node.dispatchEvent(event);
}
function dispatchConstant(type, params) {
return function() {
return dispatchEvent(this, type, params);
};
}
function dispatchFunction(type, params) {
return function() {
return dispatchEvent(this, type, params.apply(this, arguments));
};
}
var selection_dispatch = function(type, params) {
return this.each((typeof params === "function"
? dispatchFunction
: dispatchConstant)(type, params));
};
var root = [null];
function Selection(groups, parents) {
this._groups = groups;
this._parents = parents;
}
function selection() {
return new Selection([[document.documentElement]], root);
}
Selection.prototype = selection.prototype = {
constructor: Selection,
select: selection_select,
selectAll: selection_selectAll,
filter: selection_filter,
data: selection_data,
enter: selection_enter,
exit: selection_exit,
merge: selection_merge,
order: selection_order,
sort: selection_sort,
call: selection_call,
nodes: selection_nodes,
node: selection_node,
size: selection_size,
empty: selection_empty,
each: selection_each,
attr: selection_attr,
style: selection_style,
property: selection_property,
classed: selection_classed,
text: selection_text,
html: selection_html,
raise: selection_raise,
lower: selection_lower,
append: selection_append,
insert: selection_insert,
remove: selection_remove,
datum: selection_datum,
on: selection_on,
dispatch: selection_dispatch
};
var select = function(selector) {
return typeof selector === "string"
? new Selection([[document.querySelector(selector)]], [document.documentElement])
: new Selection([[selector]], root);
};
var pi = Math.PI;
var tau = 2 * pi;
var epsilon = 1e-6;
var tauEpsilon = tau - epsilon;
function Path() {
this._x0 = this._y0 = // start of current subpath
this._x1 = this._y1 = null; // end of current subpath
this._ = "";
}
function path() {
return new Path;
}
Path.prototype = path.prototype = {
constructor: Path,
moveTo: function(x, y) {
this._ += "M" + (this._x0 = this._x1 = +x) + "," + (this._y0 = this._y1 = +y);
},
closePath: function() {
if (this._x1 !== null) {
this._x1 = this._x0, this._y1 = this._y0;
this._ += "Z";
}
},
lineTo: function(x, y) {
this._ += "L" + (this._x1 = +x) + "," + (this._y1 = +y);
},
quadraticCurveTo: function(x1, y1, x, y) {
this._ += "Q" + (+x1) + "," + (+y1) + "," + (this._x1 = +x) + "," + (this._y1 = +y);
},
bezierCurveTo: function(x1, y1, x2, y2, x, y) {
this._ += "C" + (+x1) + "," + (+y1) + "," + (+x2) + "," + (+y2) + "," + (this._x1 = +x) + "," + (this._y1 = +y);
},
arcTo: function(x1, y1, x2, y2, r) {
x1 = +x1, y1 = +y1, x2 = +x2, y2 = +y2, r = +r;
var x0 = this._x1,
y0 = this._y1,
x21 = x2 - x1,
y21 = y2 - y1,
x01 = x0 - x1,
y01 = y0 - y1,
l01_2 = x01 * x01 + y01 * y01;
// Is the radius negative? Error.
if (r < 0) throw new Error("negative radius: " + r);
// Is this path empty? Move to (x1,y1).
if (this._x1 === null) {
this._ += "M" + (this._x1 = x1) + "," + (this._y1 = y1);
}
// Or, is (x1,y1) coincident with (x0,y0)? Do nothing.
else if (!(l01_2 > epsilon)) {}
// Or, are (x0,y0), (x1,y1) and (x2,y2) collinear?
// Equivalently, is (x1,y1) coincident with (x2,y2)?
// Or, is the radius zero? Line to (x1,y1).
else if (!(Math.abs(y01 * x21 - y21 * x01) > epsilon) || !r) {
this._ += "L" + (this._x1 = x1) + "," + (this._y1 = y1);
}
// Otherwise, draw an arc!
else {
var x20 = x2 - x0,
y20 = y2 - y0,
l21_2 = x21 * x21 + y21 * y21,
l20_2 = x20 * x20 + y20 * y20,
l21 = Math.sqrt(l21_2),
l01 = Math.sqrt(l01_2),
l = r * Math.tan((pi - Math.acos((l21_2 + l01_2 - l20_2) / (2 * l21 * l01))) / 2),
t01 = l / l01,
t21 = l / l21;
// If the start tangent is not coincident with (x0,y0), line to.
if (Math.abs(t01 - 1) > epsilon) {
this._ += "L" + (x1 + t01 * x01) + "," + (y1 + t01 * y01);
}
this._ += "A" + r + "," + r + ",0,0," + (+(y01 * x20 > x01 * y20)) + "," + (this._x1 = x1 + t21 * x21) + "," + (this._y1 = y1 + t21 * y21);
}
},
arc: function(x, y, r, a0, a1, ccw) {
x = +x, y = +y, r = +r;
var dx = r * Math.cos(a0),
dy = r * Math.sin(a0),
x0 = x + dx,
y0 = y + dy,
cw = 1 ^ ccw,
da = ccw ? a0 - a1 : a1 - a0;
// Is the radius negative? Error.
if (r < 0) throw new Error("negative radius: " + r);
// Is this path empty? Move to (x0,y0).
if (this._x1 === null) {
this._ += "M" + x0 + "," + y0;
}
// Or, is (x0,y0) not coincident with the previous point? Line to (x0,y0).
else if (Math.abs(this._x1 - x0) > epsilon || Math.abs(this._y1 - y0) > epsilon) {
this._ += "L" + x0 + "," + y0;
}
// Is this arc empty? We’re done.
if (!r) return;
// Is this a complete circle? Draw two arcs to complete the circle.
if (da > tauEpsilon) {
this._ += "A" + r + "," + r + ",0,1," + cw + "," + (x - dx) + "," + (y - dy) + "A" + r + "," + r + ",0,1," + cw + "," + (this._x1 = x0) + "," + (this._y1 = y0);
}
// Otherwise, draw an arc!
else {
if (da < 0) da = da % tau + tau;
this._ += "A" + r + "," + r + ",0," + (+(da >= pi)) + "," + cw + "," + (this._x1 = x + r * Math.cos(a1)) + "," + (this._y1 = y + r * Math.sin(a1));
}
},
rect: function(x, y, w, h) {
this._ += "M" + (this._x0 = this._x1 = +x) + "," + (this._y0 = this._y1 = +y) + "h" + (+w) + "v" + (+h) + "h" + (-w) + "Z";
},
toString: function() {
return this._;
}
};
var constant$1 = function(x) {
return function constant() {
return x;
};
};
function Linear(context) {
this._context = context;
}
Linear.prototype = {
areaStart: function() {
this._line = 0;
},
areaEnd: function() {
this._line = NaN;
},
lineStart: function() {
this._point = 0;
},
lineEnd: function() {
if (this._line || (this._line !== 0 && this._point === 1)) this._context.closePath();
this._line = 1 - this._line;
},
point: function(x, y) {
x = +x, y = +y;
switch (this._point) {
case 0: this._point = 1; this._line ? this._context.lineTo(x, y) : this._context.moveTo(x, y); break;
case 1: this._point = 2; // proceed
default: this._context.lineTo(x, y); break;
}
}
};
var curveLinear = function(context) {
return new Linear(context);
};
function x(p) {
return p[0];
}
function y(p) {
return p[1];
}
var line = function() {
var x$$1 = x,
y$$1 = y,
defined = constant$1(true),
context = null,
curve = curveLinear,
output = null;
function line(data) {
var i,
n = data.length,
d,
defined0 = false,
buffer;
if (context == null) output = curve(buffer = path());
for (i = 0; i <= n; ++i) {
if (!(i < n && defined(d = data[i], i, data)) === defined0) {
if (defined0 = !defined0) output.lineStart();
else output.lineEnd();
}
if (defined0) output.point(+x$$1(d, i, data), +y$$1(d, i, data));
}
if (buffer) return output = null, buffer + "" || null;
}
line.x = function(_) {
return arguments.length ? (x$$1 = typeof _ === "function" ? _ : constant$1(+_), line) : x$$1;
};
line.y = function(_) {
return arguments.length ? (y$$1 = typeof _ === "function" ? _ : constant$1(+_), line) : y$$1;
};
line.defined = function(_) {
return arguments.length ? (defined = typeof _ === "function" ? _ : constant$1(!!_), line) : defined;
};
line.curve = function(_) {
return arguments.length ? (curve = _, context != null && (output = curve(context)), line) : curve;
};
line.context = function(_) {
return arguments.length ? (_ == null ? context = output = null : output = curve(context = _), line) : context;
};
return line;
};
function sign(x) {
return x < 0 ? -1 : 1;
}
// Calculate the slopes of the tangents (Hermite-type interpolation) based on
// the following paper: Steffen, M. 1990. A Simple Method for Monotonic
// Interpolation in One Dimension. Astronomy and Astrophysics, Vol. 239, NO.
// NOV(II), P. 443, 1990.
function slope3(that, x2, y2) {
var h0 = that._x1 - that._x0,
h1 = x2 - that._x1,
s0 = (that._y1 - that._y0) / (h0 || h1 < 0 && -0),
s1 = (y2 - that._y1) / (h1 || h0 < 0 && -0),
p = (s0 * h1 + s1 * h0) / (h0 + h1);
return (sign(s0) + sign(s1)) * Math.min(Math.abs(s0), Math.abs(s1), 0.5 * Math.abs(p)) || 0;
}
// Calculate a one-sided slope.
function slope2(that, t) {
var h = that._x1 - that._x0;
return h ? (3 * (that._y1 - that._y0) / h - t) / 2 : t;
}
// According to https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Representations
// "you can express cubic Hermite interpolation in terms of cubic Bézier curves
// with respect to the four values p0, p0 + m0 / 3, p1 - m1 / 3, p1".
function point$4(that, t0, t1) {
var x0 = that._x0,
y0 = that._y0,
x1 = that._x1,
y1 = that._y1,
dx = (x1 - x0) / 3;
that._context.bezierCurveTo(x0 + dx, y0 + dx * t0, x1 - dx, y1 - dx * t1, x1, y1);
}
function MonotoneX(context) {
this._context = context;
}
MonotoneX.prototype = {
areaStart: function() {
this._line = 0;
},
areaEnd: function() {
this._line = NaN;
},
lineStart: function() {
this._x0 = this._x1 =
this._y0 = this._y1 =
this._t0 = NaN;
this._point = 0;
},
lineEnd: function() {
switch (this._point) {
case 2: this._context.lineTo(this._x1, this._y1); break;
case 3: point$4(this, this._t0, slope2(this, this._t0)); break;
}
if (this._line || (this._line !== 0 && this._point === 1)) this._context.closePath();
this._line = 1 - this._line;
},
point: function(x, y) {
var t1 = NaN;
x = +x, y = +y;
if (x === this._x1 && y === this._y1) return; // Ignore coincident points.
switch (this._point) {
case 0: this._point = 1; this._line ? this._context.lineTo(x, y) : this._context.moveTo(x, y); break;
case 1: this._point = 2; break;
case 2: this._point = 3; point$4(this, slope2(this, t1 = slope3(this, x, y)), t1); break;
default: point$4(this, this._t0, t1 = slope3(this, x, y)); break;
}
this._x0 = this._x1, this._x1 = x;
this._y0 = this._y1, this._y1 = y;
this._t0 = t1;
}
};
function MonotoneY(context) {
this._context = new ReflectContext(context);
}
(MonotoneY.prototype = Object.create(MonotoneX.prototype)).point = function(x, y) {
MonotoneX.prototype.point.call(this, y, x);
};
function ReflectContext(context) {
this._context = context;
}
ReflectContext.prototype = {
moveTo: function(x, y) { this._context.moveTo(y, x); },
closePath: function() { this._context.closePath(); },
lineTo: function(x, y) { this._context.lineTo(y, x); },
bezierCurveTo: function(x1, y1, x2, y2, x, y) { this._context.bezierCurveTo(y1, x1, y2, x2, y, x); }
};
const eps = 0.0001;
const packSquares = (values, maxValue) => {
const max = Math.sqrt(maxValue);
const square0Size = Math.sqrt(values[0]) / max;
const squares = [{ x: 0, y: 0, width: square0Size, height: square0Size }];
// This is const, but only the ref. We splice the array as we
// iterate through the data points, thus changing the value.
const outline = [[0, 0], [square0Size, 0], [square0Size, square0Size], [0, square0Size]];
// Naming conventions:
//
// - v{0,1,2,3}: The four vertices of the square which will be inserted into the result list.
// - n{1,2,...}: Vertices which are used to calculate the direction.
// - d{1,2,...}: Normalised vectors in the direction vX -> nY
values.slice(1).forEach(value => {
const size = Math.sqrt(value) / max;
const centroid = polygonCentroid(outline);
// The closest vertex to that centroid is used as one of the vertices
// for the current rectangle. Saved as the index into the 'outline'
// list because we need its neighbours.
const v0Index = outline.reduce((a, v, i) => distance(v, centroid) < distance(outline[a], centroid) ? i : a, 0);
const v0 = outline[v0Index];
// Now we need to decide into which direction the rectangle grows. We
// can pick one side arbitrarily towards one of the neighbours of the
// closest index.
// The n1 vertex is the /direction/ into which the side grows.
// We still need to do some vector arithmetic to determine where the
// actual vertex needs to be.
const n1Index = (v0Index + 1) % outline.length;
const n1 = outline[n1Index];
// The unit vector from v0 in the direction towards n1.
const d1 = normalize(subtract(n1, v0));
// The second vertex of the rectangle.
const v1 = add(v0, multiply(d1, [size, size]));
// The third vertex is from 'v0' along the line towards
// the other (previous) neighbour. But we may need to invert the direction so
// that the vector points away from the centroid.
//
// We compute the direction, and add that the 'v0'. If the
// result ends up on the same side of the line between 'v0'
// and 'v1', it means the point is on the wrong side and we have to
// invert the direction.
//
// In the degenerate case where the direction from v0 to n2 is parallel
// to d1, rotate the vector 90 degrees to the right. This works because
// the outline is always counter-clockwise (I think).
const n2Index = (v0Index - 1 + outline.length) % outline.length;
const n2 = outline[n2Index];
// The vector along the line between v0 and v2. We may have to invert
// it if it is rotated by 180 degrees.
const d2 = (() => {
// The unit vector from v0 towards n2.
const d = normalize(subtract(n2, v0));
const dot2v = dot2(d, d1);
if (Math.abs(dot2v) < eps) {
return d;
}
else if (dot2v < 0) {
return [d[1], -d[0]];
}
else {
return d;
}
})();
// Direction from 'v0' to the centroid.
const centroidDirection = subtract(centroid, v0);
// For v2 we have two choices where to go. Use the direction which results in
// the vertex being outside of the outline.
const v2_a = add(v0, multiply(negate(d2), [size, size]));
const v2_b = add(v0, multiply(d2, [size, size]));
const d3_fwd = pointIsInside(v2_a, outline);
const v2 = d3_fwd ? v2_b : v2_a;
// Push the square into the result list.
squares.push({
x: Math.min(Math.min(v0[0], v1[0]), v2[0]),
y: Math.min(Math.min(v0[1], v1[1]), v2[1]),
width: size,
height: size
});
// Update the outline.
const v4 = add(add(v0, subtract(v2, v0)), subtract(v1, v0));
const toInsert = [distance(v2, n2) < eps ? undefined : v2,
v4,
distance(v1, n1) < eps ? undefined : v1
].filter(x => x !== undefined);
if (!d3_fwd) {
outline.splice(v0Index + 1, 0, ...toInsert);
}
else {
outline.splice(v0Index, 1, ...toInsert);
}
});
return {
squares,
outline,
centroid: polygonCentroid(outline),
extent: polygonExtent(outline),
};
};
const polygonExtent = (vertices) => {
const { min, max } = vertices.reduce(({ min, max }, v) => ({
min: min2(min, v),
max: max2(max, v),
}), { min: [999, 999], max: [-999, -999] });
return {
x: min[0],
y: min[1],
width: max[0] - min[0],
height: max[1] - min[1],
};
};
// https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
const polygonCentroid = (vertices) => {
const { A, cx, cy } = vertices.reduce(({ A, cx, cy }, [x1, y1], i) => {
const [x2, y2] = vertices[(i + 1) % vertices.length];
const f = (x1 * y2 - x2 * y1);
return {
A: A + f,
cx: cx + (x1 + x2) * f,
cy: cy + (y1 + y2) * f,
};
}, { A: 0, cx: 0, cy: 0 });
return multiply([1 / (6 * 0.5 * A), 1 / (6 * 0.5 * A)], [cx, cy]);
};
const pointIsInside = ([x, y], vs) => {
let inside = false;
for (let i = 0, j = vs.length - 1; i < vs.length; j = i++) {
const [xi, yi] = vs[i];
const [xj, yj] = vs[j];
const intersect = ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect)
inside = !inside;
}
return inside;
};
// ----------------------------------------------------------------------------
// Vec2
const distance = ([x1, y1], [x2, y2]) => Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
const subtract = (a, b) => [a[0] - b[0], a[1] - b[1]];
const normalize = ([x, y]) => {
let len = x * x + y * y;
if (len > 0) {
len = 1 / Math.sqrt(len);
return [x * len, y * len];
}
else {
return [0, 0];
}
};
const multiply = (a, b) => [a[0] * b[0], a[1] * b[1]];
const add = (a, b) => [a[0] + b[0], a[1] + b[1]];
const dot2 = (a, b) => a[0] * b[0] + a[1] * b[1];
const negate = (a) => [-a[0], -a[1]];
const min2 = (a, b) => [Math.min(a[0], b[0]), Math.min(a[1], b[1])];
const max2 = (a, b) => [Math.max(a[0], b[0]), Math.max(a[1], b[1])];
const svg = select('svg');
const render = (data, width, height) => {
svg.attr('width', width).attr('height', height);
const svgNode = svg.node(0);
while (svgNode.children.length > 0) {
svgNode.removeChild(svgNode.children[0]);
}
if (data.length === 0) {
return;
}
data.sort((a, b) => b - a);
const result = packSquares(data, Math.max.apply(Math, data));
// scale: Make it so that the diagonal fits into the container.
const diag = Math.sqrt(Math.pow(result.extent.width, 2) + Math.pow(result.extent.height, 2));
const sx = width / diag;
const sy = height / diag;
const scaleFactor = Math.min(sx, sy);
// Rotation needs to be between 0 and PI/4. Otherwise the topY/leftX formula
// will not work.
const rot = Math.PI / 4;
// translation: center the thing inside the container. The rotation is 90deg
// clock-wise. Hence the rotation matrix is [[0,1],[-1,0]]
const topY = Math.sin(rot) * result.extent.x + (Math.cos(rot)) * (result.extent.y);
const leftX = Math.cos(rot) * result.extent.x + (-Math.sin(rot)) * (result.extent.y + result.extent.height);
const dx = -leftX + ((width - diag * scaleFactor) / 2 / scaleFactor);
const dy = -topY + ((height - diag * scaleFactor) / 2 / scaleFactor);
const g = svg.selectAll('g.squares').data([1]).enter()
.append('g').attr('transform', `scale(${scaleFactor} ${scaleFactor}) translate(${dx} ${dy}) rotate(${rot * 180 / Math.PI} 0 0)`);
g.selectAll('circle.centroid').data([1]).enter()
.append('circle')
.attr('cx', result.centroid[0])
.attr('cy', result.centroid[1])
.attr('r', 4 / scaleFactor)
.attr('fill', 'rgba(0,30,120,.4)');
const closedOutline = result.outline.concat([result.outline[0]]);
g.selectAll('path.outline').data([1]).enter()
.append('path')
.attr('d', () => line()(closedOutline))
.attr('fill', 'none')
.attr('stroke', 'rgba(160,0,20,.3)')
.attr('stroke-width', 1 / scaleFactor);
g.selectAll('circle.outline-vertex').data(result.outline).enter()
.append('circle')
.attr('cx', x => x[0])
.attr('cy', x => x[1])
.attr('r', 2 / scaleFactor)
.attr('fill', 'rgba(160,0,20,.8)');
g.selectAll('rect.extent').data([1]).enter()
.append('rect')
.attr('x', result.extent.x)
.attr('y', result.extent.y)
.attr('width', result.extent.width)
.attr('height', result.extent.height)
.attr('fill', 'none')
.attr('stroke', 'rgba(60,160,0,.5)')
.attr('stroke-width', 1 / scaleFactor);
const offset = 3 / scaleFactor;
const rects = g.selectAll('path.rectangles')
.data(result.squares);
rects.enter().append('path')
.attr('d', ({ x, y, width, height }) => line()([
[(x) + offset, (y) + offset],
[(x + width) - offset, (y) + offset],
[(x + width) - offset, (y + height) - offset],
[(x) + offset, (y + height) - offset],
[(x) + offset, (y) + offset]
]))
.attr('fill', 'rgba(60,0,20,.08)')
.attr('stroke', 'rgba(60,0,20,.8)')
.attr('stroke-width', 1 / scaleFactor)
.on("mouseover", function () {
select(this)
.attr("fill", 'rgba(160,0,20,.16)');
})
.on("mouseout", function (d, i) {
select(this).attr("fill", function () {
return 'rgba(60,0,20,.08)';
});
});
// const labels = g.selectAll('text.label')
// .data(result.squares)
// const text = labels.enter()
// .append('g')
// .attr('transform', ({x, y, width, height}: Square) => `translate(${x + width / 2} ${y + height / 2}) rotate(${-rot * 180 / Math.PI} 0 0)`)
// .append('text')
// .attr('x', 0)
// .attr('y', 0)
// .attr('text-anchor', 'middle')
// .attr('font-size', `${16 / scaleFactor}px`)
// .attr('pointer-events', 'none');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', -14/scaleFactor)
// .text('Parent-child/');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', 6/scaleFactor)
// .text('parent-child-school');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', 26/scaleFactor)
// .text('programme');
};
const renderValue = (value) => {
const data = value.split(/,/)
.map(x => x.trim())
.map(x => parseFloat(x))
.filter(x => !isNaN(x) && x > 0);
render(data, window.innerWidth - 80, window.innerHeight - 80 - 40);
};
const input = document.querySelector('input');
const valueFromHash = window.location.hash.substring(1);
if (valueFromHash) {
input.value = valueFromHash;
}
renderValue(input.value);
input.addEventListener('keyup', () => {
renderValue(input.value);
window.location.hash = input.value;
}, true);
window.addEventListener('resize', () => {
renderValue(input.value);
});
}());
Raw
example.ts
import {select} from 'd3-selection';
import {line} from 'd3-shape';
import {Square, packSquares} from './index';
const svg = select('svg');
const render = (data, width, height) => {
svg.attr('width', width).attr('height', height);
const svgNode = (<any>svg).node(0);
while (svgNode.children.length > 0) { svgNode.removeChild(svgNode.children[0]); }
if (data.length === 0) {
return;
}
data.sort((a, b) => b - a);
const result = packSquares(data, Math.max.apply(Math, data));
// scale: Make it so that the diagonal fits into the container.
const diag = Math.sqrt(Math.pow(result.extent.width, 2) + Math.pow(result.extent.height, 2));
const sx = width / diag;
const sy = height / diag;
const scaleFactor = Math.min(sx, sy);
// Rotation needs to be between 0 and PI/4. Otherwise the topY/leftX formula
// will not work.
const rot = Math.PI/4;
// translation: center the thing inside the container. The rotation is 90deg
// clock-wise. Hence the rotation matrix is [[0,1],[-1,0]]
const topY = Math.sin(rot) * result.extent.x + (Math.cos(rot)) * (result.extent.y);
const leftX = Math.cos(rot) * result.extent.x + (-Math.sin(rot))*(result.extent.y + result.extent.height);
const dx = -leftX + ((width - diag * scaleFactor) / 2 / scaleFactor);
const dy = -topY + ((height - diag * scaleFactor) / 2 / scaleFactor);
const g = svg.selectAll('g.squares').data([1]).enter()
.append('g').attr('transform', `scale(${scaleFactor} ${scaleFactor}) translate(${dx} ${dy}) rotate(${rot * 180 / Math.PI} 0 0)`);
g.selectAll('circle.centroid').data([1]).enter()
.append('circle')
.attr('cx', result.centroid[0])
.attr('cy', result.centroid[1])
.attr('r', 4 / scaleFactor)
.attr('fill', 'rgba(0,30,120,.4)');
const closedOutline = result.outline.concat([result.outline[0]]);
g.selectAll('path.outline').data([1]).enter()
.append('path')
.attr('d', () => line()(closedOutline))
.attr('fill', 'none')
.attr('stroke', 'rgba(160,0,20,.3)')
.attr('stroke-width', 1 / scaleFactor);
g.selectAll('circle.outline-vertex').data(result.outline).enter()
.append('circle')
.attr('cx', x => x[0])
.attr('cy', x => x[1])
.attr('r', 2 / scaleFactor)
.attr('fill', 'rgba(160,0,20,.8)');
g.selectAll('rect.extent').data([1]).enter()
.append('rect')
.attr('x', result.extent.x)
.attr('y', result.extent.y)
.attr('width', result.extent.width)
.attr('height', result.extent.height)
.attr('fill', 'none')
.attr('stroke', 'rgba(60,160,0,.5)')
.attr('stroke-width', 1 / scaleFactor);
const offset = 3 / scaleFactor;
const rects = g.selectAll('path.rectangles')
.data(result.squares);
rects.enter().append('path')
.attr('d', ({x, y, width, height}: Square) => line()([
[(x) + offset, (y) + offset],
[(x + width) - offset, (y) + offset],
[(x + width) - offset, (y + height) - offset],
[(x) + offset, (y + height) - offset],
[(x) + offset, (y) + offset]
]))
.attr('fill', 'rgba(60,0,20,.08)')
.attr('stroke', 'rgba(60,0,20,.8)')
.attr('stroke-width', 1 / scaleFactor)
.on("mouseover", function() {
select(this)
.attr("fill", 'rgba(160,0,20,.16)');
})
.on("mouseout", function(d, i) {
select(this).attr("fill", function() {
return 'rgba(60,0,20,.08)'
});
});
// const labels = g.selectAll('text.label')
// .data(result.squares)
// const text = labels.enter()
// .append('g')
// .attr('transform', ({x, y, width, height}: Square) => `translate(${x + width / 2} ${y + height / 2}) rotate(${-rot * 180 / Math.PI} 0 0)`)
// .append('text')
// .attr('x', 0)
// .attr('y', 0)
// .attr('text-anchor', 'middle')
// .attr('font-size', `${16 / scaleFactor}px`)
// .attr('pointer-events', 'none');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', -14/scaleFactor)
// .text('Parent-child/');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', 6/scaleFactor)
// .text('parent-child-school');
// text.append('tspan')
// .attr('x', 0)
// .attr('y', 26/scaleFactor)
// .text('programme');
};
const renderValue = (value) => {
const data = value.split(/,/)
.map(x => x.trim())
.map(x => parseFloat(x))
.filter(x => !isNaN(x) && x > 0);
render(data, window.innerWidth - 80, window.innerHeight - 80 - 40);
};
const input = document.querySelector('input');
const valueFromHash = window.location.hash.substring(1);
if (valueFromHash) {
input.value = valueFromHash;
}
renderValue(input.value);
input.addEventListener('keyup', () => {
renderValue(input.value);
window.location.hash = input.value;
}, true);
window.addEventListener('resize', () => {
renderValue(input.value);
});
Raw
index.html
<html>
<head>
<title>Square Packing Example</title>
<style>
* { box-sizing: border-box; }
body { margin: 0; display: flex; justify-content: center; align-items: center; flex-direction: column; }
svg { display: block; box-shadow: 0 0 3px rgba(0,0,0,.4); }
input {font-size: 18px; line-height: 1; height: 32px; transition: all .2s; cursor: pointer; outline: none; border: 1px solid transparent; box-shadow: 0 0 3px rgba(0,0,0,.4); padding: 5px 8px; margin-bottom: 8px; display: block; width: calc(100% - 80px);}
input:hover {box-shadow: 0 0 5px rgba(140,0,0,.8);}
input:focus {box-shadow: 0 0 5px rgba(140,0,0,.8); border: 1px solid rgba(140,0,0,0.6);}
</style>
</head>
<body>
<input autofocus type="text" value="0.36, 0.36, 0.32, 0.22" />
<svg></svg>
<script src="./bundle.js"></script>
</body>
</html>
Raw
index.ts
// The Vec2/Vec3 data types are the same as in gl-matrix. But the functions
// (implemented at the bottom) are slightly different: They are all completely
// immutable. Meaning: gl-matrix functions take the 'out' parameter as the
// first argument, but our functions always return a new object. This is ok
// because we're not that performance sensitive.
export type Vec2 = [number, number];
export type Vec3 = [number, number, number];
export type Result = {
squares: Square[];
// ^ The individual squares. Has same length as the input array. The squares
// are sorted by size, with the largest first and the smallest last.
outline: Vec2[];
// ^ The exact outline around all the squares. You can use this to compute
// the extent of all the squares. Counter-clockwise (I think).
centroid: Vec2;
// ^ The centroid of the outline polygon. Provided mainly for debugging
// purposes, but you could use it for label placement. Note that the
// centroid is not the same as the center of the extent square, though
// they usually are very close.
extent: Square
// ^ The extent of all the squares. You can use this to compute the scale
// matrix if you want to fit the squares into a particular area.
}
// Each square is given as the x/y position of its top-left corner and
// width/height.
export type Square = {
x: number;
y: number;
width: number;
height: number;
};
const eps = 0.0001;
export const packSquares = (values: number[], maxValue: number): Result => {
const max = Math.sqrt(maxValue);
const square0Size = Math.sqrt(values[0]) / max;
const squares = [{x: 0, y: 0, width: square0Size, height: square0Size}];
// This is const, but only the ref. We splice the array as we
// iterate through the data points, thus changing the value.
const outline: Vec2[] = [[0, 0], [square0Size, 0], [square0Size, square0Size], [0, square0Size]];
// Naming conventions:
//
// - v{0,1,2,3}: The four vertices of the square which will be inserted into the result list.
// - n{1,2,...}: Vertices which are used to calculate the direction.
// - d{1,2,...}: Normalised vectors in the direction vX -> nY
values.slice(1).forEach(value => {
const size = Math.sqrt(value) / max;
const centroid = polygonCentroid(outline);
// The closest vertex to that centroid is used as one of the vertices
// for the current rectangle. Saved as the index into the 'outline'
// list because we need its neighbours.
const v0Index = outline.reduce((a, v, i) =>
distance(v, centroid) < distance(outline[a], centroid) ? i : a, 0);
const v0 = outline[v0Index];
// Now we need to decide into which direction the rectangle grows. We
// can pick one side arbitrarily towards one of the neighbours of the
// closest index.
// The n1 vertex is the /direction/ into which the side grows.
// We still need to do some vector arithmetic to determine where the
// actual vertex needs to be.
const n1Index = (v0Index + 1) % outline.length;
const n1 = outline[n1Index];
// The unit vector from v0 in the direction towards n1.
const d1 = normalize(subtract(n1, v0));
// The second vertex of the rectangle.
const v1 = add(v0, multiply(d1, [size, size]));
// The third vertex is from 'v0' along the line towards
// the other (previous) neighbour. But we may need to invert the direction so
// that the vector points away from the centroid.
//
// We compute the direction, and add that the 'v0'. If the
// result ends up on the same side of the line between 'v0'
// and 'v1', it means the point is on the wrong side and we have to
// invert the direction.
//
// In the degenerate case where the direction from v0 to n2 is parallel
// to d1, rotate the vector 90 degrees to the right. This works because
// the outline is always counter-clockwise (I think).
const n2Index = (v0Index - 1 + outline.length) % outline.length;
const n2 = outline[n2Index];
// The vector along the line between v0 and v2. We may have to invert
// it if it is rotated by 180 degrees.
const d2 = (() => {
// The unit vector from v0 towards n2.
const d = normalize(subtract(n2, v0));
const dot2v = dot2(d, d1);
if (Math.abs(dot2v) < eps) {
return d;
} else if (dot2v < 0) {
return <Vec2>[d[1], -d[0]]
} else {
return d;
}
})();
// Direction from 'v0' to the centroid.
const centroidDirection = subtract(centroid, v0);
// For v2 we have two choices where to go. Use the direction which results in
// the vertex being outside of the outline.
const v2_a = add(v0, multiply(negate(d2), [size, size]));
const v2_b = add(v0, multiply(d2, [size, size]));
const d3_fwd = pointIsInside(v2_a, outline);
const v2 = d3_fwd ? v2_b : v2_a;
// Push the square into the result list.
squares.push(<Square>{
x: Math.min(Math.min(v0[0], v1[0]), v2[0]),
y: Math.min(Math.min(v0[1], v1[1]), v2[1]),
width: size,
height: size
});
// Update the outline.
const v4 = add(add(v0, subtract(v2, v0)), subtract(v1, v0));
const toInsert: Vec2[] =
[ distance(v2, n2) < eps ? undefined : v2
, v4
, distance(v1, n1) < eps ? undefined : v1
].filter(x => x !== undefined);
if (!d3_fwd) {
outline.splice(v0Index + 1, 0, ...toInsert);
} else {
outline.splice(v0Index, 1, ...toInsert);
}
});
return {
squares,
outline,
centroid: polygonCentroid(outline),
extent: polygonExtent(outline),
};
};
const polygonExtent = (vertices: Vec2[]): Square => {
const {min, max} = vertices.reduce(({min, max}, v) => ({
min: min2(min, v),
max: max2(max, v),
}), {min: <Vec2>[999,999], max: <Vec2>[-999,-999]});
return {
x: min[0],
y: min[1],
width: max[0] - min[0],
height: max[1] - min[1],
};
};
// https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
const polygonCentroid = (vertices: Vec2[]): Vec2 => {
const {A, cx, cy} = vertices.reduce(({A, cx, cy}, [x1, y1], i) => {
const [x2, y2] = vertices[(i + 1) % vertices.length];
const f = (x1*y2 - x2*y1);
return {
A: A + f,
cx: cx + (x1 + x2) * f,
cy: cy + (y1 + y2) * f,
};
}, {A: 0, cx: 0, cy: 0});
return multiply([1 / (6 * 0.5*A), 1 / (6 * 0.5*A)], [cx, cy]);
};
const pointIsInside = ([x,y]: Vec2, vs: Vec2[]): boolean => {
let inside = false;
for (let i = 0, j = vs.length - 1; i < vs.length; j = i++) {
const [xi, yi] = vs[i];
const [xj, yj] = vs[j];
const intersect = ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect) inside = !inside;
}
return inside;
};
// ----------------------------------------------------------------------------
// Vec2
const distance = ([x1, y1]: Vec2, [x2, y2]: Vec2): number =>
Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
const subtract = (a: Vec2, b: Vec2): Vec2 =>
[a[0] - b[0], a[1] - b[1]];
const normalize = ([x,y]: Vec2): Vec2 => {
let len = x*x + y*y;
if (len > 0) {
len = 1 / Math.sqrt(len);
return [x * len, y * len];
} else {
return [0,0];
}
};
const multiply = (a: Vec2, b: Vec2): Vec2 =>
[a[0] * b[0], a[1] * b[1]];
const add = (a: Vec2, b: Vec2): Vec2 =>
[a[0] + b[0], a[1] + b[1]];
const dot2 = (a: Vec2, b: Vec2): number =>
a[0] * b[0] + a[1] * b[1];
const cross = (a: Vec2, b: Vec2): Vec3 =>
[0, 0, a[0] * b[1] - a[1] * b[0]];
const negate = (a: Vec2): Vec2 =>
[-a[0], -a[1]];
const min2 = (a: Vec2, b: Vec2): Vec2 =>
[Math.min(a[0], b[0]), Math.min(a[1], b[1])];
const max2 = (a: Vec2, b: Vec2): Vec2 =>
[Math.max(a[0], b[0]), Math.max(a[1], b[1])];
const colinear = (a: Vec2, b: Vec2, c: Vec2): boolean =>
Math.abs((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) < eps;
// ----------------------------------------------------------------------------
// Vec3
const dot3 = (a: Vec3, b: Vec3): number =>
a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
Raw
LICENSE
MIT License
Copyright (c) 2017 Tomas Carnecky
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
Raw
package.json
{
"name": "simple-square-packing",
"version": "1.0.0",
"description": "Simple Square Packing",
"main": "index.js",
"types": "index.d.ts",
"scripts": {
"tsc": "tsc",
"tsc:watch": "tsc --watch",
"bundle": "rollup -c --output bundle.js"
},
"author": "Tomas Carnecky <tomas.carnecky@gmail.com>",
"license": "MIT",
"devDependencies": {
"@types/d3": "^4.4.1",
"@types/d3-shape": "^1.0.7",
"d3-selection": "^1.0.3",
"d3-shape": "^1.0.4",
"rollup": "0.41.4",
"rollup-plugin-commonjs": "^7.0.0",
"rollup-plugin-node-resolve": "^2.0.0",
"typescript": "2.1.5"
}
}
Raw
rollup.config.js
import nodeResolve from 'rollup-plugin-node-resolve';
export default {
entry: 'example.js',
plugins: [ nodeResolve({jsnext: true, main: true}) ],
format: 'iife',
moduleName: 'm',
};
Raw
tsconfig.json
{
"compilerOptions": {
"target": "es6",
"declaration": true
},
"files": [
"index.ts",
"example.ts"
]
}
Raw
yarn.lock
# THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY.
# yarn lockfile v1
"@types/d3-array@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-array/-/d3-array-1.0.6.tgz#f3c02ed26f2921fd018ad7c1f8cb4ba841557c89"
"@types/d3-axis@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-axis/-/d3-axis-1.0.6.tgz#6b46db3facebb6eff5b957c4d2ba69b90239ce02"
dependencies:
"@types/d3-selection" "*"
"@types/d3-brush@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-brush/-/d3-brush-1.0.6.tgz#c755ce79944f8d205dcea3771c91a1732c726d88"
dependencies:
"@types/d3-selection" "*"
"@types/d3-chord@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-chord/-/d3-chord-1.0.5.tgz#48ed6c1415043aabc3514a56075f78766e575492"
"@types/d3-collection@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-collection/-/d3-collection-1.0.4.tgz#19b1eede200ba5bdafb4c8af19afe32c2de7a660"
"@types/d3-color@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-color/-/d3-color-1.0.4.tgz#f0e1b64162fea2f932007fb966c26cc8aff3a47d"
"@types/d3-dispatch@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-dispatch/-/d3-dispatch-1.0.4.tgz#91b8de6198053efc46788ad5f27182bcc42335b5"
"@types/d3-drag@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-drag/-/d3-drag-1.0.6.tgz#38b4130accd97b29269dc5899d59f87bc55eab7d"
dependencies:
"@types/d3-selection" "*"
"@types/d3-dsv@*":
version "1.0.29"
resolved "https://registry.yarnpkg.com/@types/d3-dsv/-/d3-dsv-1.0.29.tgz#06c92b01ec32b5c457701d520d5bac6358b1fb0f"
"@types/d3-ease@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-ease/-/d3-ease-1.0.5.tgz#cae0c4a6dd39be58cc1c94ad08bd991c2d932400"
"@types/d3-force@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-force/-/d3-force-1.0.6.tgz#cadf5c5591e5d554c93ddb1c359d2b0daa83abca"
"@types/d3-format@*":
version "1.0.7"
resolved "https://registry.yarnpkg.com/@types/d3-format/-/d3-format-1.0.7.tgz#4f40de7a19def868f3811cc4ef5e37e3ff0546a3"
"@types/d3-geo@*":
version "1.4.0"
resolved "https://registry.yarnpkg.com/@types/d3-geo/-/d3-geo-1.4.0.tgz#7996fca86b1d478f9c1996b762169340b4d1664a"
dependencies:
"@types/geojson" "*"
"@types/d3-hierarchy@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-hierarchy/-/d3-hierarchy-1.0.4.tgz#9857760dc276523dd65f6ecf848b78486925daa8"
"@types/d3-interpolate@*":
version "1.1.5"
resolved "https://registry.yarnpkg.com/@types/d3-interpolate/-/d3-interpolate-1.1.5.tgz#956485bb0f75c07b49b33f7b44a35cfa9f7f4f46"
dependencies:
"@types/d3-color" "*"
"@types/d3-path@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-path/-/d3-path-1.0.5.tgz#84e54043410048a188c03100592c2b9e417664f7"
"@types/d3-polygon@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-polygon/-/d3-polygon-1.0.4.tgz#44aa10bf081c8e87642827feb6285e8280c3eee4"
"@types/d3-quadtree@*":
version "1.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-quadtree/-/d3-quadtree-1.0.4.tgz#fb164e00a82f3105b810afad757804664742c049"
"@types/d3-queue@*":
version "3.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-queue/-/d3-queue-3.0.4.tgz#a86b6d55e307d363aedd5153d8f1117793df6710"
"@types/d3-random@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-random/-/d3-random-1.0.5.tgz#e1d212f503376899f8a290ebae9cbf606eac856d"
"@types/d3-request@*":
version "1.0.1"
resolved "https://registry.yarnpkg.com/@types/d3-request/-/d3-request-1.0.1.tgz#b3e8b79c97618b396814ee8931a318efe9a51c64"
dependencies:
"@types/d3-dsv" "*"
"@types/d3-scale@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-scale/-/d3-scale-1.0.6.tgz#1a47ee5d333a5d68cc858c65a47d9fd699f48573"
dependencies:
"@types/d3-time" "*"
"@types/d3-selection@*":
version "1.0.9"
resolved "https://registry.yarnpkg.com/@types/d3-selection/-/d3-selection-1.0.9.tgz#9065f95f931468eb2a5ad5ba57531a8bb3c1e1f1"
"@types/d3-shape@*", "@types/d3-shape@^1.0.7":
version "1.0.7"
resolved "https://registry.yarnpkg.com/@types/d3-shape/-/d3-shape-1.0.7.tgz#55e70cfc86818bde435ce014f78b382e4d22f3e4"
dependencies:
"@types/d3-path" "*"
"@types/d3-time-format@*":
version "2.0.4"
resolved "https://registry.yarnpkg.com/@types/d3-time-format/-/d3-time-format-2.0.4.tgz#3f4749652f347bce4b1c405053b0cfc5154cf537"
"@types/d3-time@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-time/-/d3-time-1.0.5.tgz#c86f1f43dc2b22d3c6c75cd1734effeda74213e5"
"@types/d3-timer@*":
version "1.0.5"
resolved "https://registry.yarnpkg.com/@types/d3-timer/-/d3-timer-1.0.5.tgz#aad31e6aa185a6440f544d9167ef3194667d7f1e"
"@types/d3-transition@*":
version "1.0.6"
resolved "https://registry.yarnpkg.com/@types/d3-transition/-/d3-transition-1.0.6.tgz#f4cc5294bfe61f6f598c4c6eb765e60c54e543ea"
dependencies:
"@types/d3-selection" "*"
"@types/d3-voronoi@*":
version "1.1.5"
resolved "https://registry.yarnpkg.com/@types/d3-voronoi/-/d3-voronoi-1.1.5.tgz#67d03acb2d56006bb202c20cee1b8d5ad9fe0461"
"@types/d3-zoom@*":
version "1.1.0"
resolved "https://registry.yarnpkg.com/@types/d3-zoom/-/d3-zoom-1.1.0.tgz#2807678cb9ff44cff70f52a6c72c6b95c303dd88"
dependencies:
"@types/d3-interpolate" "*"
"@types/d3-selection" "*"
"@types/d3@^4.4.1":
version "4.4.1"
resolved "https://registry.yarnpkg.com/@types/d3/-/d3-4.4.1.tgz#7673792ee00bbf471d466a6cc9998dae0172d0bd"
dependencies:
"@types/d3-array" "*"
"@types/d3-axis" "*"
"@types/d3-brush" "*"
"@types/d3-chord" "*"
"@types/d3-collection" "*"
"@types/d3-color" "*"
"@types/d3-dispatch" "*"
"@types/d3-drag" "*"
"@types/d3-dsv" "*"
"@types/d3-ease" "*"
"@types/d3-force" "*"
"@types/d3-format" "*"
"@types/d3-geo" "*"
"@types/d3-hierarchy" "*"
"@types/d3-interpolate" "*"
"@types/d3-path" "*"
"@types/d3-polygon" "*"
"@types/d3-quadtree" "*"
"@types/d3-queue" "*"
"@types/d3-random" "*"
"@types/d3-request" "*"
"@types/d3-scale" "*"
"@types/d3-selection" "*"
"@types/d3-shape" "*"
"@types/d3-time" "*"
"@types/d3-time-format" "*"
"@types/d3-timer" "*"
"@types/d3-transition" "*"
"@types/d3-voronoi" "*"
"@types/d3-zoom" "*"
"@types/geojson@*":
version "0.0.32"
resolved "https://registry.yarnpkg.com/@types/geojson/-/geojson-0.0.32.tgz#1571eeaf045337b242852885f08d9a945e1cc940"
acorn@^4.0.1:
version "4.0.4"
resolved "https://registry.yarnpkg.com/acorn/-/acorn-4.0.4.tgz#17a8d6a7a6c4ef538b814ec9abac2779293bf30a"
balanced-match@^0.4.1:
version "0.4.2"
resolved "https://registry.yarnpkg.com/balanced-match/-/balanced-match-0.4.2.tgz#cb3f3e3c732dc0f01ee70b403f302e61d7709838"
brace-expansion@^1.0.0:
version "1.1.6"
resolved "https://registry.yarnpkg.com/brace-expansion/-/brace-expansion-1.1.6.tgz#7197d7eaa9b87e648390ea61fc66c84427420df9"
dependencies:
balanced-match "^0.4.1"
concat-map "0.0.1"
browser-resolve@^1.11.0:
version "1.11.2"
resolved "https://registry.yarnpkg.com/browser-resolve/-/browser-resolve-1.11.2.tgz#8ff09b0a2c421718a1051c260b32e48f442938ce"
dependencies:
resolve "1.1.7"
builtin-modules@^1.1.0:
version "1.1.1"
resolved "https://registry.yarnpkg.com/builtin-modules/-/builtin-modules-1.1.1.tgz#270f076c5a72c02f5b65a47df94c5fe3a278892f"
concat-map@0.0.1:
version "0.0.1"
resolved "https://registry.yarnpkg.com/concat-map/-/concat-map-0.0.1.tgz#d8a96bd77fd68df7793a73036a3ba0d5405d477b"
d3-path@1:
version "1.0.3"
resolved "https://registry.yarnpkg.com/d3-path/-/d3-path-1.0.3.tgz#60103d0dea9a6cd6ca58de86c6d56724002d3fde"
d3-selection@^1.0.3:
version "1.0.3"
resolved "https://registry.yarnpkg.com/d3-selection/-/d3-selection-1.0.3.tgz#e63e51416172427854c1bcdfa066eb5fe872c108"
d3-shape@^1.0.4:
version "1.0.4"
resolved "https://registry.yarnpkg.com/d3-shape/-/d3-shape-1.0.4.tgz#145ee100ccbec42f8e3f1996cd05c786f79fe1c6"
dependencies:
d3-path "1"
estree-walker@^0.2.1:
version "0.2.1"
resolved "https://registry.yarnpkg.com/estree-walker/-/estree-walker-0.2.1.tgz#bdafe8095383d8414d5dc2ecf4c9173b6db9412e"
estree-walker@^0.3.0:
version "0.3.0"
resolved "https://registry.yarnpkg.com/estree-walker/-/estree-walker-0.3.0.tgz#f67ca8f57b9ed66d886af816c099c779b315d4db"
magic-string@^0.19.0:
version "0.19.0"
resolved "https://registry.yarnpkg.com/magic-string/-/magic-string-0.19.0.tgz#198948217254e3e0b93080e01146b7c73b2a06b2"
dependencies:
vlq "^0.2.1"
minimatch@^3.0.2:
version "3.0.3"
resolved "https://registry.yarnpkg.com/minimatch/-/minimatch-3.0.3.tgz#2a4e4090b96b2db06a9d7df01055a62a77c9b774"
dependencies:
brace-expansion "^1.0.0"
resolve@1.1.7:
version "1.1.7"
resolved "https://registry.yarnpkg.com/resolve/-/resolve-1.1.7.tgz#203114d82ad2c5ed9e8e0411b3932875e889e97b"
resolve@^1.1.6, resolve@^1.1.7:
version "1.2.0"
resolved "https://registry.yarnpkg.com/resolve/-/resolve-1.2.0.tgz#9589c3f2f6149d1417a40becc1663db6ec6bc26c"
rollup-plugin-commonjs@^7.0.0:
version "7.0.0"
resolved "https://registry.yarnpkg.com/rollup-plugin-commonjs/-/rollup-plugin-commonjs-7.0.0.tgz#510762d5c423c761cd16d8e8451715b39f0ceb08"
dependencies:
acorn "^4.0.1"
estree-walker "^0.3.0"
magic-string "^0.19.0"
resolve "^1.1.7"
rollup-pluginutils "^1.5.1"
rollup-plugin-node-resolve@^2.0.0:
version "2.0.0"
resolved "https://registry.yarnpkg.com/rollup-plugin-node-resolve/-/rollup-plugin-node-resolve-2.0.0.tgz#07e0ae94ac002a3ea36e8f33ca121d9f836b1309"
dependencies:
browser-resolve "^1.11.0"
builtin-modules "^1.1.0"
resolve "^1.1.6"
rollup-pluginutils@^1.5.1:
version "1.5.2"
resolved "https://registry.yarnpkg.com/rollup-pluginutils/-/rollup-pluginutils-1.5.2.tgz#1e156e778f94b7255bfa1b3d0178be8f5c552408"
dependencies:
estree-walker "^0.2.1"
minimatch "^3.0.2"
rollup@0.41.4:
version "0.41.4"
resolved "https://registry.yarnpkg.com/rollup/-/rollup-0.41.4.tgz#a970580176329f9ead86854d7fd4c46de752aef8"
dependencies:
source-map-support "^0.4.0"
source-map-support@^0.4.0:
version "0.4.6"
resolved "https://registry.yarnpkg.com/source-map-support/-/source-map-support-0.4.6.tgz#32552aa64b458392a85eab3b0b5ee61527167aeb"
dependencies:
source-map "^0.5.3"
source-map@^0.5.3:
version "0.5.6"
resolved "https://registry.yarnpkg.com/source-map/-/source-map-0.5.6.tgz#75ce38f52bf0733c5a7f0c118d81334a2bb5f412"
typescript@2.1.5:
version "2.1.5"
resolved "https://registry.yarnpkg.com/typescript/-/typescript-2.1.5.tgz#6fe9479e00e01855247cea216e7561bafcdbcd4a"
vlq@^0.2.1:
version "0.2.1"
resolved "https://registry.yarnpkg.com/vlq/-/vlq-0.2.1.tgz#14439d711891e682535467f8587c5630e4222a6c"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment