Optimize the algorithm for finding intersection points on 2 roads (lines)

I have a list of Lines that represent Roads, so each road has a "StartingPoint" and "EndingPoint". My goal is to find the "Further" road along each road. A road is ahead of another road if its start point OR the end point falls on top of the start point or end point of another road . For example:

Road A: start point: (0,0) and end point (2,0)
Road B: start point: (2,0) and end point (5,0)
Road C: start point: (2,0) and end point (4.2)

So, the road Further will be:


My current algorthim does this in O (n ^ 2), comparing each starting point of a road to the start and end of another road. How to do it faster. I think road sorting might work, but I'm not sure. Please tell me what you think!

Note: Those who say use Hashmap<Start/EndPoint,Road>

, your solution is still O (N ^ 2).


source to share

5 answers

It depends on what you want to do with the result. The result of your calculation is measured O(#roads^2)

. This means that if you want to iterate over it, you will need it O(#roads^2)

at best. Speaking of which, if you just want to answer questions such as "return all adherence to a given road", you can do so O(#roads)

with the algorithm that you have implemented.



In Java, a is enough HashMap<XYPoint, HashSet<Road>> endPoints

and one more HashMap<Road, HashSet<Road> next

; if your road objects end and start with XYPoint

s. The logic will look like this:

 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);                     


At the end of this procedure, your map next

will contain the following roads for each road. You just need to iterate through this map to create the desired output.

If there are no further roads, the algorithm is O (n). In the worst case (all roads have the same start and end points), this is O (n ^ 2); you can eliminate this by using appropriate equals / hashcode for your roads, at the cost of some additional complexity (you will need to recalculate the repetitions).



In my opinion, the easiest way to do this is to create a Cell class that will represent a specific point of type (x; y). Override the equals and hashCode of the cell, and then simply store the Cell objects in a HashMap to ensure that its elements are retrieved quickly.



There is an O (n log n) algorithm, I'm not sure if there are any excellent ones.

You can:

1) Create a Point class which consists of a 2D point and a pointer to the road where it has an end point (start or end point).

2) Create an array twice as large as your collection of roads

3) Loop on all roads and add a point representing both the start point and the end point to the array - pointed the point of the point to the road that created it.

4) Order the array using your selection. You can use a lot of sorting functions, but since you are writing code, I would say that you are using one that sorts by y first and then uses x to tie-break at y's. So:

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;


For points alone, you should probably rewrite it as non-branching if you want speed.

5) Adjacent points can be the same. The unbiased points are of course not. Run the ordered array in O (n) time. The glasses refer to their roads. Combine as you see fit.



Storing your end result doesn't have to be O (^ 2 roads) sized if you allow 3 things:

  • Keep separate labels for roads that overlap the start point of the road and its end point. You can simply concatenate the two lists together to get the path to the next list by looping through it, or iterate over one and then the other.
  • Share lists between roads. The start point list of one road can be another road start or a list of end points. In other words, for each point, there is one list of all roads that either start or end there.
  • Allow the road to be a member of its own lists (and just ignore it when retrieving the list).

Hash Map Required HashMap<XYPoint, List<Road>>

For each road keep List<Road>

startList and endList

Algorithm (pseudocode):

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
            add road to roadList
        set roadList as either road.startList or road.endList


You only add each road to the list twice. Assuming the hash lookup and addition is O (1) then it should be O (n).