Could PIC handle this?

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

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

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

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!

"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


..

dapage@gmail.com wrote:
> ~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