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!

Daniel Kvist
  • 361
  • 1
  • 3
  • 7
  • [Traveling Salesman?](https://en.wikipedia.org/wiki/Travelling_salesman_problem) – 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
  • @RobertHarvey Given a list of 40k coordinates and 400 POIs (a route of about 2.700 kilometers), the loop takes roughly 96 seconds to complete. Please note though, **1)** it is ran on Android, **2)** my loop takes in accountance some other parameters too. Thus, I am just looking for a good principle to use, that I can then apply to my code. As for the time requirement, I would say "faster". – Daniel Kvist May 24 '18 at 13:06
  • "Faster" is not a requirement; it's a wish. I can shave one second off that 96 seconds and meet that "requirement." – Robert Harvey May 24 '18 at 14:57
  • @RobertHarvey Then be my guest! I could as well have said five or 50 seconds, but that would be a wish too, wouldn't it? :) With that being said, 30 seconds would be a great goal! – Daniel Kvist May 26 '18 at 17:23

0 Answers0