I'll be glad to provide lots of crappy data if anybody wants to play with it.

The refclock (nmea, PPS, TBolt, ...) support in ntpd has code to discard
outliers on a clump of timestamps.  I think something like that would be very
helpful when processing position data.

The code is pretty simple in one dimension: sort, compute average, compare
distance to left and right ends, discard one, adjust average...  After the
sort, the processing time is linear in the number of samples to be discarded.

I haven't figured out how to do something like that in 2 dimensions: there is
no left or right end.

The basic idea you want to implement is to start with a large circle centered
on the center of mass and shrink that circle until it hits a point.  That's
the point you want to discard.

Pure brute force would compute the center of mass and then scan all the data
points computing the distance...  That's an N-squared process which might
take too long with a large clump of data.  For offline research like this, it
might be OK.

There is a slightly better approach that I'll call semi-brute force.  The
idea would be to make two lists: one for NS and one for EW, sort them, then
use the longest end as a trial point.  Then you scan in from the 4 ends.  The
semi- part is that you can stop when you get to the trial / sqrt(2).  At
first glance, discarding isn't cheap since you have to scan the other
list/array.  Actually, you don't have to scan the other list.  Just mark that
slot as dead.  In either case, you can fixup the center location rather than
recomputing it.  If you notice a dead slot on the end of a list you can
delete it.

[I'm pretty sure that will get the right answer.  I'll try again if that
description isn't clear.]

--
These are my opinions, not necessarily my employer's.  I hate spam.

On Sat, Nov 26, 2011 at 2:35 PM, Hal Murray hmurray@megapathdsl.net wrote:

For off line work your "shrink the bounding box (or bounding ellipse)"
method would work fine.  I think even with a few million points it is
nearly trivial on a modern PC.

But you can do something like this continuously in real time and keep
the processing time constant.
Keep a running mean of each point (actually two means as you need one
for Y and one for X direction.  three for Z if you include altitude.
Along with the running means keep a running "sigma" (To do this you
need keep the count "N", and the sum and the sum of the squares.)  Now
as you get each point test if it falls outside a three sigma limit.
Discard it if it does.  You can play with the size and shape of the
bounding box.  If the robot moves then it can update the running
means by dead reckoning and errors in the dead reckoned estimate will
get corrected eventually by GPS

GPS is never going to be exact.  Or I should say you don't know the
exact lat. long. for every place you want to go.  So to find something
like a bear bottle in your refrigerator you need vision

Chris Albertson
Redondo Beach, California

Or an alcohol sensor !

Bill....WB6BNQ

Chris Albertson wrote:

Kalman filtering navigation?

On Sun, Nov 27, 2011 at 4:53 AM, WB6BNQ wb6bnq@cox.net wrote: