7

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

我们知道：

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

解决方案越快越好！我很坚持这个，真的不知道从哪里开始。

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

干杯

4

6 回答 6

6

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

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

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

编辑

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

于 2010-07-08T12:36:17.387 回答
2

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

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

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

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

于 2010-07-08T12:35:08.920 回答
1

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

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

  1. 为所有矩形编号，为它们分配单独的 ID
  2. 创建一个空的二叉树集合（btc）。这个集合应该有一个方法来插入一个带有 info btc::insert(key, value) 的整数节点
  3. 对于所有矩形，请执行以下操作：

foreach rect in rects do
    btc.insert(rect.top, rect.id)
    btc.insert(rect.bottom, rect.id)
  1. 现在遍历 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 - 对 rect.left 和 rect.right 坐标重复步骤 2,3,4

于 2010-07-08T12:49:19.453 回答
1

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

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

但请记住：如果您找到位于顶点位置的交点，则它是有效的。

于 2010-07-08T13:01:22.407 回答
1

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

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

例子：

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

  • 正方形 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碰撞）：

  • 比较 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，因此，有碰撞

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

于 2010-07-08T13:08:06.913 回答
0

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

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

于 2010-07-09T06:53:40.813 回答