我有一个 n 大小的 Rects 集合，其中大部分相互交叉。我想删除交叉点并将相交的矩形减少为更小的非相交矩形。
我可以很容易地暴力破解解决方案，但我正在寻找一种有效的算法。
这是一个可视化：
原来的：
处理：
理想情况下，方法签名应如下所示：
public static List<RectF> resolveIntersection(List<RectF> rects);
输出将大于或等于输入，其中输出解析上述视觉表示。
问问题
487 次
3 回答
6
扫描线算法擅长处理二维宇宙中的交叉点。我的意思是考虑一条从矩形边缘向下移动到下一个矩形边缘的水平线。这条线碰到许多矩形，形成所谓的活动列表。活动列表在每次移动时都会保持更新。
通过研究沿水平线的横坐标范围，您可以检测到重叠。
仔细研究所有配置应该允许您在单次扫描中以您想要的方式拆分矩形，其复杂性低于蛮力（接近 N^1.5 而不是 N^2）。
于 2012-02-16T00:38:26.730 回答
2
这是我过去解决的问题。首先使用其中一条边的 x 或 y 值对矩形进行排序。假设您在 y 方向订购并使用顶部边缘。您的示例中最上面的矩形按排序顺序排列在第一位。对于每个矩形，您都知道它在 y 方向上的大小。
现在，对于排序列表中的每个条目（称为当前条目，它对应于一个矩形），您在列表中向前搜索，直到找到一个大于当前条目 + 相应矩形大小的条目。（称之为停止入口）
当前条目和此停止条目之间的排序列表中的任何条目都将是潜在的交叉点。只需检查矩形 x 范围是否相交。
选择在x或y方向上排序时，最好选择更大的尺寸，因为这将暗示平均的交叉点较少，因此较少的检查。
这是一个例子。矩形定义为 R(x1,x2,y1,y2) 其中 x1 是左侧，x2 是右侧，y1 是顶部，y2 是底部
rectangle 1 (1,5,0,4)
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)
按y1排序给
# y1 size
rectangle 1 0 4
rectangle 3 2 3
rectangle 4 3 4
rectangle 2 6 2
rectangle 5 9 6
因此，矩形 1 的 y1 + size = 0 + 4 = 4 意味着它可能与矩形 3（y1 值 = 3 < 4）和矩形 4（y1 值 = 3 < 4）相交，但不会与矩形 2（y1 值 = 6 > 4）...无需在 2 之后检查列表中的任何矩形
矩形 3 具有 y2 + 大小 = 2 + 3 = 5，这意味着它可能与矩形 4 相交（y1 值 = 3 < 5）但不会与矩形 2 相交（y1 值 = 6 > 5）不需要在 2 之后检查列表中的任何矩形
矩形 4 的 y2 + size = 3 + 4 = 7 意味着它可能与矩形 2 相交（y1 值 = 6 < 7），但不会与矩形 5 相交（y1 值 = 9 > 7）
当然，对于大量矩形，您通常只需检查一小部分可能的交叉对。
于 2012-02-16T11:37:44.517 回答