| Author |
Message |
Joop
Guest
|
 Posted:
Thu Dec 16, 2004 2:22 am Post subject:
Re: Could PIC handle this? |
|
|
Noel Henson <noel@noels-lab.com> wrote:
<snip>
| Quote: |
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) );
} |
|
| Back to top |
|
 |
Noel Henson
Guest
|
| Posted:
Thu Dec 16, 2004 3:00 am Post subject:
Re: Could PIC handle this? |
|
|
Joop wrote:
| Quote: | 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 |
|
| Back to top |
|
|
Joop
Guest
|
| Posted:
Thu Dec 16, 2004 3:19 am Post subject:
Re: Could PIC handle this? |
|
|
Noel Henson <noel@noels-lab.com> wrote:
| Quote: |
/* --------------------------------------------------------
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));
} |
|
| Back to top |
|
|
CBFalconer
Guest
|
| Posted:
Thu Dec 16, 2004 4:35 am Post subject:
Re: Could PIC handle this? |
|
|
Joop wrote:
| Quote: | 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! |
|
| Back to top |
|
|
Ed Beroset
Guest
|
| Posted:
Thu Dec 16, 2004 4:41 am Post subject:
Re: Could PIC handle this? |
|
|
dapage@gmail.com wrote:
| Quote: | ~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 |
|
| Back to top |
|
|
Ulf Samuelsson
Guest
|
| Posted:
Thu Dec 16, 2004 4:41 am Post subject:
Re: Could PIC handle this? |
|
|
"David" <dapage@gmail.com> skrev i meddelandet
news:e9b6577d.0412131344.2e612b8a@posting.google.com...
| 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 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
... |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in