我有一个 n 大小的矩形集合，其中大部分彼此相交。我想删除相交并将相交的矩形减少为较小的非相交的矩形。
我可以轻松地暴力破解解决方案，但我正在寻找一种有效的算法。
这是一个可视化：
原来的：
处理：
理想情况下，方法签名如下所示：
public static List<RectF> resolveIntersection(List<RectF> rects);
输出将大于或等于输入，其中输出解析上述视觉表示。
扫描线算法擅长处理二维宇宙中的交叉点。我的意思是考虑一条水平线从矩形边缘向下移动到下一个矩形边缘。该线触及多个矩形，形成所谓的活动列表。活动列表在每次移动时都会保持更新。
通过研究沿水平线的横坐标范围，您可以检测重叠。
对所有配置的仔细研究应该允许您在单次扫描中按照您想要的方式分割矩形，其复杂度比暴力破解低（更接近 N^1.5，而不是 N^2）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
