Hilbert Curve with Query

.block

license: mit

README.md

An interactive version of the Hilbert curve that demonstrates the range query required to cover a specific bounding box.

Forked from Vasco Asturiano's Hilbert Curve Block and inspired by Jared Winick's Z-order Curve with Query Block.

hilbert-demo.js

function hilbertDemo() {

    var svg = d3.select('svg#hilbert-chart'),
        canvasWidth = Math.min(window.innerWidth, window.innerHeight - 100),
        hilbert,
        order = 6,
        brushSelection = [
          [canvasWidth * 0.1, canvasWidth * 0.1], 
          [canvasWidth * 0.45, canvasWidth * 0.45]
        ];

    function d3Digest() {
        var hilbertData = {
            start: 0,
            length: Math.pow(4, order)
        };

        hilbert.order(order).layout(hilbertData);

        svg.selectAll('.skeleton, .main-path')
            .datum(hilbertData)
            .attr('d', function(d) { return getHilbertPath(d.pathVertices); })
            .attr('transform', transform);

        if (brushSelection) {
            var hilbertRange = getHilbertRange();
            var hilbertHighlightData = {
                start: hilbertRange[0],
                length: hilbertRange[1] - hilbertRange[0]
            };

            hilbert.layout(hilbertHighlightData);

            svg.selectAll('.highlight-path')
                .datum(hilbertHighlightData)
                .attr('d', function(d) { return getHilbertPath(d.pathVertices); })
                .attr('transform', transform);
        }

        function transform(d) {
            return 'scale('+ d.cellWidth + ') '
                + 'translate(' + (d.startCell[0] +.5) + ',' + (d.startCell[1] +.5) + ')';
        }

        /**
         * Computing the hilbert distance for each of the four bounding box corners
         * alone is not enough. There may be another point on the perimeter of the
         * bounding box that has a lower/higher distance. This function generates
         * a list of points around the perimeter and then computes the hilbert
         * distance for each of those points to get a better idea of the full range
         * we'd need to scan.
         */
        function getHilbertRange() {
            var increment = 1;
            var xExtent = [brushSelection[0][0], brushSelection[1][0]];
            var yExtent = [brushSelection[0][1], brushSelection[1][1]];

            // Generate points around the perimeter from bounding box
            var points = [];
            for (var x = xExtent[0]; x <= xExtent[1]; x+= increment) {
                points.push([x, yExtent[0]]);
                points.push([x, yExtent[1]]);
            }
            for (var y = yExtent[0]; y <= yExtent[1]; y+= increment) {
                points.push([xExtent[0], y]);
                points.push([xExtent[1], y]);
            }

            // Convert to hilbert distances (distance along the curve)
            var distances = points.map(p => hilbert.getValAtXY.apply(hilbert, p))

            var start = Math.min.apply(null, distances);
            var end = Math.max.apply(null, distances);

            return [start, end];
        }

        function getHilbertPath(vertices) {
            var path = 'M0 0L0 0';

            vertices.forEach(function(vert) {
                switch(vert) {
                    case 'U': path += 'v-1'; break;
                    case 'D': path += 'v1'; break;
                    case 'L': path += 'h-1'; break;
                    case 'R': path += 'h1'; break;
                }
            });
            return path;
        }
    }

    function orderChange(newOrder) {
        order = newOrder;
        d3Digest();
    }

    function init() {
        hilbert = d3.hilbert()
            .order(order)
            .canvasWidth(canvasWidth)
            .simplifyCurves(false);

        var brush = d3.brush()
            .on("brush", brushed)
            .extent([[0, 0], [canvasWidth, canvasWidth]]);
        
        function brushed() {
            brushSelection = d3.event.selection;
            d3Digest();
        }

        svg.attr("width", canvasWidth).attr("height", canvasWidth);

        var canvas = svg.append('g');
        canvas.append('path').attr('class', 'skeleton');
        canvas.append('path').attr('class', 'main-path');
        canvas.append('path').attr('class', 'highlight-path');

        var brushNode = canvas.append("g").attr("class", "brush").call(brush);
        brush.move(brushNode, brushSelection);

        // Canvas zoom/pan
        svg.call(d3.zoom()
            .translateExtent([[0, 0], [canvasWidth, canvasWidth]])
            .scaleExtent([1, Infinity])
            .on("zoom", function() {
                canvas.attr("transform", d3.event.transform);
            })
        );

        // Value Tooltip
        var valTooltip = d3.select('#val-tooltip');
        svg.on('mouseover', function() { valTooltip.style("display", "inline"); })
            .on('mouseout', function() { valTooltip.style("display", "none"); })
            .on('mousemove', function () {
                var coords = d3.mouse(canvas.node());
                console.log(coords);
                valTooltip.text(hilbert.getValAtXY(coords[0], coords[1]))
                    .style('left', d3.event.pageX)
                    .style('top', d3.event.pageY);
            });

        // Order slider
        $('input#hilbert-order').slider({
            step: 1,
            max: 9,
            min: 0,
            value: order,
            tooltip: 'always',
            tooltip_position: 'bottom',
            formatter: function(d) {
                return 'Order: ' + d;
            }
        }).on('change', function(e) {
            orderChange(e.value.newValue);
        });

        d3Digest();
    }

    init();
}

index.html

<head>
    <script src="//code.jquery.com/jquery-3.1.0.min.js"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/d3/4.2.6/d3.min.js"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/bootstrap-slider/9.1.3/bootstrap-slider.min.js"></script>
    <script src="//unpkg.com/[email protected]/build/d3-hilbert.min.js"></script>
    <script src="hilbert-demo.js"></script>

    <link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
    <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/bootstrap-slider/9.1.3/css/bootstrap-slider.min.css">

    <style>
        body {
            text-align: center;
        }

        svg {
            margin: 10px;
        }

        path.main-path {
            fill: none;
            stroke: #3A5894;
            stroke-width: 0.2;
            stroke-linecap: square;
        }

        path.highlight-path {
            fill: none;
            stroke: #ff0000;
            stroke-width: 0.2;
            stroke-linecap: square;
        }

        path.skeleton {
            fill: none;
            stroke: #EEE;
            stroke-width: 0.1;
        }

        #val-tooltip {
            display: none;
            position: absolute;
            margin-top: 22px;
            margin-left: -1px;
            padding: 5px;
            border-radius: 3px;
            font: 11px sans-serif;
            color: #eee;
            background: rgba(0, 0, 140, 0.9);
            text-align: center;
            pointer-events: none;
        }

        .brush .selection {
            stroke: none;
        }
    </style>
</head>

<body>
    <svg id="hilbert-chart"></svg>
    <div id="hilbert-controls">
        <input id="hilbert-order" />
    </div>
    <div id="val-tooltip"></div>

    <script>
        hilbertDemo();
    </script>
</body>