我有N个矩形,其边平行于x和y轴。另外还有一个矩形model。 我需要创建一个算法来判断model是否完全被N个矩形覆盖。
我有一些想法。首先,我需要按其左侧对矩形进行排序(可以在O(n log n)时间内完成),然后使用垂直扫描线。
+------------------------------------------------------------> x
|O
| +----+
| +---------+ | |
| | ++----+--+ |
| | +-++----+-+| |
| | | | +-++-+
| +------+ +-------++
| +---------+
|
|
|
|y
蓝色矩形是模型。
首先,我需要抽象算法。对于实现没有特殊要求。矩形可以表示为一对点(左上角和右下角)。
这是为准备测试而完成的任务之一。我知道最好的算法可以在O(n log n)时间内完成此任务。
O(n log n)
的算法,它基于对qsort
算法的改进。 - Matthieu M.