> ~5000 over the entire UK. distribution varies a little, but not hugely.
> indexing it by longitude is probably best.
You might instead consider indexing by latitude. I did something like
this a very long time ago. My application was to look for radio towers
(in a database) within cicles of a certain radius given an arbitrary lat
and long. I had everything sorted by latitude, since the distance
between lat lines can be approximated as constant everywhere on the
planet (about 111km). To do a quick search of everything within 2km,
you can quickly eliminate everything that differs in latitude by more
than 0.018 degrees. Since you're entirely within the range of about 50
to 60 degrees of latitude, you can also do a similar quick compares on
longitude (around 75km per degree, but verify that number!). In my
application, I didn't actually need the distance -- just whether a tower
was within the circle, so I was able to absolutely exclude everything
outside of the enclosing square. I then had it do similar comparisons
on an inscribed square. Then the only actual calculations the program
had to do was only on points which were inside the outer square but
inside the inner one -- often there were none. This would be easier
with a simple diagram, but you can probably figure it out.
Ed
Reply by Ulf Samuelsson●December 15, 20042004-12-15
"David" <dapage@gmail.com> skrev i meddelandet
news:e9b6577d.0412131344.2e612b8a@posting.google.com...
> 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 that if the volume is OK, you can run the calulations inside a GPS
chip.
Vendors are not likely to bother with you for 1s or 2s.
If you first get the position, and then do the calculation you should have
enough MIPS.
If you need an external micro, then the AT91SAM7S32 might be a good choice.
Has 32 kB of Flash providing 12 kB for the application and 20 for the data.
Bandwidth for data would be 120 MByte/second
AT91SAM7S128 (available in January) would have enough SRAM to store the
complete
table so your bandwidth could be up to 200 MByte per second.
--
Best Regards,
Ulf Samuelsson ulf@a-t-m-e-l.com
This is a personal view which may or may not be
share by my Employer Atmel Nordic AB
..
Reply by CBFalconer●December 15, 20042004-12-15
Joop wrote:
> Noel Henson <noel@noels-lab.com> wrote:
>
> <snip>
>>
>> BTW, the sum of the differences technique is really pretty
>> efficient. The worst case error occurs when the points are at 45
>> degrees from each other. Even then, it's still really close.
>
> I actually started on something like this for a 8051, but stopped
> it after buying a 2nd hand PalmV.
>
> All code was using integer32 and the distance was approximated
> using somthing derived from the code below. Scaling on longitude
> before the function call was done based on lattidude value
> (usable for <85 degree north/south).
>
> The main loop would run over the points list in eeprom/flash and
> find and the nearest point. The current nearest was monitored
> each second per GPS update.
> Simulation showed capability of looping over 256 stored EEPROM
> coordinates in about 120ms on 11.0592 Mhz AT89S8252.
>
> The OP's 5000 points would then require 2-3 seconds. Still seems
> quite usable.
>
> /* --------------------------------------------------------
> A Fast Approximation to the Hypotenuse
> by Alan Paeth
> from "Graphics Gems", Academic Press, 1990
> * --------------------------------------------------------- */
>
> int idist(x1, y1, x2, y2)
> int x1, y1, x2, y2;
> {
> /*
> * gives approximate distance from (x1,y1) to (x2,y2)
> * with only overestimations, and then never by more
> * than (9/8) + one bit uncertainty.
> */
> if ((x2 -= x1) < 0) x2 = -x2;
> if ((y2 -= y1) < 0) y2 = -y2;
> return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
> }
Would make more sense if properly commented. This actually takes
the sum of abs(x1-x2) and abs(y1-y2), and deducts 1/2 of the
smaller of those two. The 45 degree is the point at which the
smaller selection switches over. When either the x or the y points
are identical the formula is trivially exact. I think it falls out
directly from a power series approximation to the root.
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Reply by Joop●December 15, 20042004-12-15
Noel Henson <noel@noels-lab.com> wrote:
>>
>> /* --------------------------------------------------------
>> A Fast Approximation to the Hypotenuse
>> by Alan Paeth
>> from "Graphics Gems", Academic Press, 1990
>> * --------------------------------------------------------- */
>>
>> int idist(x1, y1, x2, y2)
>> int x1, y1, x2, y2;
>> {
>> /*
>> * gives approximate distance from (x1,y1) to (x2,y2)
>> * with only overestimations, and then never by more
>> * than (9/8) + one bit uncertainty.
>> */
>> if ((x2 -= x1) < 0) x2 = -x2;
>> if ((y2 -= y1) < 0) y2 = -y2;
>> return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
>> }
>
>Now that's a simple solution.
>
>Noel
Nice, isn't it?
I noticed the SDCC compiler was helped quite a bit by calling the
following function passing the X and Y distances. Functionally the
same but better fitted to the 8051.
// Less generated code and uses more registers
unsigned long ldist(long distX, long distY)
{
if (distX < 0) distX = -distX;
if (distY < 0) distY = -distY;
if (distX > distY)
return (unsigned long)(distX + (distY>>1));
else
return (unsigned long)(distY + (distX>>1));
}
Reply by Noel Henson●December 15, 20042004-12-15
Joop wrote:
> Noel Henson <noel@noels-lab.com> wrote:
>
> <snip>
>>
>>BTW, the sum of the differences technique is really pretty efficient. The
>>worst case error occurs when the points are at 45 degrees from each other.
>>Even then, it's still really close.
>>
>>Noel
>>
> I actually started on something like this for a 8051, but stopped it
> after buying a 2nd hand PalmV.
>
> All code was using integer32 and the distance was approximated using
> somthing derived from the code below. Scaling on longitude before the
> function call was done based on lattidude value (usable for <85 degree
> north/south).
>
> The main loop would run over the points list in eeprom/flash and find
> and the nearest point. The current nearest was monitored each second
> per GPS update.
> Simulation showed capability of looping over 256 stored EEPROM
> coordinates in about 120ms on 11.0592 Mhz AT89S8252.
>
> The OP's 5000 points would then require 2-3 seconds. Still seems quite
> usable.
>
> Joop
>
> /* --------------------------------------------------------
> A Fast Approximation to the Hypotenuse
> by Alan Paeth
> from "Graphics Gems", Academic Press, 1990
> * --------------------------------------------------------- */
>
> int idist(x1, y1, x2, y2)
> int x1, y1, x2, y2;
> {
> /*
> * gives approximate distance from (x1,y1) to (x2,y2)
> * with only overestimations, and then never by more
> * than (9/8) + one bit uncertainty.
> */
> if ((x2 -= x1) < 0) x2 = -x2;
> if ((y2 -= y1) < 0) y2 = -y2;
> return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
> }
Now that's a simple solution.
Noel
Reply by Joop●December 15, 20042004-12-15
Noel Henson <noel@noels-lab.com> wrote:
<snip>
>
>BTW, the sum of the differences technique is really pretty efficient. The
>worst case error occurs when the points are at 45 degrees from each other.
>Even then, it's still really close.
>
>Noel
>
I actually started on something like this for a 8051, but stopped it
after buying a 2nd hand PalmV.
All code was using integer32 and the distance was approximated using
somthing derived from the code below. Scaling on longitude before the
function call was done based on lattidude value (usable for <85 degree
north/south).
The main loop would run over the points list in eeprom/flash and find
and the nearest point. The current nearest was monitored each second
per GPS update.
Simulation showed capability of looping over 256 stored EEPROM
coordinates in about 120ms on 11.0592 Mhz AT89S8252.
The OP's 5000 points would then require 2-3 seconds. Still seems quite
usable.
Joop
/* --------------------------------------------------------
A Fast Approximation to the Hypotenuse
by Alan Paeth
from "Graphics Gems", Academic Press, 1990
* --------------------------------------------------------- */
int idist(x1, y1, x2, y2)
int x1, y1, x2, y2;
{
/*
* gives approximate distance from (x1,y1) to (x2,y2)
* with only overestimations, and then never by more
* than (9/8) + one bit uncertainty.
*/
if ((x2 -= x1) < 0) x2 = -x2;
if ((y2 -= y1) < 0) y2 = -y2;
return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
}
Reply by Jonathan Kirwan●December 15, 20042004-12-15
On Wed, 15 Dec 2004 02:14:59 -0500, Spehro Pefhany
<speffSNIP@interlogDOTyou.knowwhat> wrote:
>I've seen ads (from Western Design Center?) that show that a 65C02
>core would run at several hundred MHz if manufactured in a modern
>process. Maybe the market price per chip times the demand for such a
>fast, but lean, processor won't support the up-front cost of such a
>process.
The ever popular flash is generally slow and I/O pins generally don't need to be
near that fast, so the external interface is probably what makes this kind of
fast embedded 8-bit CPU in the center not so interesting. And if you add in
cache and inbound and outbound fifos, etc., it's not so interesting anymore to
have a 65C02 in the middle of all that. And there's the core voltage versus
what people would like for their applications, perhaps.
Jon
Reply by Spehro Pefhany●December 15, 20042004-12-15
On Wed, 15 Dec 2004 08:57:17 +0200, the renowned Paul Keinanen
<keinanen@sci.fi> wrote:
>On Tue, 14 Dec 2004 21:58:18 -0500, Spehro Pefhany
><speffSNIP@interlogDOTyou.knowwhat> wrote:
>
>>>[raspberry sound] Today's PICs have hardware multiply and run at up to
>>>40MHz. For 8 bitters, they're rather good.
>>
>>Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
>>multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
>>times the work. Although technically a 16-bit micro, it competes
>>directly. Also, 40MHz is the oscillator frequency-- the minimum
>>instruction cycle is 100ns.
>
>It is interesting to compare these clock frequencies and minimum cycle
>times to the original MC6800 some 30 years ago running at 1 MHz and 1
>us. Despite the huge improvement in silicon processing, the
>performance of current 8 bitters is only modest.
>
>While on wider processors, much of the performance increase is due to
>using more and more transistors, the maximum clock frequency has also
>grown several decades.
>
>Thus, I would have expected that with current 130 nm line widths, the
>performance would have been at least two decades better than with the
>original 6800/8080/8085/Z80 processors, even with a similar number of
>gates.
>
>Are manufacturers afraid that fast 8 bitters would reduce the market
>for 16/32 bit processors ?
>
>Paul
I've seen ads (from Western Design Center?) that show that a 65C02
core would run at several hundred MHz if manufactured in a modern
process. Maybe the market price per chip times the demand for such a
fast, but lean, processor won't support the up-front cost of such a
process.
Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com
Reply by Paul Keinanen●December 15, 20042004-12-15
On Tue, 14 Dec 2004 21:58:18 -0500, Spehro Pefhany
<speffSNIP@interlogDOTyou.knowwhat> wrote:
>>[raspberry sound] Today's PICs have hardware multiply and run at up to
>>40MHz. For 8 bitters, they're rather good.
>
>Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
>multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
>times the work. Although technically a 16-bit micro, it competes
>directly. Also, 40MHz is the oscillator frequency-- the minimum
>instruction cycle is 100ns.
It is interesting to compare these clock frequencies and minimum cycle
times to the original MC6800 some 30 years ago running at 1 MHz and 1
us. Despite the huge improvement in silicon processing, the
performance of current 8 bitters is only modest.
While on wider processors, much of the performance increase is due to
using more and more transistors, the maximum clock frequency has also
grown several decades.
Thus, I would have expected that with current 130 nm line widths, the
performance would have been at least two decades better than with the
original 6800/8080/8085/Z80 processors, even with a similar number of
gates.
Are manufacturers afraid that fast 8 bitters would reduce the market
for 16/32 bit processors ?
Paul
Reply by Spehro Pefhany●December 14, 20042004-12-14
On Tue, 14 Dec 2004 23:37:16 +0000, the renowned Mike Page
<brian@brian.com> wrote:
>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.
>>
>> hamilton
>
>[raspberry sound] Today's PICs have hardware multiply and run at up to
>40MHz. For 8 bitters, they're rather good.
Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
times the work. Although technically a 16-bit micro, it competes
directly. Also, 40MHz is the oscillator frequency-- the minimum
instruction cycle is 100ns.
Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com