Using a Capacity Constrained Point Distribution to display a picture of an American hero.
This is a variant of the original algorithm by Michael Balzer, Thomas Schlömer & Oliver Deussen (University of Konstanz, Germany, 2009), in which I use a Voronoi Diagram to create a topology of the current sites, and only swap the points between neighbouring sites (and neighbours of neighbours). It appears to be much faster than the original algorithm.
See also https://seenthis.net/messages/619204 for an application in cartography.
Note to self: do not edit on BlockBuilder
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.polygons {
fill: none;
stroke: #333;
}
canvas {
display: none;
}
</style>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
var img = new Image();
img.src = 'snowden.jpg';
img.onload = function () {
draw(this);
};
function draw(img) {
var canvas = d3.select('body')
.append('canvas')
.attr('width', img.width)
.attr('height', img.height)
.node();
var ctx = canvas.getContext('2d');
ctx.drawImage(img, 0, 0);
var imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
var data = imageData.data;
var height = 500,
width = 960;
var svg = d3.select("body")
.append('svg')
.attr('width', width)
.attr('height', height);
var points = [];
var factor = height / canvas.height;
for (var i = 0; i < data.length; i += 4) {
if (Math.random() > (data[i] + data[i + 1] + data[i + 2]) / (3 * 256)) {
var y = Math.floor(i / 4 / canvas.width),
x = (i / 4) - y * canvas.width;
points.push([x * factor, y * factor]);
}
}
const capacity = 14;
const npoints = Math.floor(points.length / capacity);
var sites = d3.range(npoints)
.map(function (d) {
var p = points[Math.floor(Math.random() * points.length)];
p.index = d;
return p;
});
var voronoi = d3.voronoi().size([width, height]),
diagram = voronoi(sites);
var polygon = svg.append("g")
.attr("class", "polygons")
.selectAll("path")
.data(diagram.polygons())
.enter().append("path")
.attr('stroke-opacity', 0.1);
function distance2(a, b) {
var dx = a[0] - b[0],
dy = a[1] - b[1];
return /*Math.sqrt*/ (dx * dx + dy * dy);
}
var calc = 0,
iterations = 0;
function iterate() {
var swaps = 0;
iterations++;
var links = new Array(sites.length);
diagram.links().forEach(function (l) {
var ext = d3.extent([l.source.index, l.target.index]),
i = ext[0],
j = ext[1];
if (!links[i]) links[i] = [j];
else links[i].push(j);
});
for (var i in links) {
var l = links[i];
/* if (false) */
links[i] = d3.merge([links[i]].concat(links[i].map(function (j) {
return links[j] || [];
})));
l.forEach(function (j) {
var Hi = [],
Hj = [],
k, ki, kj;
for (k = 0; k < capacity; k++) {
Hi.push(distance2(points[i * capacity + k], sites[j]) - distance2(points[i * capacity + k], sites[i]));
Hj.push(distance2(points[j * capacity + k], sites[i]) - distance2(points[j * capacity + k], sites[j]));
calc++;
}
while (Hi.length > 0 && Hj.length > 0 && ((ki = d3.scan(Hi)) || true) && ((kj = d3.scan(Hj)) || true) && (Hi[ki] + Hj[kj] < 0)) {
swaps++;
var temp = points[i * capacity + ki];
points[i * capacity + ki] = points[j * capacity + kj];
points[j * capacity + kj] = temp;
Hi = Hi.slice(0, ki).concat(Hi.slice(ki + 1));
Hj = Hj.slice(0, kj).concat(Hj.slice(kj + 1));
}
});
}
return swaps;
}
var site = svg.selectAll('circle')
.data(sites)
.enter()
.append('circle')
.attr('r', 1.5)
.attr('fill', '#333');
var lastswaps = null;
var interval = d3.interval(function () {
var swaps = iterate();
svg.selectAll('circle')
.data(sites)
.attr('transform', function (d) {
return 'translate(' + d + ')';
});
svg.selectAll('rect')
.data(points)
.attr('transform', function (d) {
return 'translate(' + d + ')';
});
diagram = voronoi(sites);
polygon = polygon.data(diagram.polygons())
.attr("d", function (d) {
return d ? "M" + d.join("L") + "Z" : null;
});
sites = sites.map(function (site, i) {
var pts = points.slice(i * capacity, i * capacity + capacity);
site[0] = d3.mean(pts.map(function (d) {
return d[0];
}));
site[1] = d3.mean(pts.map(function (d) {
return d[1];
}));
return site;
});
console.log("" + swaps + " swaps, " + calc + " distances computed");
if (swaps == lastswaps && swaps < 300) {
console.log("stabilized after " + iterations + " iterations.")
interval.stop();
polygon
.transition()
.duration(2000)
.attr('stroke-opacity', 0.05);
site
.transition()
.duration(2000)
.attr('fill', 'black');
}
lastswaps = swaps;
})
}
</script>
���� JFIF H H �� C P7<F<2PFAFZUP_xȂxnnx��������������������������������������������� CUZZxix낂��������������������������������������������������������� TX" �� �� 3 !1AQaq"��2B���3��#Rbr���� �� �� ? � W<�\��������1� �9er��檚� � ��n��
�馁 ݝ��XJ kŝ��-]�k�g�Ze.V_e����y�ao��-����`g×_9|ƀ ���z�[��o���yLp�/�e��� L�ۗ�G�=��pK��x���K�����q�j-1,��ZpGOI�'Z�b�GH9�R��u�[�9 L���Γ������N9c���u�{�?xe��~@�� �����7g������rj^�� [r�=I:o�����ve�����c.��@����Z����'{���N�׃��Ut�5���H�ZM h�@B4�
�,�R��y8�R�pe��b����-��������ik,��e;L��-��x�ܛ��zxެe�����~K��2�}�
@ NKq��f����7�3;r�-���q��b��E-��c�������{�Ϗ�g�h����a (TU��WH����(8�Fk)��Ye��͎�g� �Y~��75�~\�k����y\yz{�� _ @<�K��ͬ�sv��}Y�eu�]���ۯ�:"�X�Ţ�`�� l6 ��n_ "�Y�U��:s�C9��ύ�
auw��M=5���{�l����5ߴ�+��l��X % ����2�Vmy��{J��=��wO�ӏ��L'e��Jv��H�>{.�}h:v��� �wիc���`u�a�&��k.�/�v]��Ϭ�Z�y}F8�yg��e�����Po}E�ʓ�,s�=��*tY;���f�Z�=Ny�$�}[L�n��ˏN�K�3�/x����,�����W��aφ�E��uK.���LJ ˔�w�S�Y���ƴ�<n\o�W��M�z��T�˫��b� 7�a���ws�Y��\�5x!��`ߋ��:� K�7�K͌�-���Ygd���;ٿ�������[{֖[�p��s���k��ﶾ�N?��r_��n��:�g�v�\��{�|���'�'.~,?�n�y�G��c��~����e{��:�3�����DN;$�>����?6~�9�y߶-8x�%��c�����S��<x����9~�a͖M�ϖܮ�w�AߎS+���I��xr�k�k��r��pUz�:����81�vrq�81�y�e<����=>�
�5e�� ���� \�����FS�+>����w[��@�i:���ޯ���>]�7����8��w<���c3Ǫ�o��1��H��W��<m�P������>�.�Ŗ|����E8��>�����~]_0~D��������]�Λ����fyn߀s��������YỾ��/�q�9��5?�>�uer�1����1����Ǔ,��ZB��nS��c�.,3�e�~ݧ���'%� �/���W�' �3X�NZ�,ܬ��]��苇&3�[?�q˹2���&79$[<y��V���L���Æ�����e��ںu>T�%���~��Ŏ���nZ�M���<.R�m�(��c�7,����&<s5��v�;ώV�]�O@ o[�s���^�e�w�+��1�e��ta��9�k5�Y��Y���X��91��e۰8����7r^�2��ܛg��=y�57�;$�9r����V��oͭ2�\8�>۠�m֪����'oV���0�����kmO�ǧ��t��.��m�h��M�+Pe��K/��9�.�� ��kgv|�L��3���~S�{3�e;U��m��GN�{����&M]�sS'5��&\s�n��?��=Z�TN�_���w�ߕ1�),��� ���tz���v��;�c�m��[��\s��߅�?��9�{�{��S�;1⟋s�<zk�v�q��] k��T����-�~��~�H��I�}�(�|�DI&?P0]Lj�2SVM���+�$�Al{Ŵ�]�pF�bʂ�V�Y\�j���w����S̉�h�Y,����q�o��y�7,���w�r�4 �����](�uMPy���ل�c�,z�X�6|7��y��WM���睫n;w��F�iL,�ఈ�W��~���v�̤������㝗�<|�}���I����+�t����s��U|x�~��r��u����]��Uj�Z�d�ճ@��Z�g,���\�����r�W�ڜ��}�F��sLw�3�H 9���9=�TuuKѬ�6��7�:?=L�9�g{k���seoM��\�y��W�Z�7RϷ��PYeR eɎ6��7�w.�`s��z�=��c����oo>�8-�)���Ֆ���-'�߉��N\�Z����+}�7M����-�r���[َ<�Yy�}��I����*ߕ����_�������>�_.�/��#��9۽�mh 9}^�\�ξ�^����Y<���=�o����\r�g,��A�/��~i��a����r����×�^"嫪��)r��r^�����^;߳�>]_6�˛>K�%�`ugχm���Y=��<=&y]�f-���nT��Mkv��O&��N>��3u���垪���,�nΫ鸯��OK�?�߽$ϼ���+�{�y�g���R�[�����r��GV��-� e�Y�<_�c�s[��׃�_�f��>�� ��N6�&�o�W�q�cՏ�c�#�>�e�i��x�Lm��[�M�W�F��c��y��r�ˎ��s��s�z��� �/M�����2+�K���>Y=�e/�<��ty��Mv�_M�9�[��:8��0J��G�mۦ<�I��I�.���� �����,��[���[|��M��;Y⩽ޙ{m��(:8�:����r�l��ޝg2�PX S+����=�e������Si�
�u*�~\�Y�b9\��a�n9mՎ�67-��&疓-�q���{����\g��=�/���N5m���;&ֹy����?J�7���͕�_��3��ޜp[�.�e�N=�ٖ:�� �2�<����tc<}�q���m<��d�y�S�]���g�y;h�.��Y����,}����%� nZ��L������
�w��_���n$ �1�@e�2��Y\���¾ ��������~-�~.__'��x̧��XC�߅��ӓOk����D�i+�\��ګyo�]�H�<���cy.��r�/�&����o�h�8�^n�y��8�א9��~</�>>V���vߘ��4�~��?�L|Dc;O���� +����� I�k�N�S<}��̻n�~�&y�2��s���h_1:Kb���a�@ �� ���ve�/�<� ���c���<~��v�<$ �p�Uvr^�]�ڄK/�3�+��99��?��/�;/����k�9=WN�OI�]����ُ�>_�?�0�x��ǖ���<Xa?.0l��/�p�����F��w=��_�q�Ƕ�ϒ�Q���|1�%��������������-=����[��쯝O���/��dO)��D[�B�h ��� �7���' �v����
�N�<��rz{�5|���3\�����qX� �� �2��n���m��){�_`/�z��� K{ �t�c���N���ӛ�c<�Şw+���+��3��� �фާ��v���� m�<�����D��������� ���y�J�;[��U��]8[&����R�xLVcd��KK��G���� �쌷��D���ϐL��Re.Z��\ rg��e������|o��fx^��JP�@ �r�|,���|���F����[L{@F2����Jܦ ���>lq�YrsW6Y�NOQo�7�@ /�;� �o��q�>�?�\q��<����<O�y�u�?�$��ս�߿� �i?T�ȐL�eߛ �;��up�nW�� �,}�{ ����ŷ��}�h�>�o�-<��=� ����宅s�g�����Yn7������m�.�8]�P B@E�Pgb�3{kU��)�2d�Y�g�\��G.Y�N\���>Fr�}U���Z� ���|~��������O������� �@����� "�v�7�?�2{_��S��� ����d��,�O������)�6��e�mϏ �wZ�=��"��[��x���|�O�ow_C,�{O>� @_:�.9n[��� 8�V=�?l���yoݷ?�q\}��]��;��0� pJ*PV�|)A��&��r��I�|yq[��u /����\f�|��d�]�� z�����88�s��� Gg><��� i�D�&� �� ��{����|c4������>��+�� [���'������ �.Z������>T��{��5����~���v���Lqמ� 擽߷����eg�� p�$�YI�� uc�`� (�������� -�W��( �����z2����� W��?����)�q�� +<�����y��������t &w�� ��m, ��