我正在制作一个2D游戏，使用基于矩形的碰撞检测中的y轴排序。这很好用，现在我想高效地找到给定位置和大小的最近的空矩形。有什么算法可以做到这一点吗？
我能想到一个简单的暴力网格测试（每个网格都是我们要寻找的空间大小），但显然这很慢，也不是完整的测试。
2个回答
2
考虑使用四叉树来存储你的矩形。
更多信息请参见http://en.wikipedia.org/wiki/Quadtree。
- Patrick
1
经过一些阅读，似乎矩形四叉树是正确的选择。感谢提供链接。 - Morrowless
0
如果您已经在使用轴排序，那么您可能已经计算出了按其位置排序的矩形列表。
也许我误解了，但是您不可以只看一下问题矩形前后的两个矩形，并决定哪一个更接近吗？如果您要找到离任意点最近的矩形，则可以简单地遍历列表，直到找到第一个位置大于您的任意点的矩形，并将其与前一个矩形一起用作进行比较的两个矩形。
- Jordan Lewis
1
Y轴排序只是意味着每个矩形根据其y位置进行排序，因此前后并不一定意味着最接近。此外，我正在尝试找到最近的适合特定大小的空白空间，而不是最接近的矩形。 - Morrowless
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接