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

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/

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

hamilton 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 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

On Tue, 14 Dec 2004 00:50:42 GMT, no-one@dont-mail-me.com (Robert
Scott) wrote:


>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

In article <U5wvd.3165$2J2.1870@newsread2.news.atl.earthlink.net>,
Nicholas O. Lindan <see@sig.com> wrote:

> 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&#4294967295;ran Larsson     http://www.mitt-eget.com/

"Goran Larsson" <hoh@invalid.invalid> wrote

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

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

Nicholas O. Lindan <see@sig.com> wrote:
> "Goran Larsson" <hoh@invalid.invalid> wrote

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

> They publish the locations?

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

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

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 (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

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.

"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

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

"Nicholas O. Lindan" <see@sig.com> wrote in message
news:U5wvd.3165$2J2.1870@newsread2.news.atl.earthlink.net...
>
> The charm of using a PIC is the perverse satisfaction of getting
> something useful out of what is arguably the world's worst
> processor.
>

ROTFLMAO!

But don't underestimate the satisfaction!

Rufus

(I envision that quote on a t-shirt)