合并相似项的数据结构/算法

Question

要求：

给定二维平面上的一系列线段，我需要能够合并所有相似或相等的线段。

例如，如果给我两个线段，(0, 0) - (1, 1)和(1, 1) - (2, 2)。这两条线连在一起，有着相同的斜率。因此，我可以将这两者合并成一行(0, 0) - (2, 2)

用于线段(0, 0) - (1, 1)和(1.01, 1) - (2, 2)。尽管它们的斜率有一点不同，而且它们没有连接，但它对人的眼睛没有那么明显，所以我仍然会将这两者合并到(0, 0) - (2, 2)中以换取性能。

用于线段(0, 0) - (1, 1)和(0.5, 0.5) - (0.6, 0.6)。后者只是前者的一部分，因此只删除后者而只保留前者是安全的。

显然，我可以用残酷的武力方式O(n^2)，但这需要太长时间。是否有一个好的算法/数据结构可以帮助减少运行时间？

尝试：

Range树:因为它支持范围查询(具有相似斜率的行)，所以它似乎是一种自然的匹配。但是，不支持插入/删除。

R树:r树支持使用矩形查询关闭的元素。使用此方法，我可以首先找到绑定框中的所有行，然后筛选出斜率差> epsilon或距离> epsilon2的行。然而，我找不到关于实现的好的描述(搜索看起来有很好的文档，但是插入/删除非常模糊)

B树:B树看起来很有希望，但我的用例似乎不是它的主要用途。不确定这是否是正确的方法。

Answer 1

您可以将投射对偶性与您最喜欢的邻近结构(kd-树、覆盖树等)一起使用。将这些片段聚为接近共线的组。然后，对于每个组，您可以使用标准的扫描线算法来计算间隔的合并，作为不相交间隔的列表。

为了计算包含(a, b)和(c, d)的直线的投影坐标，我们将端点嵌入到射影空间中，如(a, b, 1)和(c, d, 1)，然后计算交叉积。投影坐标的问题是，它们并不是唯一的。我天真的建议是使用3D中的单位球面作为覆盖空间，方法是对欧几里德范数进行归一化，并复制其对位点。

换句话说，我们将(a, b) - (c, d)映射到(x', y', z')和(-x', -y', -z')，其中(x, y, z) = (b - d, c - a, ad - bc)和x' = x/sqrt(x^2+y^2+z^2)，y' = y/sqrt(x^2+y^2+z^2)和z' = z/sqrt(x^2+y^2+z^2)。

Answer 2

你试过用扫描线算法吗？您可以找到/计数/检测线段交叉口，这听起来肯定像您的第一步(检测是否有一个交叉口，然后检查斜率)。通过使用n+k，您可以在O(n+k)logn)(其中k是交叉口的数目)中解决问题。你基本上把你的线段排序，然后按顺序划一条线，然后在每一个交叉处停下来。

还有一件事，你可以计算斜率，然后你可以用字典法排序，首先是斜率，然后是x坐标(或者用这样的斜率通过0点投影到直线上)，然后按照这个顺序遍历这些段。然后，您可以做一个简单的“行扫描”，只需验证段的距离和合并。您可以在斜率中添加一些错误，因此您也可以将类似的斜率放在同一个桶中。

Answer 3

将线Ax+By+C=0映射到(A，B，C)的问题是，如果两个斜率略有不同的相似线段离原点很远，C之间的差异就会变大，从而使两个线段不能聚成一个。

另一方面，如果两条线段的斜率相差很大，如果其中一段极短，则仍可视为视觉上的“相似”。

我怀疑任何二元映射->聚类->过滤方法是否能完全解决这个问题。考虑以下两种极端情况：

• 线段AB，A处的无限小线段，B->处的无限小线段，等价线的性质不成立->不能按原样对线段进行聚类，必须先对线段进行聚类，然后再处理线段。
• AB线和CD线具有相似的坡度。如果段A'B‘和C'D’接近交点，它们是“相似的”；否则，它们在聚类后不能处理-->线段。

因此产生了矛盾。

在我看来，O(N^2)可能是你能得到的最好的，因为对于每一个线段，最坏的情况是搜索整包线(或其余的线)。不过，如果线段是随机分布的，那么使用一些空间分区技术可以得到更好的平均情况复杂度。