algorithm - 解决简单(？)数组问题的算法

Question

对于这个问题，速度非常关键。我画了一个很好的图像来更好地解释这个问题。该算法需要计算一个矩形的边是否继续在 Canvas 的范围内，该边是否会与另一个矩形相交？

我们知道:

1. Canvas 的大小
2. 每个矩形的大小
3. 每个矩形的位置

解决方案越快越好!我很困在这个问题上，真的不知道从哪里开始。

alt text http://www.freeimagehosting.net/uploads/8a457f2925.gif

干杯

Answer 1

只需为每个 X 轴和 Y 轴创建一组间隔。然后对于每个新矩形，查看 X 轴或 Y 轴上是否存在相交间隔。 See here实现区间集的一种方法。

在您的第一个示例中，水平轴上设置的间隔为 { [0-8], [0-8], [9-10] }，而在垂直轴上:{ [0-3], [4-6], [0-4] }

这只是一个草图，我在这里抽象了很多细节(例如，通常人们会问一个区间集/树“哪些区间与这个区间重叠”，而不是“与这个区间相交”，但没有什么不可行的)。

编辑

Please watch this related MIT lecture (它有点长，但绝对值得)。即使您找到了更简单的解决方案(比实现增强型红黑树)，了解这些事情背后的想法也是有好处的。