Could a PIC handle interfacing via rs232 with a GPS unit, and comparing the location against a list of ~5000 stored positions, and alerting (LED/LCD) if any points are considered close enough (~1-2km, using haversine formula, perhaps)? I guess the points would have to be stored on a CF/MMC card. They would be updated/changed time to time...
Could PIC handle this?
Started by ●December 13, 2004
Reply by ●December 13, 20042004-12-13
David wrote:> Could a PIC handle interfacing via rs232 with a GPS unit, and > comparing the location against a list of ~5000 stored positions, and > alerting (LED/LCD) if any points are considered close enough (~1-2km, > using haversine formula, perhaps)? > > I guess the points would have to be stored on a CF/MMC card. They > would be updated/changed time to time...I think even a smallish PIC could handle this. If you needed to go really inexpensive, you could use a part without a USART and emulate it yourself.; For memory you could go with an 8-pin serial FLASH part and skip the overhead of CF/MMC; unless of course the storage had to be removable. Noel
Reply by ●December 13, 20042004-12-13
Noel Henson wrote:> David wrote: >> Could a PIC handle interfacing via rs232 with a GPS unit, and >> comparing the location against a list of ~5000 stored positions, and >> alerting (LED/LCD) if any points are considered close enough (~1-2km, >> using haversine formula, perhaps)? >> >> I guess the points would have to be stored on a CF/MMC card. They >> would be updated/changed time to time... > > I think even a smallish PIC could handle this. If you needed to go really > inexpensive, you could use a part without a USART and emulate it yourself.; > For memory you could go with an 8-pin serial FLASH part and skip the > overhead of CF/MMC; unless of course the storage had to be removable.I'd really be interested in that. Doesn't that mean comparing the distance from a specified point on earth to one of 5000 different positions? According to a quick google search, which reveals this article: http://en.wikipedia.org/wiki/Great_circle_distance there're some calculations which are rather complex for a 8 bit processor I guess :-? Regards, j.
Reply by ●December 13, 20042004-12-13
Reply by ●December 13, 20042004-12-13
On Tue, 14 Dec 2004 01:28:14 +0100, "johannes m.r." <psychosos@gmx.at> wrote:>...I'd really be interested in that. Doesn't that mean comparing the distance >from a specified point on earth to one of 5000 different positions? >According to a quick google search, which reveals this article: >http://en.wikipedia.org/wiki/Great_circle_distance there're some >calculations which are rather complex for a 8 bit processor I guess :-?If all you need to do is decide if any of the 5000 points are close enough to where you are now, you can reduce the number of points drastically by using a much simpler metric: (abs(x-x0) + abs(y-y0)) * cosine(y0) Use a rough table-driven approximation for cosine(y0). This is very easy to calculate, and gives the right angle distance instead of the great circle distance. Use a threshold that is 1.414 times larger than you really want. Chances are there will only be one point that qualifies. Once you have determined which point that is, then you can use a slower calculation to get the great circle distance to see if that one point is really close enough to alarm about. If the threshold is reasonably small, the great circle distance is adequately approximated by the Eucidean distance times the cosine of the lattitude. -Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)
Reply by ●December 13, 20042004-12-13
Robert Scott wrote:> On Tue, 14 Dec 2004 01:28:14 +0100, "johannes m.r." <psychosos@gmx.at> > wrote: > >>...I'd really be interested in that. Doesn't that mean comparing the distance >>from a specified point on earth to one of 5000 different positions? >>According to a quick google search, which reveals this article: >>http://en.wikipedia.org/wiki/Great_circle_distance there're some >>calculations which are rather complex for a 8 bit processor I guess :-? > > If all you need to do is decide if any of the 5000 points are close > enough to where you are now, you can reduce the number of points > drastically by using a much simpler metric: > > (abs(x-x0) + abs(y-y0)) * cosine(y0) > [..]Thank you for your answer, Robert. That's what I was curious about. I'll read through it some times and try to really understand it. Thanks! Regards, johannes
Reply by ●December 13, 20042004-12-13
johannes m.r. wrote:> Noel Henson wrote: >> David wrote: >>> Could a PIC handle interfacing via rs232 with a GPS unit, and >>> comparing the location against a list of ~5000 stored positions, and >>> alerting (LED/LCD) if any points are considered close enough (~1-2km, >>> using haversine formula, perhaps)? >>> >>> I guess the points would have to be stored on a CF/MMC card. They >>> would be updated/changed time to time... >> >> I think even a smallish PIC could handle this. If you needed to go really >> inexpensive, you could use a part without a USART and emulate it >> yourself.; For memory you could go with an 8-pin serial FLASH part and >> skip the overhead of CF/MMC; unless of course the storage had to be >> removable. > > I'd really be interested in that. Doesn't that mean comparing the distance > from a specified point on earth to one of 5000 different positions? > According to a quick google search, which reveals this article: > http://en.wikipedia.org/wiki/Great_circle_distance there're some > calculations which are rather complex for a 8 bit processor I guess :-? > > Regards, > j.There are some calculations but they're not that bad. You simply need the magnitude of the distance, not the actual distance. You simply square the differences between the longitude and latitude of each pair of points you are comparing. There is no need for a square-root. I do this on another project; only about 2000-3000 items in my lists. You can also do some optimizations by simply comparing the sum of differences in longitude and latitude. It's not perfect but it will get you in the ball park quickly. Then you can use magnitude to select the best from the presorted set. You may also be able to store the data in FLASH in an optimized way; perhaps twice, one ordered by longitude, spiraling by latitude and once the opposite way. What kind of response time is necessary? How close are the points? Miles? Feet? Noel
Reply by ●December 13, 20042004-12-13
David wrote:> Could a PIC handle interfacing via rs232 with a GPS unit, and > comparing the location against a list of ~5000 stored positions, and > alerting (LED/LCD) if any points are considered close enough (~1-2km, > using haversine formula, perhaps)? > > I guess the points would have to be stored on a CF/MMC card. They > would be updated/changed time to time...I would be hard pressed to believe that a PIC can do this. The largest/fastest PIC can do floating point math in seconds. 5000 * 2 floating point calculations (lat/long) would require 10s on thousands of seconds. ( 10,000 seconds / 3600/hr = 2.77 hours ) Let alone storage and retrieval of 5000 pairs (lat/long) numbers. Searching an external flash memory device would take a long time as well. There are many other low cost solutions that can better handle this problem. If your are cheap and this in not on a schedule, sure have fun. But, when do you want to see this done ? Not within a single semester !! hamilton
Reply by ●December 14, 20042004-12-14
Seconds to do a floating point calculation? Wrong. The stored positions, and all required math, could be scaled to make the math much simpler. Based on the only requirements stated by the original poster, the goal seems very achievable. However, I would 1) consider a simpler storage scheme for the stored positions (serial flash or even serial EEPROM sounds good) and 2) maybe consider a processor with a hardware multiplier, like the excellent TI MSP430 16-bit parts. "hamilton" <hamilton@deminsional.com> wrote in message news:41be53ef$1_1@omega.dimensional.com...> David wrote: > > Could a PIC handle interfacing via rs232 with a GPS unit, and > > comparing the location against a list of ~5000 stored positions, and > > alerting (LED/LCD) if any points are considered close enough (~1-2km, > > using haversine formula, perhaps)? > > > > I guess the points would have to be stored on a CF/MMC card. They > > would be updated/changed time to time... > > I would be hard pressed to believe that a PIC can do this. > > The largest/fastest PIC can do floating point math in seconds. > > 5000 * 2 floating point calculations (lat/long) would require 10s on > thousands of seconds. ( 10,000 seconds / 3600/hr = 2.77 hours ) > > Let alone storage and retrieval of 5000 pairs (lat/long) numbers. > > Searching an external flash memory device would take a long time as well. > > There are many other low cost solutions that can better handle this > problem. If your are cheap and this in not on a schedule, sure have fun. > > But, when do you want to see this done ? Not within a single semester !! > > hamilton
Reply by ●December 14, 20042004-12-14
David wrote:> Could a PIC handle interfacing via rs232 with a GPS unit, and > comparing the location against a list of ~5000 stored positions, andIt will be reduced to a few simple integer comparisons assuming a rectangular "window" is OK and the corners of the windows were stored in the lookup table. Pre-index the table for added efficiency.
