[OSM-talk] Points Fitting (was Re: Delete gpx points in JOSM)

[bvh]

On Thu, Nov 30, 2006 at 02:36:54PM +0000, Robert (Jamie) Munro wrote:
> > (The way Illustrator manages to convert straight line paths into  
> > simpler beziers, however, is something I'd class as magic but  
> > fortunately not something OSM has to worry about.)
> I wonder if we could borrow some of the algorithms from things like
> AutoTrace? (http://autotrace.sf.net)

It is indeed not magic, but a well researched topic. In my profession
life I've written the code to do it, and have the authorization to
release it (GPL) for Merkaartor should bezier curves ever come about.
I believe there was some code to do this available from the
Graphic Gems. Must be one of the older books but I am too lazy to
research that right now.

> I'd be inclined to write an algorithm where you select a way in JOSM, it
> then finds all the GPS points that look like they are part of the way
> and not part of other segments or ways, and then iteratively tries to
> manipulate points in the way so that the total distance^2 of GPS points
> from the way is reduced. If it doesn't go below a certain threshold,
> then add another point on the way (on the segment with the highest
> error). It if goes very low, take some points away (from between the two
> segments that are the most straight in line). The thresholds depend on
> the number of GPS points (if there are less points, we don't worry about
> trying to get too much accuracy).

In fact the math is trivial. What's going to be hard is deciding what
points look like they are part of a way... Also a lot of the fitting
algo's try to fit (infinite) lines. Finding the relevant segment off
that line (wrt outliers) is going to be a hard problem too.

cu bart