一个解决简单(?)数组问题的算法

Question

一个解决简单(?)数组问题的算法

algorithmarrayspseudocode

7

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

我们知道：

画布的大小
每个矩形的大小
每个矩形的位置

解决方案越快越好！我卡在这个问题上了，不知道从哪里开始。 alt text http://www.freeimagehosting.net/uploads/8a457f2925.gif 干杯

- Tom Gullen

3

你能更清楚地解释一下数组如何使用吗？我不明白它是如何将所有的1识别为单独的矩形。 - Justian Meyer

1

和 @Justian Meyer 一样的问题，再加上我的一个问题：你到底需要输出什么？如果一个矩形的边缘与另一个矩形相交并且它们的长度增加，是简单地输出“是”或“否”，还是报告每条线可能的交点？ - IVlad

1

1代表矩形的一个部分。每个矩形都是一个类，具有X、Y坐标和高度/宽度值。脚本循环每个矩形并将其添加到数组中。我这样做的原因是，如果两个矩形重叠，则其中一个单元格的值将大于1。 - Tom Gullen

我有些困惑...如果两个矩形的边无限延伸，它们怎么可能不相交呢？每个矩形都有两条互相垂直的线。假设R1的斜率为A和B，R2的斜率为C和D。如果A和C平行，那么A一定会与D相交。如果A和C不平行，那么A一定会与C相交。 - NG.

你应该看一下“SAT”（分离轴定理）。 - fatehmtd

显示剩余4条评论

6个回答

2

不平行的线条将在某一点相交。计算每条线条的斜率，然后确定它们不会相交的线条。

从这里开始，让我们看看如何进行优化。我不确定您的数据是如何表示的，并且我无法查看您的图像。

使用斜率进行简单的相等性检查，这可能意味着您可以利用对数据进行排序。实际上，您可以只创建一组不同的斜率。您需要想出如何表示数据，以便不将同一矩形的两个斜率计算为相交。

编辑：等等...如果两个边界延伸到无限远的矩形没有相交，那么怎么可能？矩形基本上是两条相互垂直的线条。如果将这些线条延伸到无穷远，那么它不应该始终与另一个相交吗？

- NG.

抱歉，“无限”这个词不对，我是指“在画布范围内进行”。有时候我也看不到那张图片，尝试刷新页面，大多数情况下可以显示出来。 - Tom Gullen

1

只要你没有提到你选择用哪种语言来解决问题，我将使用某种伪代码

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

为所有矩形编号，分配它们各自的ID
创建一个空的二叉树集合（btc）。此集合应具有插入整数节点的方法，其信息为btc::insert(key, value)
对于所有矩形，执行以下操作：


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

现在遍历比特币（这将给你一个排序的顺序）。


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坐标

- ULysses

二叉搜索树还需要一个额外的容器，排序实际上可能不需要它。
排序是O（n log n），在bst中插入n项也是O（n log n）。
平衡树在实践中比排序算法慢得多，仅对于多个查询有用。
在您的实现中，每个bst查询是o（n），因此对于多个查询而言，bst并不比排序更好。区间树可能是，但也仅限于多个查询。

- IVlad

好的，确定两种方式都需要一个额外的容器，问题是您需要对矩形序列进行迭代多少次。如果使用排序，则首先填充容器o（n），然后对容器进行排序o（n log n）。如果使用树，则只需将树填充o（n log n）。 - ULysses

不需要，使用迭代器遍历树是一个O(1)的操作。 - ULysses

@ULysses - 你的意思是你代码中的 do .. while 循环是 O(1) 吗？ - IVlad

IVlad，我想我们刚刚讨论过这个问题，你又说它更慢。不，它不是，看看我的先前评论就知道为什么了。在这种情况下使用树可能对你来说看起来很奇怪，但这并不意味着它是低效的。 - ULysses

显示剩余5条评论

1

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

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

但请记住：如果您找到一个在角点位置的交点，则它是有效的。

- InsertNickHere

1

这里有一个想法。不要使用 (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]

首先，我们比较方块1和方块3（没有碰撞）:

比较x值
- [0, 8]和[0, 8]完全相同，所以不存在交叉。
比较y值
- [0, 4]和[3, 6]中没有任何相似的数字，因此它们不是一个因素。

接下来，我们比较方块3和方块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，因此发生了碰撞

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

- Justian Meyer

看起来这是一个很好的解决方案，我会测试一下！ - Tom Gullen

这种方法将导致每个矩形与每个矩形进行比较。这不是高效的，因为它会产生n(n-1)/2个矩形比较，这是所有四个坐标的o(n^2)比较。 - ULysses

@ULysses：我在这个讨论串的早些评论中提到，我的概念并不是为了效率而设计的，这是真的。我的目标是以尽可能简单的方式呈现这个概念，有时候这包括一个缓慢的逐步方法。你完全可以像Dimitris在他的回答中提到的那样执行，这将成本要低得多。 - Justian Meyer

0

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

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

- MSN

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dimitris Andreou · Accepted Answer

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

在您的第一个示例中，水平轴上的区间集将是{ [0-8], [0-8], [9-10] }，垂直轴上的区间集将是{ [0-3], [4-6], [0-4] } 这只是一个草图，我在这里抽象了许多细节（例如，通常人们会询问一个区间集/树“哪些区间与此重叠”，而不是“与此相交”，但没有做不到的事情）。编辑请观看这个相关的MIT讲座（有点长，但非常值得）。即使您找到比实现增强红黑树更简单的解决方案，也了解这些东西背后的想法是好的。