合并和分割重叠的矩形以产生不重叠的矩形

Question

我正在寻找一个算法如下:

给定一组可能重叠的矩形(所有这些都是"未旋转",可以统一表示为(左,上,右,下)连音符等...),它返回一组最小(非旋转)非重叠的矩形,占据相同的区域.

乍一看似乎很简单,但是很容易变得棘手(至少要有效地完成).

这个/ ideas /指针有一些已知的方法吗？

不一定是最小但是启发式小的集合的方法也很有趣,所以产生任何有效输出集的方法也是如此.

Answer 1

基于线扫描算法的东西可行,我想:

• 将所有矩形的最小和最大x坐标排序为数组,作为"起始矩形"和"结束矩形"事件
• 逐步执行数组,将遇到的每个新矩形(start-event)添加到当前集合中
• 同时,维护一组将作为输出集的"非重叠矩形"
• y每次遇到一个新的矩形时,你都可以检查它是否已完全包含在当前/输出集中(简单比较-coordinates就足够了)
• 如果不是,请在输出集中添加一个新矩形,并将y-coordinates设置为尚未覆盖的新矩形部分.
• 每当您点击矩形结束事件时,请停止输出集中任何不再覆盖任何内容的矩形.

我不完全确定这涵盖了所有内容,但我认为通过一些调整它应该完成工作.或者至少给你一些想法...... :)