在二维空间中找到矩形位置，使其覆盖最多的点

Question

在二维空间中找到矩形位置，使其覆盖最多的点

algorithmgraphicsgeometryintersectiongraphics2d

12

给定一个有 X 个点的二维空间，如何有效地找到放置固定大小矩形的位置，以便它覆盖尽可能多的这些 X 点？

我需要类似这样的东西来定位我正在开发的二维游戏中的视口。

- Jamona Mican

3

你是否可以旋转你的矩形，还是边必须平行于X轴和Y轴？ - Sergey Kalinichenko

2

为什么不确定点的最小和最大X和Y，并构造其范围矩形。如果矩形的轴被旋转，它就是一个最小面积包围矩形，它将覆盖所有点，就像范围矩形一样，但它的面积更小。第一种选项很容易实现，而后者则更难。 - user1121588

不允许旋转矩形。 - Jamona Mican

1

你想要快速的结果还是准确的结果？如果你只需要快速的结果，你可以将矩形居中于点的质心。如果你想要准确的结果，你可能需要迭代 O(n) 个可能的位置。 - beaker

我需要一些快速的东西。我不确定是否可能在不超过我的CPU预算的情况下完成（每帧60 fps移动点）。也许可以通过足够的缩短来实现。无论如何，我会为所有评论点赞。感谢您的帮助。 - Jamona Mican

2个回答

2

如果有人正在寻找@m69的C++代码，则在此处提供：

最初的回答：

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);

}

- Sidd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m69 ''snarky and unwelcoming'' · Accepted Answer

将点从左到右排序。在最左边的点处设置一个left指针，在left + width范围内的最右边的点处设置一个right指针。然后遍历所有点，每次重新计算right指针的位置，直到它在最后一个点上。
对左右之间的每个点集按从上到下的顺序进行排序。在最高点处设置一个top指针，在top + height范围内的最低点处设置一个bottom指针。然后遍历所有点，每次重新计算bottom指针的位置，直到它在最后一个点上。
对于左、右、上和下之间的每个点集，检查它有多少个点，并存储最优点集。
一旦找到最佳点集，矩形的中心就在最左和最右点之间，以及最高和最低点之间的中心。

以下是Javascript的简单实现，可以在许多方面进行优化。运行代码片段以查看使用随机数据的结果。

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>