Hi there,
i am trying to find a way to get the closest of hundred thousand points from a textfile (lat/lon coordinates) on an sd card to an actual gps location.
some time ago i did something similar, but with muuuch more powerfull hardware (pc) and nodejs. back then i used a kd-tree to quickly find the closest point after converting all points to xy.
this time i think i will not have the ability to convert the points to a xy coordinate system (because they are too far spread out for conversion) - i need to stay in lat /lon (wgs84) and probably will not be able to use a kd-tree because of the little ram available on the arduino (no matter wich one i guess).
but anyway - i wanted to ask here if anyone has an idea for a way to get the distance to the closest point when there are thousands of points to compare against.
I think the problem here will be the non-functional requirements, which @pcace has not told us about yet.
I suspect the KD-tree reduces the time taken to find the closest point from N to log2(N) where N is the number of points.
Also transforming the points from lat/long into x/y will make calculating the distances faster (Pythagoras instead of spherical geometry calculations).
Yes, any Arduino can do this. But can any model of Arduino do it fast enough for @pcace ?
Hi there, thanks a lot for your replies! i did forgot to add that i need this calculation to be as fast as possible. the location to wich i am trying the closest point is changing constantly. if possible i would aim for a sub second calculation to find the closest and the distance to the current point. @PaulRB what do you mean by non-functional requirements?
kd-trees will reduce time taken - but i think greatly increase the ram usage. and using x/y coordinates will probably not be possible entirely because i would need to compare different coordinate systems (like epsg25833 against epsg25823...) with each other wich would also introduce a lot of calculating (i guess).
What board are you thinking of using (RAM, clock speed, etc.) and will the text file coordinates be pre-loaded, or being written and read from multiple times?
the reason i ask here is, that on a modern pc using typescript and around a million (not ordered, and around 10x more then what i need here) coordinates takes around 20s when they are not in a kd tree. (just going through them and calculate the distance between two coordinates using turfjs.org). so i guess without any good tricks it will be way too slow on the arduino or am i wrong?
Honestly - no idea about the board. the text file was just an idea - because i dont know how else i would save 100 thousands of coordinates. once they're written they will not change. its only the one point i am testing it against will change. constantly.
yeah.. i was just calculating around a little bit and realized that i would need around 10 minutes to go through a textfile via spi with 300000 6-digit lat/lon coordinates.
puh.. so i guess this is not the right way to do it...
i might be able to cluster the coordinates beforehand - so that i know in adcvance in what cluster i have to look. or maybe make some kind of tiles or bounding boxes. but maybe i am just not on the right plattform?
Yeah. Maybe when you load those values to the card, EEPROM, etc., you can set up some kind of matrix calculator that's automated. You'd have cases, or for loop, that uses 1 - 181 for lat (90 through -90 and 0), and 1 - 361 for long and it'd preface the preceding byte as the case/index number. I'd also look at calculating the distance of each stored point to its nearest neighbor.
The processor would dig down through the cases until a match isn't found or the distance to the nearest point is small enough you know it's closest to that point. Just calculate the most significant digit that isn't a match. That would give you the closest lat and long but then you'd... Well this is where my brain is at for the moment.
Functional requirements of a system are all about what it should do. Non-functional requirements are about how it should do it. How reliably, how securely, how quickly. It was the "how quickly" part of your project I was thinking of that could be difficult to achieve on any kind of microcontroller. Microcontrollers are not really designed for this kind of thing. They are designed to control things, to react quickly following simple rules. Not perform complex calculations on large amounts of data.
This is a random thought. Could you bound your fixed coordinates in a few fixed points. Precalculate the distance of each fixed point from the bounding points. Calculate the distance of your variable point to the bounding points and then use that to limit which fixed points you need to try to accurately calculate.
That would work pretty well, close to the equator. But as you move closer to the poles, a degree of longitude is an increasingly shorter distance compared to a degree in latitude (which remains constant). That would lead to incorrect identification of the nearest point being more and more likely.
(I'm assuming a perfectly spherical Earth. If you believe the Earth to be flat, please forgive my sacrilegious theory )
Imagine you and I shaking hands after successfully reaching the south pole. We could be standing 180 degrees of longitude apart.
In northern Scotland, for example, around 57 degrees north latitude, a degree in longitude is around 60KM, but a degree in latitude is, as it is everywhere, around 110KM.
about the board. the text file was just an idea - because i dont know how else i would save 100 thousands of coordinates. once they're written they will not change. its only the one point i am testing it against will change. constantly.