Android Question Realtime calculation of distances (POI)

[wl]

I'm looking into writing an application that calculates the nearest POI's from a moving target (similar as application to indicate that one is nearing a speed camera).

I know I can calculate the distance with DistanceTo so basically what I could do is:
on every move (or a move of at least x meters): take the full list of POI's (might be a few thousand), calculate the current distance, sort them and take first one (= the POI that is most close)..

I would expect this is not something that can be done without any optimization: calculating and sorting distances of a few thousand locations each an every time ...
What would be the optimization that could be done ? Of course I can always only recalculate the distance to the previous POI's that were previously the nearest, but this approach would get incorrect the further I move from the original position.

Any idea's ?

Thanks

 

[EnriqueGonzalez]

It should be easier to calculate any poi inside a circle of x radius and calculate only those

 

[wl]

It should be easier to calculate any poi inside a circle of x radius and calculate only those

Thanks I understand, but in order to determine what the POI's in this circle with x radius are, I would need to calculate all of them no ?
And as I need to calculate from a moving target the circle will move along...

 

[tchart]

It should be easier to calculate any poi inside a circle of x radius and calculate only those

A long time ago I wrote an GPS application for Pocket PC that did exatly as you describe. This was for speed cameras.

I will see if I can find the code but from memory I did a rough calculation (Pythagoras) to get an approximate distance to filter out the ones that were too far away. Then for any that were within the filter distance I did the more complex and accurate calculation. This was displayed on a radar type display that rotated around the users position.

 

[tchart]

Oh looks like it was even simpler than that. All I did was compare the latitude minus the user latitude was less than 0.1 degree (roughly 11km) and then the same for longitude.

This is C++ BTW but should be readable for you.

    for(c=0; c<camCount; c++)
    {                       
        if (fabs(camArray[c].lat - dLatitude) < 0.1)
        {
            if (fabs(camArray[c].lon - dLongitude) < 0.1)
            {
                camArrayC[lCount].id = camArray[c].id;
                camArrayC[lCount].speed = camArray[c].speed;
                camArrayC[lCount].type = camArray[c].type;

                DIST_BEAR dbTemp;
                dbTemp = CalcDistanceDelta(dLatitude,dLongitude,camArray[c].lat,camArray[c].lon);
                camArrayC[lCount].distance = dbTemp.distance;
                camArrayC[lCount].bearing = dbTemp.bearing;

                lCount++;
            }
        }
    }

 

[emexes]

I did a rough calculation (Pythagoras) to get an approximate distance to filter out the ones that were too far away

The key here being to avoid the square root, eg if sqr(a*a+b*b) > sqr(c*c+d*d) then a*a+b*b > c*c+d*d

And best use a*a rather than a^2 just in case the compiler somehow misses that optimization and starts using hidden logarithms.

 

[emexes]

calculates the nearest POI's from a moving target

POI plural or singular?

take the full list of POI's (might be a few thousand), calculate the current distance, sort them and take first one (= the POI that is most close)

If you just need the one most close POI, then you can skip the sort: just keep track of the minimum distance as you calculate your way through the list.

An interesting optimization might be to retain a sorted list, and use the knowledge that if you have moved d, then the distance between you and a POI can only have changed (up or down) by (at most) d.

 

[tchart]

My old app was doing this every second (on ancient hardware compared to nowadays) so the code is pretty efficient.

I read the 1000's of cameras into memory then filtered into a second array using the function above to get the closest only.

I also had to keep track of the closest one as well as whether this was in a certain "angle" comapred to the direction of travel (ie whether the vehicle was approaching the target - so as not to pick up detections on other roads nearby etc).