# Android QuestionRealtime calculation of distances (POI)

#### wl

##### Well-Known Member
Longtime User
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

##### Well-Known Member
Longtime User
It should be easier to calculate any poi inside a circle of x radius and calculate only those

#### wl

##### Well-Known Member
Longtime User
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...

Last edited:

#### tchart

##### Well-Known Member
Longtime User
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

##### Well-Known Member
Longtime User
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.

C++:
``````    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

##### Expert
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.

wl

#### emexes

##### Expert
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.

wl

#### tchart

##### Well-Known Member
Longtime User
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).

Replies
2
Views
260
Replies
6
Views
2K
Android Question GPS app distance calculation
Replies
1
Views
684
Replies
4
Views
2K
Replies
22
Views
7K