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

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 tree:看起来很自然，因为它支持范围查询(具有相似斜率的线)。但是不支持插入/删除。

R tree:R tree支持使用矩形查询相邻的元素。使用它，我可以首先找到边界框内的所有线，并过滤掉斜率差 > epsilon 或距离 > epsilon2 的线。但是我找不到关于实现的很好的描述(搜索看起来有据可查但插入/删除非常模糊)

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

Answer 1

您可以使用 projective duality使用您最喜欢的邻近结构(kd 树、覆盖树等)将线段聚类成几乎共线的组。然后对于每个组，您可以使用标准扫描线算法来计算区间的并集作为不相交区间的列表。

为了计算包含 (a, b) 和 (c, d) 的直线的投影坐标，我们将端点嵌入到投影空间中作为 (a, b, 1) 和 (c, d, 1) 然后计算 cross product .投影坐标的问题是它们不是唯一的。我天真的建议是通过相对于欧几里德范数进行归一化并在其对映点复制点，将 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)。