javascript - 如何在二维中表示已用空间？

Question

我有固定区域的二维空间，里面充满了矩形。我想移动矩形，添加新矩形，删除一些矩形，但不允许它们重叠。如果所有矩形的高度和宽度相同(50x50px)，我应该使用什么数据结构来存储它们的位置以及它们正在使用的空间，以及在向场景添加新矩形时我应该使用什么查找方法针对该结构？

Answer 1

这是经典的简单部分 collision detection问题。大部分AABB Trees (不确定这是否是最佳链接，但这就是名称，无论如何)用于有效地解决它，但查找用于边界框碰撞检测的任何碰撞检测算法。 AABB(轴对齐边界框)树适用于“对齐”的矩形，即无法旋转的矩形。

对于非对齐矩形，只需取包含旋转矩形的最小轴对齐矩形。事实上，AABB 树用于通过获取任意多边形的边界框来加速对任意多边形的碰撞检测。如果轴对齐边界框等于所有对象，那就更好了。

但是，如果您不介意性能，那么使用矩形的平面列表并执行 O(n²) 搜索确实会更容易:用伪代码表示:

function intersection_free(rectangles)
    for rect in rectangles
        for rect2 in rectangles
            if intersects(rect, rect2)
                return false;

    return true;

简单是一件很棒的事情，不是吗？