寻找一种非“蛮力”算法来删除矩形集合的相交区域

Question

我有一个n大小的矩形集合，其中大多数相互相交。我想删除交叉点，并将相交的矩形减少为较小的非相互作用矩形。

我可以轻松地强迫解决方案，但是我正在寻找有效的算法。

这是一个可视化：

原来的：

处理：

理想情况下，方法签名看起来像这样：

public static List<RectF> resolveIntersection(List<RectF> rects);

输出将更大或等于输入，其中输出可以解决上述视觉表示。

Answer 1

这是我过去解决的问题。使用其中一个边的X或Y值对矩形进行排序的第一件事。假设您在Y方向上订购并使用顶部边缘。示例中最上方的矩形首先按顺序排序。对于每个矩形，您都知道其大小在y方向上。

现在，对于每个条目（将其称为当前条目，它对应于矩形），您可以通过列表向前搜索的排序列表中，直到您到达比当前条目 +相应的矩形大小的输入。 （称其为停止条目）

当前条目和此停止条目之间的分类列表中的任何条目将是潜在的交叉点。只需检查矩形X射线是否相交。

When choosing to sort in the x or y direction, it will be better to choose the dimension that is larger as this will imply fewer intersection on average so less checking.

这是一个例子。矩形定义为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）

当然，使用大量矩形，您通常只需要检查可能对的一对以进行交叉即可。

Answer 2

扫描义务擅长处理2D宇宙中的交叉点。我的意思是考虑从矩形边缘向下移动到下一个矩形边缘的水平线。该行登录了许多矩形，形成了所谓的活动列表。积极的列表在每一步都保持更新。

通过研究沿着水平线的横坐标范围，您可以检测到重叠。

对所有配置的仔细研究应使您能够以单个扫描方式将矩形分开，其复杂性低于蛮力（接近n^1.5，而不是n^2）。

Answer 3

您要描述的是包装问题，看看 维基百科

它指的是 这个 文章描述了用于包装矩形矩形的算法的文章

这是从文章中：

本文介绍了一种快速算法，可以将一系列不同宽度和高度的矩形包装到一个封闭的矩形中，没有重叠，并且以最小化封闭矩形中浪费的空间的数量。