algorithm - 计算矩形选择所选择的所有框的算法

Question

假设您绘制了大量的框，并且用户可以在它们上绘制一个矩形区域。

虽然我将在浏览器中实现它，但让我们将它抽象出来并假设我们已经获得了每个矩形的每个点的坐标。

鉴于我想检查选择哪些框，这里最有效的数据结构和算法a) intersect b) are contained by是什么？

我目前的想法是：

• 对所有框进行排序x
• 通过 binsearch，检查哪些框与选择区域在 x 方向上重叠，然后，对于每个 x 方向重叠的框，检查它们是否也与 y 方向对齐。

或者

• 按x和对所有框进行排序y，每个框都在单独的数组中
• 通过 binsearch，首先找到所有 x 重叠的框，然后找到所有 y 重叠的框，然后检查两组中有哪些框，

...虽然我很确定有一些众所周知的算法可以解决这样的问题。

标签： algorithm

Answer 1

我想通过某个矩形选择，您的意思是与某个矩形相交或包含在某个矩形中。如果“绘制的框”是固定位置的，那么想到的一种方法是二进制空间分区。粗略地说，可以为“绘制的框”生成（理想平衡的）二元空间分区树。如果选择矩形被定位，则其角的位置将与二进制空间分区树匹配，并且可以从显式检查交叉点中排除大半空间。