在一系列矩形中寻找一个矩形的最佳位置

Question

在一系列矩形中寻找一个矩形的最佳位置

javaalgorithmlibgdx

3

我正在进行一款2D城堡防御游戏的编程，今天遇到了一个问题，但是我无法找到一个好的解决方案。请看下面的图片：

http://imgur.com/zOe2Muv

我希望在这个矩形区域中找到一个最接近当前鼠标位置的可放置红色矩形的位置，且不会与其他矩形重叠。所谓的最接近可能的位置是指相对于给定点最接近的位置。

针对该问题，什么是正确的算法呢？

谢谢！

- gerds0n

1

希望你使用某种网格来定位矩形，而不是随机浮点值作为坐标，否则，这将无法快速计算... - Keiwan

1个回答

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

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

- BKE · Accepted Answer

这是一个优化问题，其中您的约束是线性的，目标函数是（分段）二次或线性的，具体取决于您如何定义光标距离。假设矩形由x_i，y_i，w_i，h_i for i=1..n定义，红色矩形的大小为w，h，则决策变量是红色矩形的x，y位置。然后，非重叠约束为：对于所有i = 1..n，都有x>= x_i + w_i或y>= y_i + h_i或x <= x_i - w或y <= y_i - h。您可以以多种方式定义目标（红色矩形与光标之间的距离）：

光标与红色矩形最近点之间的正确欧几里得平方距离（我认为会产生分段二次函数）
从红色矩形中心的欧几里得平方距离（二次函数）
从红色矩形中心的曼哈顿距离（分段线性）

然后，您可以使用二次规划求解器或MILP（混合整数线性规划）求解器来找到答案。如果矩形的数量不太大（比如少于一百个），即使使用免费的求解器如GLPK或LP Solve，速度也会非常快。

请注意，为了正确表达这些求解器的约束条件，您可能需要转换约束条件和目标函数，例如使用大M法来处理约束条件，或将问题转换为线性目标。这意味着您将有额外的二进制变量，并且会有更多的约束条件（额外变量和约束条件的数量将与矩形的数量成比例）。