algorithm graphics geometry intersection graphics2d

Finding rectangle position that makes it cover maximum points in 2D space

Given a 2D Space with X points, how can I efficiently find where to place a fixed-size rectangle, so that it covers the largest possible number of those X points?

I need something along these lines to position a viewport in a 2D game I'm building.

Solution

Sort the points from left to right. Set a left pointer at the leftmost point, and a right pointer at the rightmost point that falls within left + width. Then iterate over all the points, recalculating the position of the right pointer each time until it is at the last point.
Sort each subset of points between left and right from top to bottom. Set a top pointer at the highest point, and a bottom pointer at the lowest point that falls within top + height. Then iterate over all the points, recalculating the position of the bottom pointer each time until it is at the last point.
For every subset of points between left, right, top and bottom, check how many points it has, and store the optimal subset.
Once the optimal subset has been found, the center of the rectangle is halfway between the leftmost and rightmost point, and halfway between the highest and lowest point.

Below is a simple implementation in Javascript, which can be optimised on many points. Run the code snippet to see the results with random data.

function placeRectangle(p, width, height) {
    var optimal, max = 0;
    var points = p.slice();
    points.sort(horizontal);

    for (var left = 0, right = 0; left < points.length; left++) {
        while (right < points.length && points[right].x <= points[left].x + width) ++right;
        var column = points.slice(left, right);
        column.sort(vertical);

        for (var top = 0, bottom = 0; top < column.length; top++) {
            while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom;
            if (bottom - top > max) {
                max = bottom - top;
                optimal = column.slice(top, bottom);
            }
            if (bottom == column.length) break;
        }
        if (right == points.length) break;
    }

    var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y;
    for (var i = 0; i < optimal.length; i++) {
        var x = optimal[i].x;
        if (left == undefined || x < left) left = x;
        if (right == undefined || x > right) right = x;
    }
    return {x: (left + right) / 2, y: (top + bottom) / 2};

    function horizontal(a, b) {
        return a.x - b.x;
    }

    function vertical(a, b) {
        return a.y - b.y;
    }
}

var width = 160, height = 90, points = [];
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)};
var rectangle = placeRectangle(points, width, height);

// SHOW RESULT IN CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 300; canvas.height = 200;
canvas = canvas.getContext("2d");
paintRectangle(canvas, rectangle.x - width / 2, rectangle.y - height / 2, width, height, 1, "red");
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue");
function paintDot(canvas, x, y, size, color) {
    canvas.beginPath();
    canvas.arc(x, y, size, 0, 6.2831853);
    canvas.closePath();
    canvas.fillStyle = color;
    canvas.fill();
}
function paintRectangle(canvas, x, y, width, height, line, color) {
    canvas.beginPath();
    canvas.rect(x, y, width, height);
    canvas.closePath();
    canvas.lineWidth = line;
    canvas.strokeStyle = color;
    canvas.stroke();
}

<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS>
</BODY>