java - 优化算法以在二维道路(线)中找到交点

Question

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

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

接下来的道路将是:

A 下一个 { B , C}
B 下一个 { A }
C 下一个 { A }

我目前的算法是通过将一条道路的每个起点与另一条道路的起点和终点进行比较，在 O(n^2) 中完成的。怎样才能让它更快。我认为对道路进行分类可能会奏效，但我不确定。请告诉我你的想法!

注意:那些说的用Hashmap<Start/EndPoint,Road>你的解决方案仍然是 O(N^2)。

Answer 1

这取决于你想对结果做什么。计算结果的大小为 O(#roads^​​2)。这意味着如果你想迭代它那么你最多需要 O(#roads^​​2) 。这就是说，如果您只想能够回答诸如“返回给定道路的所有邻接”之类的问题，那么您可以使用您实现的算法在 O(#roads) 中做到这一点。