0

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.
Multi-threading is allowed!

  • Traveling Salesman? – Robert Harvey May 21 '18 at 15:54
  • @RobertHarvey Yeah, I thought so too, but that's not it. He already has a predetermined route, and for each POI he wants to find the segment of the route that passes closest to it (or so I read the code). I'm not particularly sure how to reduce that to vanilla traveling salesman. – Ordous May 21 '18 at 17:08
  • @Ordous Correct, I already know the route. The POIs are always located very close to the route, I just need to find their appropriate positions in the list, if this makes sense. – Daniel Kvist May 23 '18 at 12:06
  • @RobertHarvey I'm not sure how I would adapt this for my use case, feels like it would maybe even be slower. I also know the order of the POIs, i.e. the order they will be in when added to the route, this may open for some more solutions! – Daniel Kvist May 23 '18 at 12:11
  • How long does your code take to execute as currently written, and how long do you need it to take? – Robert Harvey May 23 '18 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.