# Finding appropriate positions for coordinates added to a coordinate-list

I am looking for the most efficient way to find the appropriate position of a geographical coordinate in a list of other (geographical) coordinates forming a route.

That may sound a little cryptical, but consider this:

Conditions
I have the following data to work with:

• A list of (cartesian) coordinates describing a geographical route (the coordinate-list)
• A list of (cartesian) coordinates for points of interest (POIs) spread out along the route (the POI-list)

What I am trying to do is merge the coordinates from the POI-list into the coordinate-list at their appropriate positions, so that the coordinate-list is ordered in the same order as I would reach each coordinate, including the POIs, if I were to travel the route.

I know in which order the POIs should be "added".
I.e. the second POI should have a higher index than that of the first POI and so on.

Current Approach
What I am currently doing is iterating through the whole coordinate-list once per coordinate in the POI-list, and for each coordinate calculating the distance between the POI and the line formed by the coordinate and the next coordinate in the coordinate-list.

Consider the following code:

``````shortestDistance = /* distance between the first two coordinates */;
index = 0;

for(POI poi : poiList) {
for(i = 0; i < coordinateList.size(); i++) {
Line line = new Line(coordinateList.get(i), coordinateList.get(i + 1));
int distance = distanceBetween(line, poi);

if(distance < shortestDistance) {
shortestDistance = distance
index = i
}
}

/* "index" now represents the index of the "coordinateList" at which the POI-coordinate should be added */
}
``````

In my eyes this solution is extremely ineficcient, and there has to be a faster way of doing it...

The Requirement
Similar to the current solution, the new solution must be able to handle about all situations that an automatically generated car-route can cause, for example situations where the route makes a U-turn and goes back into the opposite direction close to itself.

The solution should be as fast as possible.