我正在寻找如下算法：
给定一组可能重叠的矩形（所有矩形都“未旋转”，可以统一表示为（左，上，右，下）连音符等...），它返回一组最小的（非旋转）不重叠的矩形，占据相同的面积。
乍一看似乎很简单，但事实证明很棘手（至少要高效地完成）。
this/ideas/pointers 有一些已知的方法吗？
不一定是最小的，但启发式的小集合的方法也很有趣，产生任何有效输出集的方法也很有趣。
我认为基于线扫描算法的东西会起作用：
- 对所有矩形的最小值和最大值进行排序
x坐标到数组中，作为“开始矩形”和“结束矩形”事件
- 单步遍历数组，将遇到的每个新矩形（开始事件）添加到当前集合中
- 同时，维护一组“不重叠的矩形”，这将是您的输出集
- 任何时候你遇到一个新的矩形，你都可以检查它是否已经完全包含在当前/输出集中（简单比较
y- 坐标就足够了）
- 如果不是，请向输出集中添加一个新矩形，使用
y- 坐标设置为新矩形中尚未覆盖的部分。
- 每当您遇到矩形结束事件时，请停止输出集中不再覆盖任何内容的任何矩形。
我不完全确定这涵盖了所有内容，但我认为通过一些调整应该可以完成工作。或者至少给你一些想法......:)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
