当前位置：文江博客话题详情

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

发布于 2025-01-06 00:43:23 字数 437 浏览 3 评论 0原文

我有一个 n 大小的矩形集合，其中大部分彼此相交。我想删除相交并将相交的矩形减少为较小的非相交的矩形。

我可以轻松地暴力破解解决方案，但我正在寻找一种有效的算法。

这是一个可视化：

原始：

original

处理后：

processed

理想情况下，方法签名如下所示：

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

输出将大于或等于输入，其中输出解析上述视觉表示。

原文

I have an n-sized collection of Rects, most of which intersect each other. I'd like to remove the intersections and reduce the intersecting Rects into smaller non-intersecting rects.

I could easily brute force a solution, but I'm looking for an efficient algorithm.

Here's a visualization:

Original:

original

Processed:

processed

Ideally the method signature would look like this:

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

the output would be greater or equal to the input, where the output resolves the above visual representation.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不美如何 2025-01-13 00:43:23

扫描线算法擅长处理二维宇宙中的交叉点。我的意思是考虑一条水平线从一个矩形边缘向下移动到下一个矩形边缘。该线触及多个矩形，形成所谓的活动列表。活动列表在每次移动时都会保持更新。

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

对所有配置的仔细研究应该允许您在单次扫描中按照您想要的方式分割矩形，其复杂度比暴力破解低（更接近 N^1.5，而不是 N^2）。

回复收藏 0 原文

冷︶言冷语的世界 2025-01-13 00:43:23

这是我过去解决过的一个问题。第一件事是使用其中一条边的 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）

当然，对于大量矩形，您将通常只需要检查可能的交集对的一小部分。

this is a problem I solved in the past. The first thing it to sort the rectangles using the x or y value of one of the edges. Lets say you order in the y-direction and use the top edge. The topmost rectangle in your example is first in sorted order. For each rectangle you know its size in the y-direction.

Now, for each entry (call it the the current entry, it corresponds to a rectangle)in the sorted list you search forward through the list until you reach an entry greater than the current entry + the corresponding rectangle size. (call it the stopping entry)

Any entries in the sorted list between the current entry and this stopping entry will be potential intersections. Simply check if the rectangles x-ranges intersect.

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.

Here is an example. Rectangles are defined as R(x1,x2,y1,y2) where x1 is the left side, x2 is right side, y1 is top and y2 is bottom

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)

sort according to y1 to give

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

so, rectangle 1 has y1 + size = 0 + 4 = 4 implying it will potentially intersect rectangle 3 (y1 value = 3 < 4) and rectangle 4 (y1 value = 3 < 4) but not rectangle 2 (y1 value = 6 > 4)...no need to check any rectangels in the list after 2

Rectangle 3 has y2 + size = 2 + 3 = 5 implying it will potentially intersect rectangle 4 (y1 value = 3 < 5) but not recatngle 2 (y1 value = 6 > 5) no need to check any rectangels in the list after 2

Rectangle 4 has y2 + size = 3 + 4 = 7 implying it will potentially intersect rectangle 2 (y1 value = 6 < 7) but not recatngle 5 (y1 value = 9 > 7)

Of course, with large numbers of rectangles you will generally only have to check a fraction of the possible pairs for intersection.

回复收藏 0 原文