# 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:

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

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

+3

source to share

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.

+3

source

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

0

source

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.

0

source

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.

0

source

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]
If null then
else
```

```

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

0

source