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

Question

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.

Chateau

Are you allowed to turn your rectangle, or are the sides parallel to X and Y axes? – Jeanett

Why not determine the min and max X and Y of the points and construct its extent rectangle. If the axes of the rectangle are rotated it is a minimum area bounding rectangle, it will cover all the points like the extent rectangle, but it will have a smaller area. The first option it simple to implement, the latter is more difficult. – Roturier

not allowed to turn the rectangle – Chateau

Do you want something fast, or do you want something accurate? If you just want fast, you can center the rectangle on the centroid of points. If you want accurate, you'll likely have to iterate through O(n) possible positions. – Communalize

I needed something fast. I'm not sure it's even possible to do without exceeding my CPU budget (the points move every frame at 60 fps). Probably with enough cutting corners. Anyway, I'm upvoting all the comments. Thanks for your help. – Chateau

Answer 1

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

Scission

This is a ridiculously complete answer. Running code that you can click on! Good work, accepting it. Doesn't look like I will use it though because I've made some gameplay changes so that the requirement in the question does not need to be fulfilled anymore. Think it would have been too expensive anyway. Needs to run every frame at 60fps + all the points are constantly moving. The sorting may have killed it. Either way, thanks. – Chateau

@HarryMexican I wrote the code to demonstrate the idea, but whether you can actually do it like this does indeed depend on how many points there are and how fast it needs to be; running it at the framerate of the game would likely be problematic with anything more than a handful of points. The algorithm relies on the sorting, so there's no way to skip that to increase efficiency. An algorithm that only looks at points that are about to leave the rectangle and then gradually moves it around would probably be more efficient in your case. – Breaker

Yep, it's an interesting thought experiment in any case. Hope you got something out of writing it out, and that it helps someone else looking for an algorithm of this kind. :) – Chateau

@HarryMexican If you put the points in a tree structure where every point is connected to the 4 points directly above, below, left and right of it, that could probably do away with all the re-sorting. But that's an exercise for another day :-) – Breaker

This could be improved to O(n log n) by using a full-out sweepline algorithm to avoid resorting. – Thrown

Answer 2

If someone is looking for @m69's code in C++ then here it is:

struct str {
bool operator() (cv::Point2f a, cv::Point2f b) 
{
    return a.x < b.x;
}
} compX;

struct str1 {
    bool operator() (cv::Point2f a, cv::Point2f b) 
    {
       return a.y < b.y;
    }
} compY;


cv::Point2f placeRectangle(std::vector<cv::Point2f> p, float width, float height)
{
    double max = 0;
    std::vector<cv::Point2f> points = p;
    std::sort(points.begin(), points.end(), compX);
    std::vector<cv::Point2f> optimal;
    float left = 0.0;
    float right = 0.0;

    for (left = 0, right = 0; left < points.size(); ++left)
    {
        while (right < points.size() && points[right].x <= points[left].x + width) ++right;

        std::vector<cv::Point2f> myVector1(points.begin() + left, points.begin() + right);
        std::vector<cv::Point2f> column = myVector1;
        std::sort(column.begin(), column.end(), compY);

        for (int top = 0, bottom = 0; top < column.size(); top++)
        {
            while (bottom < column.size() && column[bottom].y <= column[top].y + height) ++bottom;
            if (bottom - top > max)
            {
                max = bottom - top;
                std::vector<cv::Point2f> myVector(column.begin() + top, column.begin() + bottom);
                optimal = myVector;
            }
            if (bottom == column.size()) break;
        }
        if (right == points.size()) break;
    }

    left = 0; right = 0; float top = optimal[0].y; float bottom = optimal[optimal.size() - 1].y;
    for (int i = 0; i < optimal.size(); i++)
    {
        float x = optimal[i].x;
        if (left == 0 || x < left) left = x;
        if (right == 0 || x > right) right = x;
    }

    return cv::Point2f((left + right) / 2.0, (top + bottom) / 2.0);

}

Maurine