performance - 用于在一组正方形之间拟合正方形的图形算法

Question

假设我在 2D 坐标系（浮点坐标）的有限区域内有 n 个大小相同且旋转相同的方形框。方框不应重叠。现在我想再找个空地再放一个盒子。我需要一些算法来解决这个问题。有任何想法吗？

Answer 1

应该有一个扫描线算法。你说盒子是同样旋转的，所以你应该能够在必要时旋转坐标系，使盒子的边缘平行于 x 和 y 坐标。然后我会按 y 坐标的顺序对这些框进行排序。

现在尝试将一个盒子放在尽可能低的位置。从已排序的框中读取所有低到足以干扰您的放置的框，并创建这些框的有序集（例如红黑树或类似的容器类）。现在沿着这组盒子扫描，看看是否有足够大的间隙可以放置一个盒子。如果没有，请使用原始排序的框列表来查找并删除最低框，因此您可以考虑将新框放在最低框的上方，这样就不会干扰。从排序列表中添加更多框以覆盖所有高到足以干扰框的新可能高度的框。跟踪您从列表中删除盒子的位置，并检查那里是否有足够大的间隙可以容纳一个盒子。如果没有，请重复练习，直到在可能区域的顶部找到间隙或空间不足。

这看起来像初始排序的成本 N log N，然后从有序集中插入和删除框的每个框的成本最多为 log N。检查间隙并不比这更昂贵，因为您只检查刚刚移除盒子的位置的间隙。所以我认为总成本是 N log N。