Storing a lot of gps coordinates and comparing distances

I have a GPS module (GY-NEO6MV2) attached to an arduino nano and I am able to get my position (LNG and LAT coordinates) using the code provided in the TinyGPS library.

Here is what I would like to do: I have ~7000 gps coordinates (LNG and LAT coordinates) of specific locations (e.g. stores) in a plain text file. From all the 7000 gps locations I would like to know/calculate the nearest store to my position. With the code on this website that takes two lng,lat pairs I can calculate the distance. So at first I thought I can create a hugh array with 2*7000=14000 values, calculate each distance and determine the nearest store. The problem is 7000 gps coordinates are quiet big (~200kilobytes!) and that is apparently to much for my arduino nano to handle.

How would you approach this? I think I have to use some source of external memory... eeprom? Are there 256kb eeproms out there? Or should I use a sd card+sd card reader? Can I do the calculations in short time (let's say under 10 sec)? I would like to find a cheap solution.

I would use a more capable micro, like the Raspberry Pi. No extra hardware needed, other than the GPS. Unlike Arduino, the RPi supports double precision floating point arithmetic, which makes GPS calculations much easier and much more accurate.

Of course you could build an EEPROM memory or use SD cards with an Arduino, but it would be a lot of work, around 100X slower and cost about the same as an RPi.

For locating the nearest ‘stores’ the single precision floating point calcs of Ardunio is more than adequate.

At least that has been my experience of a lot of field testing and GPS Libraries such as TinyGPS++, which incidently supports the distance calculation direct.

However, retrieving the locations from store, and then doing the calculations at 700 a second, sounds like a challenge.

Did you time how much time it took one of your distance calculations ?

Not yet, still planning.

If you pre-sorted your database eg such that furthest north / furthest west is the first entry, then in increasing distance from that point ( you could do this on a pc before loading it to eg an SD card ) your in-field search would be a lot quicker - eg with a binary search which would reduce your number of comparisons from 7000 to (edit) 2*log(2) 7000 ie about 28 tests.

To make things even easier make 2 databases ( sd cards store a lot) - 1st list in order of furthest north southwards, and a second with furthest west going eastwards...

This should be feasible - after all, your stores don't move about! redo the database every time you add/remove a store..

The quicksort example in the 'C' bible would do the sorting job... or even ( with a bit of fiddling) the old DOS 'sort'. Or ( shows my age!) an AEDIT macro....

I did something like this for 'laserscan' in the uk ages ago - they made digital maps for eg the ordnance survey. I had to certify that my code would survive the anticipated millenium bug. I replied that unless unix blew up it should be OK.... it was.



ps if your area includes the Greenwich meridian it makes things a little more complicated - but not too bad...

Have you tried reading each record from an SD card, calculating distance, and keeping the closest one (or few)? If it only takes a few seconds to do a brute force search then there is no need to do anything fancier. The SD card would allow you to include more information about each store, like address, phone number, operating hours.

You've still got to load the database onto an sd card - eg from a pc - so why not do the sort first...?

Quite right about the database as an array of structures containing all the details - good idea.