Could PIC handle this?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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...

Re: Could PIC handle this?

Quoted text here. Click to load it

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




Re: Could PIC handle this?
Quoted text here. Click to load it

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.

Re: Could PIC handle this?
yes, thats for an accurate distance calculation. pythagoras can be used
to get a rough idea.


Re: Could PIC handle this?

Quoted text here. Click to load it

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.)

Re: Could PIC handle this?
Quoted text here. Click to load it

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

Re: Could PIC handle this?
Quoted text here. Click to load it

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


Re: Could PIC handle this?
On Tue, 14 Dec 2004 00:50:42 GMT, no-one@dont-mail-me.com (Robert


Quoted text here. Click to load it


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


Re: Could PIC handle this?

Quoted text here. Click to load it

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


Re: Could PIC handle this?
Quoted text here. Click to load it

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.
We've slightly trimmed the long signature. Click to see the full one.
Re: Could PIC handle this?

Quoted text here. Click to load it

More likely it is intended to alert a driver when approaching an
automatic speed camera.

--
Göran Larsson     http://www.mitt-eget.com /

Re: Could PIC handle this?

Quoted text here. Click to load it

They publish the locations?

In Germany they do seem to stay in the same position
for an awfully long time.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.
Re: Could PIC handle this?

Quoted text here. Click to load it


Some legislations do, indeed.  Typically not by way of GPS
coordinates, but that's easily fixed by a dedicated service provider.

Quoted text here. Click to load it

That's because these things have to be vandal-proofed to an extent
that does makes them quite hard to move.  Most of the time there's no
camera in them, though.  I.e. they move the camera, but not the box.

--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Could PIC handle this?
Theres thousands of fixed ones - thick metal concreted into ground, not
moveable. Then theres many mobile ones - in vans or handheld (hiding
behind bushes near speed limit change signs, etc), carriageway bridges.

They publish the locations by listing road name, although theres some
public GPS lists.


Re: Could PIC handle this?

Quoted text here. Click to load it

ROTFLMAO!

But don't underestimate the satisfaction!

Rufus

(I envision that quote on a t-shirt)




Re: Could PIC handle this?
Quoted text here. Click to load it

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

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.


Quoted text here. Click to load it



Re: Could PIC handle this?
Quoted text here. Click to load it

No way...

Al


Re: Could PIC handle this?

Quoted text here. Click to load it

What is the distribution of the stored positions?

it's possible that the points can be sorted according to regions, then the
only calculations would be: In which region is the test point?  Are any
points
in this or immediately adjacent  regions close enough?

Rufus



Re: Could PIC handle this?
~5000 over the entire UK. distribution varies a little, but not hugely.
indexing it by longitude is probably best.


Site Timeline