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

[Andy Robinson]

bvh wrote:
>Sent: 30 November 2006 5:58 PM
>To: talk at openstreetmap.org
>Subject: [OSM-talk] Points Fitting (was Re: Delete gpx points in JOSM)
>
>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.
>

I seem to recall many moons ago that we had a discussion about Bezier curves
and whether to implement them in OSM but moved away when someone pointed out
that Navtech I think has a patent on their use in something or other that
might have conflicted.

Cheers

Andy

>cu bart
>
>
>_______________________________________________
>talk mailing list
>talk at openstreetmap.org
>http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk