解决简单（？）数组问题的算法

Question

对于这个问题，速度非常关键。我画了一张漂亮的图来更好地解释这个问题。该算法需要计算矩形的边缘是否在画布的范围内继续，该边缘是否会与另一个矩形相交？

我们知道：

1. 画布的大小
2. 每个矩形的大小
3. 每个矩形的位置

解决的速度越快越好！我对这个问题很困惑，不知道从哪里开始。

替代文本 http://www.freeimagehosting.net/uploads/8a457f2925.gif

干杯

Answer 1

只需为 X 轴和 Y 轴创建一组间隔即可。然后对于每个新矩形，查看 X 轴或 Y 轴上是否存在相交间隔。 请参阅此处了解实现间隔集的一种方法。

在第一个示例中，水平轴上设置的间隔为 { [0-8], [0-8], [9-10] }，垂直轴上设置的间隔为： { [0-3], [4-6], [0-4] }

这只是一个草图，我在这里抽象了许多细节（例如，通常有人会问一个区间集/树“哪些区间与这个区间重叠” ”，而不是“与这个相交”，但没有什么是不可行的）。

编辑

请观看这个相关的麻省理工学院讲座（有点长，但绝对值得）。
即使您找到更简单的解决方案（比实现增强红黑树），了解这些事物背后的想法也是有好处的。

Answer 2

彼此不平行的线将在某个点相交。计算每条线的斜率，然后确定它们不会与哪些线相交。

从这里开始，然后让我们看看如何优化它。我不确定您的数据是如何表示的，也看不到您的图像。

使用斜率是一种简单的相等检查，这可能意味着您可以利用对数据进行排序。事实上，您可能只需创建一组不同的斜坡即可。您必须弄清楚如何表示数据，以便同一矩形的两个斜率不被视为相交。

编辑：等等..两个边长无穷大的矩形怎么可能不相交？矩形基本上是两条相互垂直的线。如果这些线延伸到无穷大，这不应该意味着它总是与另一条线相交吗？

Answer 3

只要您没有提到您选择解决问题的语言，我就会使用某种伪代码，

其想法是，如果一切正常，那么沿着一个轴的矩形边缘的排序集合应该是一系列非- 重叠间隔。

1. 对所有矩形进行编号，为它们分配单独的 id，
2. 创建一个空的二叉树集合 (btc)。 插入带有信息 btc::insert(key, value) 的整数
3. 这个集合应该有一个方法，可以为所有矩形

foreach rect in rects do
    btc.insert(rect.top, rect.id)
    btc.insert(rect.bottom, rect.id)

4. 节点，请执行以下操作：现在迭代 btc （这将为您提供排序的顺序）

btc_item = btc.first()
do
    id = btc_item.id
    btc_item = btc.next()
    if(id != btc_item.id)
    then report_invalid_placement(id, btc_item.id)
    btc_item = btc.next()
while btc_item is valid

5,7,8 - 重复步骤2,3,4 用于 rect.left 和 rect.right 坐标

Answer 4

我喜欢这个问题。这是我的尝试：

如果可能的话：
从每个矩形创建一个多边形。将每条边视为必须修剪的最大长度的线。使用裁剪算法来检查天气或一条线是否与另一条线相交。例如这个： 线路剪辑

但请记住：如果您发现一个交叉点位于顶点位置，它是有效的。

Answer 5

这是一个想法。不要用 (x, y, width, height) 创建每个矩形，而是用 (x1, y1, x2, y2) 实例化它们，或者至少让它解释这些给定宽度和高度的值。

这样，您就可以检查哪些矩形具有相似的 x 或 y 值，并确保相应的矩形具有相同的辅助值。

---

示例：

您给出的矩形具有以下值：

• 正方形 1：[0, 0, 8, 3]
• 正方形 3：[0, 4, 8, 6]
• 正方形 4：[9, 0, 10, 4]

首先，我们将 Square 1 与 Square 3 进行比较（无碰撞）：

• 比较 x 值
  • [0, 8] 到 [0, 8] 这些完全相同，因此没有交叉。
• 比较 y 值
  • [0, 4] 到 [3, 6] 这些数字都不相似，因此它们不是一个因素

接下来，我们将 Square 3 与 Square 4 进行比较code>（碰撞）：

• 比较x值
  • [0, 8] 到 [9, 10] 这些数字都不相似，因此它们不是一个因素
• 比较 y 值
  • [4, 6] 到 [0, 4] 矩形的共同数字为 4，但 0 != 6，因此发生了碰撞

通过知道我们知道会发生碰撞，因此该方法将结束，但让我们评估一下 Square 1 和 Square 4 以获得额外的清晰度。

• 比较 x 值
  • [0, 8] 到 [9, 10] 这些数字都不相似，因此它们不是一个因素
• 比较 y 值
  • [0, 3] 到 [0, 4] 矩形的共同数字为 0，但 3 != 4，因此存在碰撞

如果您需要任何额外的详细信息，请告诉我:)

Answer 6

呵呵，将重叠间隔答案发挥到极致，您只需确定沿 x 和 y 轴的所有不同间隔即可。对于每条切割线，根据间隔的起始值，沿着它将切割的轴进行上限搜索。如果找不到区间或区间不与线相交，则该线是有效线。

稍微棘手的部分是要认识到有效的切割线不会沿轴与矩形的边界相交，因此您可以将重叠的间隔合并为单个间隔。您最终会得到一个简单的排序数组（您用 O(n) 时间填充该数组）和对每条切割线的 O(log n) 搜索。