java优化算法在二维道路（线）中寻找交点

Question

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

道路A：起点：（0,0）和终点（2,0）
B路：起点（2,0）和终点（5,0）
道路C：起点（2,0）和终点（4,2）

所以接下来的道路是：

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

我目前的算法是在O（n^2）中，通过比较一条路的每个起点和另一条路的起点和终点。怎样才能让这更快。我认为整理道路可能有用，但我不确定。请告诉我你的想法

注意：那些说使用Hashmap<Start/EndPoint,Road>你的解决方案仍然是O（N^2）

Answer 1

有一个O（n logn）算法，我不确定是否有更好的算法

你可以：

1）创建一个点类，该点类由一个二维点和一个指向其端点（起点或终点）的道路的指针组成

2）创建一个数组，其大小是道路集合的两倍

3）在所有道路上循环，并将代表起点或终点的点添加到数组中——将所述点返回到创建该点的道路

4）使用您选择的排序来订购阵列。你可以使用很多排序函数，但既然你在写代码，我想说你使用的是一个先按y排序，然后用x在相等的y上进行tiebreak的函数。所以：

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）时间内运行有序数组。点指的是他们的道路。按你认为合适的方式组合

Answer 2

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

Answer 3

如果允许以下三种情况，则最终结果的存储大小不必为O（roads^2）：

• 为重叠道路起点和终点的道路存储单独的子列表。你可以将两个列表连接在一起，在查找时得到一条道路的完整下一个列表，或者遍历其中一个，然后遍历另一个
• 在道路之间共享列表。一条道路的起点列表可能是另一条道路的起点或终点列表。换句话说，对于每个点，都有一个单一的列表，其中列出了从那里开始或结束的所有道路
• 允许一条道路成为其自身列表的成员（在检索列表时忽略它）

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

对于每条道路，存储List<Road>列表和结束列表

算法是（伪代码）：

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）

Answer 4

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

 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）；你可以通过为你的道路使用合适的equals/hashcode来消除这种情况，代价是增加一些额外的复杂性（你需要计算重复次数）

Answer 5

在我看来，实现这一点最简单的方法是创建一个表示某个点的类单元格，如（x；y）。覆盖单元格的equals和hashCode，然后简单地将单元格对象存储在一个HashMap中，以保证快速检索其元素