Calculating approximation to a point

Hi guys

Im working with the gps module, and I want to know how can I calculate the approximation to a given coordinate to announce a deviation in the way.

I know that calculating the distance to that point is an option,

but if for example I have 1000 possible deviations, if I have to perform a calculation each time that I get a position from the gps, this will be very slow, knowing that I have 1000 coordinates to evaluate.

there are any option that allows me to optimize this problem.

Thank you

If I understand the post correctly, you want to know the error in the distance to travel, given possible errors in the coordinates of the location to which you are traveling.

This is called “error propagation” or “propagation of uncertainty” and is straightforward to do mathematically. It does require use of the calculus (taking derivatives) and in your case, the distance is a complicated formula that depends on the latitude and longitude of the target. I’m sure someone has already worked out the exact formula but haven’t looked for a specific example.

For the general approach google “error propagation” and the first page will turn up many hits describing the general approach. The Wikipedia entry is OK – look at the “example” for the two dimensional case Propagation of uncertainty - Wikipedia

Hi jremington

Thanks for you answer.

I'm using a simple formula to calculate the distance.

The problem is, for example, if I have 1000 points

deviation_coord_1 deviation_coord_2 deviation_coord_3 deviation_coord_4 ... deviation_coord_1000

if I'm 1km before of the first deviation, how can I know what is the most near deviation of the above list, without have to check each deviation_coordinate?

I say this because if I have to check if coordinate, it will be very tedious and slow.

For example, how can a gps in a car, that you have to turn right in 800ft?

if I'm 1km before of the first deviation, how can I know what is the most near deviation of the above list, without have to check each deviation_coordinate?

You have to check every one.

an old thread discussing haversine - http://forum.arduino.cc/index.php?topic=45760.0 -

Hi guys Thanks for your answers.

I understand what you are telling.

I have further questions.

I have an arduino mega 2560. What is the best way to keep in arduino from 1000 to 3000 coordinates knowing that the arduino doesn't have enough memory to keep my code and all coordinates?

Arduino mega only have 256KB in flash memory, and other versions just 32KB.

Thanks

if the coordinates are static you can use PROGMEM to store them in flash

if the coordinates can change runtime you might derive a compression scheme or storage on an SD

E.g. if all coordinates are within the square (100,100) (100,102) (102,102) (102,100) you can remove the common offset and store (0,0) (0,2) (2,2) (2,0) . Maybe better to take a midpoint so the square becomes (-1,-1) (-1,1)(1,1)(1,-1) as then the signbit is also used to hold one bit of precision.

Remove the common offset while parsing the numbers is part of the trick.


If there are repetitions in coordinates e.g. they form a grid you can use lookup tables. e.g.

float val[256] = { 125.623923, 163.456789, 163.23456, ... }; // will need 1000 bytes (use datatype long for more digits of course)

struct { byte x; byte y; } point[4000]; // 8000 bytes

point[0] = {0,1} => (125.623923, 163.456789) point[1] = {1,1} => (163.456789, 163.456789) point[2] = {2,1} => (163.23456, 163.456789) point[2] = {2,2} => (163.23456, 163.23456)

in total 1000 + 8000 bytes = 9K traditionally you would need 4000 * 2 * 4 bytes = 32K bytes so compression factor of approx 3.5

if certain amount of error is acceptable you can define your own grid and round every point to a grid point.

Note that these two methods can also be combined.

Hi guys,

Thanks for your prompt replies.

I'll try what you are telling.

Thanks again.

If your co-ordinates are not fixed and cant be put in PROGMEM, you could use an SD card to store them, but this will make processing slower and more complicated as you'd need to load them from the card in batches e.g. of 128 coords (or whatever will fit in memory)

Re: processing time.

It depends how quick you need the response, and what processing you are doing on each point ie whether you are doing complex floating point maths or just simple addition an subtraction.

You can probably speed the maths by long's instead of floats e.g. unsigned long is 0 to 4,294,967,295 and the earth is just over 40,000 in circumference, this gives the accuracy as 40,000 km / 4,294,967,295 which is around 9mm ! (If my maths is correct ;-)