algorithm - 找到一组矩形未触及的点的高效算法

Question

输入:在(0, 0)到(1600, 1200)范围内的一组矩形。

输出:没有任何矩形包含的点。

对此有什么有效的算法？目前我能想到的只有两个:

• 创建一个 1600x1200 的 bool 数组。遍历每个矩形的区域，将这些位标记为 True。最后迭代，发现一个 False 位。问题是它会浪费内存并且速度很慢。
• 随机遍历点。对于每个点，遍历矩形并查看其中是否包含该点。返回所有矩形都不包含的第一个点。问题是它对于人口密集的问题实例来说真的很慢。

我为什么要这样做？这不是为了家庭作业或编程竞赛，尽管我认为这个问题的一个更复杂的版本被问过(每个矩形都有一个“颜色”，你必须输出他们给你的几个点的颜色)。我只是想以编程方式禁用 Windows 上的第二台显示器，我遇到了更多 sane approach 的问题.所以我的目标是在桌面上找到一个未占用的位置，然后模拟右键单击，然后模拟所有必要的单击以从显示属性窗口禁用它。

Answer 1

对于每个矩形，创建一个沿水平方向运行的列表。例如，一个 100x50 的矩形将生成 50 个 100 的游程。将它们及其最左侧的 X 坐标和 Y 坐标写入列表或 map 。

对列表进行排序，先是 Y，然后是 X。

浏览列表。重叠的运行应该是相邻的，这样您就可以合并它们。

当您发现第一次运行没有横跨整个屏幕时，您就完成了。