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)但这需要太长时间。是否有一个好的算法/数据结构可以帮助减少运行时间？

尝试：
范围树：看起来很自然，因为它支持范围查询（具有相似斜率的线）。但是不支持插入/删除。

R树：R树支持使用矩形查询靠近的元素。使用它，我可以首先找到边界框中的所有线，然后过滤掉斜率差异 > epsilon 或距离 > epsilon2 的线。但是我找不到关于实现的好的描述（搜索看起来有据可查，但插入/删除非常模糊）

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

标签： algorithmdata-structureslanguage-agnosticcomputational-geometry

Answer 1

您可以将投影对偶性与您最喜欢的邻近结构（kd-tree、cover tree 等）一起使用，将段聚类成几乎共线的组。然后对于每个组，您可以使用标准扫描线算法来计算区间的并集作为不相交区间的列表。

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

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