block by fil 983398617871ad90d2853f3b35a86b84

CCPD Snowden

Full Screen

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

index.html

<!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>

snowden.jpg

����JFIFHH��CP7<F<2PFAFZUP_xȂxnnx���������������������������������������������CUZZxix낂���������������������������������������������������������TX"����3!1AQaq"��2B���3��#Rbr��������?�W<�\��������1��9er��檚� ���n��
�馁	ݝ��XJkŝ��-]�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�v݋rq�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۽�mh9}^�\�ξ�^����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,��