寻找一种非"强力"算法来移除一组Rects的交叉区域
Mic*_*rdo 5 algorithm intersection polygon rect orthogonal
我有一个n大小的Rects集合,其中大部分相互交叉.我想删除交叉点并将相交的Rects缩小为较小的非交叉rects.
我可以很容易地强制解决方案,但我正在寻找一种有效的算法.
这是一个可视化:
原版的:
处理:
理想情况下,方法签名看起来像这样:
public static List<RectF> resolveIntersection(List<RectF> rects);
输出将大于或等于输入,其中输出解析上述视觉表示.
Sweepline算法擅长处理2D宇宙中的交叉点.我的意思是考虑从矩形边缘向下移动到下一个矩形边缘的水平线.该线撞击了许多矩形,形成了所谓的活动列表.活动列表在每次移动时都会保持更新.
通过研究水平线上的横坐标范围,您可以检测到重叠.
仔细研究所有配置应该允许您在单次扫描中按照您想要的方式分割矩形,复杂性低于蛮力(接近N ^ 1.5而不是N ^ 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 + size = 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）
当然，对于大量矩形，您通常只需检查可能对的一小部分是否相交。