一种解决简单(？)数组问题的算法

Question

对于这个问题,速度非常重要.我画了一个很好的图像来更好地解释这个问题.算法需要计算矩形边缘是否在画布的范围内继续,边缘是否与另一个矩形相交？

我们知道:

解决方案越快越好!我非常坚持这个,并不知道从哪里开始.

干杯

Answer 1

只需为每个X轴和Y轴创建一组间隔.然后,对于每个新矩形,查看X轴或Y轴是否存在交叉间隔.请参阅此处了解实现区间集的一种方法.

在第一个示例中,水平轴上设置的区间将是{ [0-8], [0-8], [9-10] }垂直轴:{ [0-3], [4-6], [0-4] }

这只是一个草图,我在这里抽象了许多细节(例如,通常会有人问一个间隔集/树",这个间隔与这个间隔重叠",而不是"与这一个相交",但没有什么不可行).

编辑

请看这个相关的麻省理工学院讲座(它有点长,但绝对值得).即使您找到更简单的解决方案(而不是实现增强的红黑树),也很了解这些事情背后的想法.