个人中心
gpt4 book ai didi

algorithm - 找到使其覆盖二维空间中最大点的矩形位置

转载 作者：塔克拉玛干 更新时间：2023-11-03 02:37:07 25 4
gpt4 key购买 nike

给定一个带有 X 点的 2D 空间，我如何才能有效地找到放置固定大小矩形的位置，以便它覆盖尽可能多的 X 点？

我需要按照这些思路在我正在构建的 2D 游戏中定位视口(viewport)。

最佳答案

  • 将点从左到右排序。在最左边的点设置一个 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>

关于algorithm - 找到使其覆盖二维空间中最大点的矩形位置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32429311/

25 4 0
文章推荐： algorithm - 如何查找矩阵中唯一直线的数量
文章推荐： internationalization - prestashop 中不同语言项目的重复内容
文章推荐： xml - 站点地图中 urlset 标记的 xmlns 属性值应该是多少？
文章推荐： algorithm - 对 40 亿个整数使用 10 MB 的内存(关于找到优化的 block 大小)
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com