| Author |
Message |
David
Guest
|
 Posted:
Tue Dec 14, 2004 2:44 am Post subject:
Could PIC handle this? |
|
|
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... |
|
| Back to top |
|
 |
Noel Henson
Guest
|
| Posted:
Tue Dec 14, 2004 3:46 am Post subject:
Re: Could PIC handle this? |
|
|
David wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Andrew DeWeerd
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
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...
| Quote: | 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 |
|
|
| Back to top |
|
|
hamilton
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
David wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Noel Henson
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
johannes m.r. wrote:
| Quote: | 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 |
|
| Back to top |
|
|
johannes m.r.
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
Robert Scott wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Robert Scott
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
On Tue, 14 Dec 2004 01:28:14 +0100, "johannes m.r." <psychosos@gmx.at>
wrote:
| Quote: | ...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.) |
|
| Back to top |
|
|
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
yes, thats for an accurate distance calculation. pythagoras can be used
to get a rough idea. |
|
| Back to top |
|
|
johannes m.r.
Guest
|
| Posted:
Tue Dec 14, 2004 4:40 am Post subject:
Re: Could PIC handle this? |
|
|
Noel Henson wrote:
| Quote: | 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. |
|
| Back to top |
|
|
John Harlow
Guest
|
| Posted:
Tue Dec 14, 2004 10:01 am Post subject:
Re: Could PIC handle this? |
|
|
David wrote:
| Quote: | Could a PIC handle interfacing via rs232 with a GPS unit, and
comparing the location against a list of ~5000 stored positions, and
|
It 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. |
|
| Back to top |
|
|
Nicholas O. Lindan
Guest
|
| Posted:
Tue Dec 14, 2004 11:53 am Post subject:
Re: Could PIC handle this? |
|
|
| Quote: | 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)?
|
What's this thing supposed to do: ring a bell if you are close to a
Krispy Kreme Doughnut Shoppe?
I imagine 16 bit precision for locations would be good enough?
25,000 miles / 65,000 ~= 0.4 mile / 0.6 Km at the equator.
Memory would be 4bytes x 5000 = 20Kbytes.
You would have to rig a serial EEROM to the PIC. PICs don't have, and
can't natively access, gobs of memory (for a PIC 20K of anything is a
very large gob).
As to the math: If the 'close enough (1-2km)' means 'somewhere in a
square centered on' then the thing devolves into a look-up table.
I suppose doing 'somewhere in an octagon' wouldn't be much of a
stretch. To do true distance you would need to do square roots;
great circle calcs shouldn't be needed, just treat local space as a flat
grid.
The question is: why use a PIC for this? I can't imagine a worse
choice of microprocessor for this job.
An 8051 class processor is a dollar or so more than a PIC. You may even
be able to cram the location table into the device (I am assuming the
locations are fixed - if not then its back to Esquare). Fast, accurate
IEEE floating point packages are available for 8051's. It's even got
a UART.
IMHO you could spend a month or more getting this to work on a PIC
Vs maybe a week on an 8051? And then if you have to go back and maintain
convoluted PIC code --- ooooh boy.
I would look at the trade off between development cost, program risk
(after two months of 'research': surprise, surprise, it _can't_ be
done in a PIC), life-cycle costs and increased time-to-market against
a higher product cost in using a "civilized man's" uP.
If this is a one-of hobby project get a nice micro with a good
HLL compiler and a JTAG debugger.
The charm of using a PIC is the perverse satisfaction of getting
something useful out of what is arguably the world's worst
processor.
I do design products using PICs ... And curse every time I do.
--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer: Electronics; Informatics; Photonics.
Remove spaces etc. to reply: n o lindan at net com dot com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/ |
|
| Back to top |
|
|
Tauno Voipio
Guest
|
| Posted:
Tue Dec 14, 2004 12:41 pm Post subject:
Re: Could PIC handle this? |
|
|
Robert Scott wrote:
| Quote: | 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.
|
The great circle calculations will pretty surely produce a much
more inaccurate solution as the simple Pythagoras shown above.
The reason is that the great circle distance is calculated so
that the cosine of the distance as seen from the center of the
Earth is obtained. For distances less than 1/1000 of the Earth's
radius, the cosine differs less than 1/1000000 from 1.0. The
round-off errors will be huge, even with double precision
IEEE floats.
--
Tauno Voipio
tauno voipio (at) iki fi |
|
| Back to top |
|
|
Al Borowski
Guest
|
| Posted:
Tue Dec 14, 2004 12:51 pm Post subject:
Re: Could PIC handle this? |
|
|
hamilton wrote:
| Quote: | 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.
|
No way...
Al |
|
| Back to top |
|
|
Paul Keinanen
Guest
|
| Posted:
Tue Dec 14, 2004 2:49 pm Post subject:
Re: Could PIC handle this? |
|
|
On Tue, 14 Dec 2004 00:50:42 GMT, no-one@dont-mail-me.com (Robert
Scott) wrote:
| Quote: | 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).
|
or rather
abs(y-y0) + abs(x-x0) * cosine(y0)
The latitude distance is practically constant (about 110 km/degree) at
all latitudes, but the longitude distance measured in kilometers (or
equatorial longitudes) is reduced, when going towards the poles.
Since the position report is usually received in some degree.fraction
or degree/minute/sec format, it might be a good idea to store the
points grouped by latitude and with some index structure, retrieve
only those points within +/-degree of the integer part of the current
latitude. This will reduce the flash access. The latitude calculation
can now be done at 14-16 bits with one second resolution and any
points too far North and South can be discarded.
If you use an index for each degree of latitude, there is no need to
store the degree part for latitude for the actual data points. You
could also store cosine(y) for each full degree in the index
structure, so you only need to store those cosine(y) values actually
needed and no approximation would be required.
For latitudes above 85 degrees, some approximation might still be
useful, if the device is supposed to work in polar regions.
Paul |
|
| Back to top |
|
|
Goran Larsson
Guest
|
| Posted:
Tue Dec 14, 2004 3:48 pm Post subject:
Re: Could PIC handle this? |
|
|
In article <U5wvd.3165$2J2.1870@newsread2.news.atl.earthlink.net>,
Nicholas O. Lindan <see@sig.com> wrote:
| Quote: | What's this thing supposed to do: ring a bell if you are close to a
Krispy Kreme Doughnut Shoppe?
|
More likely it is intended to alert a driver when approaching an
automatic speed camera.
--
Göran Larsson http://www.mitt-eget.com/ |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in