优化算法以在2D道路（线）中查找交点

Question

我有一份道路列表，每条道路都有一个“起点”和一个“终点”。我的目标是找到每条道路的“下一条”道路。如果一条道路的起点或终点恰好落在另一条道路的起点或终点上，则该道路是另一条道路的“下一条”道路。例如：

道路A：起点为(0,0)，终点为(2,0) 道路B：起点为(2,0)，终点为(5,0) 道路C：起点为(2,0)，终点为(4,2)

因此，道路Next将是：

A NEXT { B , C } B NEXT { A } C NEXT { A }

我的当前算法通过将每条道路的起点与另一条道路的起点和终点进行比较，以O(n^2)的时间复杂度实现。如何使这个过程更快？我认为对道路进行排序可能有效，但我不确定。请告诉我您的想法！

注意：那些建议使用HashMap的人，您的解决方案仍然是O(N^2)。

- Hirad Roshandel

---

你能否在一个使用起点/终点作为键，以该点为值的所有道路的multimap中“索引”道路？从那里开始，构建有向图应该很容易。 - David Ehrmann

我也不明白你所说的“每条路都有起点和终点”的意思。为什么不让它可以双向移动呢？ - Lysenko Andrii

@LysenkoAndrii 因为一条路可以是双向的。 - Hirad Roshandel

@HiradRoshandel 坐标范围有限制吗？例如 (x, y) 其中 x，y <= 10^9 ? - shole

Answer 1

这取决于您希望如何使用结果。您的计算结果的大小为O(#roads^2)。这意味着，如果您想对其进行迭代，则最好需要O(#roads^2)。但是，如果您只想能够回答类似“返回给定道路的所有相邻道路”的问题，则可以使用您实现的算法在O(#roads)内完成。

- Benjy Kessler

---

在我的情况下，找到下一个不是O(1)，因为我想要找到所有道路的下一个，所以再次遍历所有道路和所有集合就变成了O(n^2)对吧？ - Hirad Roshandel

是的，从技术上讲，由于addAll调用，查找单条路线的下一个节点的时间复杂度为O(n)。因此，查找所有道路的时间复杂度为O(n^2)，比你的O(n^3)更好。 - Benjy Kessler

我的时间复杂度也是O(n^2)。我使用嵌套的for循环。 - Hirad Roshandel

Answer 2

在Java中，一个HashMap<XYPoint, HashSet<Road>> endPoints和另一个HashMap<Road, HashSet<Road> next应该足够了；假设你的Road对象有一个结束和开始的XYPoint。逻辑如下：

 for each road R,
     add it, using its starting point, to the endPoints map; and
             for each road X with a co-incident endpoint, 
                 next.put(R, X); next.put(X, R);                     
     add it, using its ending point, to the map endPoints map; and
             for each road X with a co-incident endpoint, 
                 next.put(R, X); next.put(X, R);                     

在此过程结束时，您的next映射将包含每条道路的下一条道路。您只需迭代此映射以生成所需的输出即可。

如果没有下一条道路，则算法为O(n)。在最坏情况下（所有道路具有相同的起点和终点），它是O(n^2)；您可以通过为您的Roads使用适当的equals/hashcode来消除这种情况，但需要付出一些额外的复杂性（您需要计算重复）。

- tucuxi

---

这不是和Benjy Kessler上面的答案一样吗？仍然是O(n^2)，对吧？ - Hirad Roshandel

它类似于 - 我在他发布之前开始写，但是完成比他晚。 - tucuxi

Answer 3

有一个O(n log n)的算法，我不确定是否有更优秀的。

你可以：

1）创建一个Point类，包含一个2D点和指向它所在道路（起点或终点）的指针。

2）创建一个比你的道路集合大两倍的数组。

3）循环遍历所有道路，并将表示起点或终点的Point添加到数组中 - 让该Point指向创建它的道路。

4）使用您选择的排序方法对数组进行排序。您可以使用许多排序函数，但由于您正在编写代码，我建议您使用首先按y排序，然后在相等的y上使用x进行打破平局的排序函数。所以：

if ( a.y < b.y ) return -1;
if ( a.y > b.y ) return 1;
if ( a.x < b.x ) return -1;
if ( a.x > b.x ) return 1;
return 0;

如果你在意速度，那么仅对于点应该将其重写为非分支形式。

5) 相邻的点可能相同。不相邻的点肯定不同。在 O(n) 的时间内遍历有序数组。点引用它们的道路。按照您认为合适的方式进行组合。

- Jesse

Answer 4

在我看来，最简单的方法是创建一个称为“Cell”的类，代表像(x;y)这样的特定点。重写Cell的equals和hashCode方法，然后将Cell对象简单地存储在HashMap中，以保证高速检索其元素。

- Lysenko Andrii

Answer 5

如果你允许以下三点，那么你的最终结果的存储空间大小不必为O(roads^2)：

• 为与某个道路的起始点和终点重叠的道路分别存储子列表。当查找时，你可以将这两个列表简单地连接在一起以获取道路的完整下一个列表，或者先迭代一个列表再迭代另一个。
• 在道路之间共享列表。一个道路的起始点列表可能是另一个道路的起点或终点列表。换句话说，对于每个点，都有一个包含所有从该点开始或以该点结束的道路的列表。
• 允许一条道路成为其自身列表的成员（在检索列表时忽略它）。

你需要的哈希映射是 HashMap<XYPoint, List<Road>>

对于每条道路，存储List<Road> startList和endList

算法如下（伪代码）：

For each road in list
    For point in [start, end]
        Look up List<Road> roadlist from hash map based on point X,Y
        If null then
            roadlist = new List<Road>
            add road to roadlist
            add roadlist to hash map
        else
            add road to roadList
        set roadList as either road.startList or road.endList

你只需要将每条路添加到列表中两次。假设哈希查找和添加的时间复杂度为O(1)，那么这个操作应该是O(n)。

- samgak