合并相似项目的数据 structure/algorithm
Data structure/algorithm for merging similar items
要求：
给定二维平面中的一堆线段，我需要能够合并所有彼此相似或相等的线段。
例如，如果我有两条线段 (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) 但这需要很长时间。是否有一个好的 algorithm/data 结构可以帮助减少 运行 时间？
尝试次数：
Range tree：看起来很自然，因为它支持范围查询（具有相似斜率的线）。但是 insert/delete 不受支持。
R tree：R tree支持使用矩形查询相邻的元素。使用它，我可以首先找到边界框内的所有线，并过滤掉斜率差 > epsilon 或距离 > epsilon2 的线。但是我找不到关于实现的很好的描述（搜索看起来有据可查但 insert/delete 非常模糊）
B 树：B 树看起来很有前途，但我的用例似乎不是它的主要用途。不确定这是否是正确的方法。
您可以将 projective duality 与您最喜欢的邻近结构（kd 树、覆盖树等）结合使用，将线段聚类成几乎共线的组。然后对于每个组，您可以使用标准扫描线算法来计算区间的并集作为不相交区间的列表。
为了计算包含 (a, b) 和 (c, d) 的直线的投影坐标，我们将端点嵌入到投影 space 中作为 (a, b, 1) 和 (c, d, 1)然后计算 cross product。投影坐标的问题是它们不是唯一的。我天真的建议是使用 3D 中的单位球体作为覆盖 space 通过相对于欧几里得范数进行归一化并在其对映点复制点。
换句话说，我们将 (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).
将 Ax+By+C=0 映射到 (A,B,C) 的问题是，如果斜率略有不同的两条相似线段离原点很远，C 之间的差异会变大，从而阻止这两个部分不会聚集成一个。
另一方面，如果两条线段的斜率相差很大，如果其中一条线段非常短，仍然可以从视觉上考虑'similar'。
我怀疑是否有任何对偶映射->聚类->过滤方法可以完全解决这个问题。考虑以下两种极端情况：
- 线段AB，A处的无限小线段，B处的无限小线段--> 属性等式不成立-->永远不能按原样聚类线段-- > 必须先对线进行聚类，然后再处理线段
- AB线和CD线的斜率相似。如果线段A'B'和C'D'靠近交点，则为'similar'；否则，它们不是 --> 聚类后不能处理线段
所以矛盾。
在我看来，O(N^2) 可能是你能得到的最好的，因为对于每个线段，最坏的情况是在整个线袋中搜索（或剩下的）。尽管如此，假设线段是随机分布的，使用一些 space 分区技术你可以获得更好的平均情况复杂度。
你试过 Sweep line algorithm? You can find/count/detect line segment intersections which definitely sounds like your first step (detect if there's an intersection then check slopes). You could solve your problem in O((n+k)logn) (where k is the number of intersections) by using the Bentley-Ottman algorithm 吗？您基本上对线段进行排序，然后按该顺序用线滑动平面，并在每个交叉点停下来。
还有一点，可以计算斜率，然后可以字典序排序，先按斜率，再按x坐标（或者投影到这样的斜率通过0点的直线），然后遍历段以该顺序。然后您可以做一个简单的 "line sweep"，只需验证段的距离并合并。您可以为斜率添加一些误差，因此您也可以将相似的斜率放在同一个桶中。
要求：
给定二维平面中的一堆线段，我需要能够合并所有彼此相似或相等的线段。
例如，如果我有两条线段 (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) 但这需要很长时间。是否有一个好的 algorithm/data 结构可以帮助减少 运行 时间？
尝试次数：
Range tree：看起来很自然，因为它支持范围查询（具有相似斜率的线）。但是 insert/delete 不受支持。
R tree：R tree支持使用矩形查询相邻的元素。使用它，我可以首先找到边界框内的所有线，并过滤掉斜率差 > epsilon 或距离 > epsilon2 的线。但是我找不到关于实现的很好的描述（搜索看起来有据可查但 insert/delete 非常模糊）
B 树：B 树看起来很有前途，但我的用例似乎不是它的主要用途。不确定这是否是正确的方法。
您可以将 projective duality 与您最喜欢的邻近结构（kd 树、覆盖树等）结合使用，将线段聚类成几乎共线的组。然后对于每个组，您可以使用标准扫描线算法来计算区间的并集作为不相交区间的列表。
为了计算包含 (a, b) 和 (c, d) 的直线的投影坐标，我们将端点嵌入到投影 space 中作为 (a, b, 1) 和 (c, d, 1)然后计算 cross product。投影坐标的问题是它们不是唯一的。我天真的建议是使用 3D 中的单位球体作为覆盖 space 通过相对于欧几里得范数进行归一化并在其对映点复制点。
换句话说，我们将 (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).
将 Ax+By+C=0 映射到 (A,B,C) 的问题是，如果斜率略有不同的两条相似线段离原点很远，C 之间的差异会变大，从而阻止这两个部分不会聚集成一个。
另一方面，如果两条线段的斜率相差很大，如果其中一条线段非常短，仍然可以从视觉上考虑'similar'。
我怀疑是否有任何对偶映射->聚类->过滤方法可以完全解决这个问题。考虑以下两种极端情况：
- 线段AB，A处的无限小线段，B处的无限小线段--> 属性等式不成立-->永远不能按原样聚类线段-- > 必须先对线进行聚类，然后再处理线段
- AB线和CD线的斜率相似。如果线段A'B'和C'D'靠近交点，则为'similar'；否则，它们不是 --> 聚类后不能处理线段
所以矛盾。
在我看来，O(N^2) 可能是你能得到的最好的，因为对于每个线段，最坏的情况是在整个线袋中搜索（或剩下的）。尽管如此，假设线段是随机分布的，使用一些 space 分区技术你可以获得更好的平均情况复杂度。
你试过 Sweep line algorithm? You can find/count/detect line segment intersections which definitely sounds like your first step (detect if there's an intersection then check slopes). You could solve your problem in O((n+k)logn) (where k is the number of intersections) by using the Bentley-Ottman algorithm 吗？您基本上对线段进行排序，然后按该顺序用线滑动平面，并在每个交叉点停下来。
还有一点，可以计算斜率，然后可以字典序排序，先按斜率，再按x坐标（或者投影到这样的斜率通过0点的直线），然后遍历段以该顺序。然后您可以做一个简单的 "line sweep"，只需验证段的距离并合并。您可以为斜率添加一些误差，因此您也可以将相似的斜率放在同一个桶中。