[OSM-dev] Algorithm for extracting nodes/edges from gps-tracklogs

[Stefan de Konink]

Hi :)

Jan-Benedict Glaw wrote:
> Hi!
> 
> Please keep posting to the list, so everybody else could follow the
> discussion.
> 
> On Sat, 2007-03-03 14:35:05 +0100, Stefan de Konink <skinkie at xs4all.nl> wrote:
>> Jan-Benedict Glaw wrote:
>>> On Thu, 2007-03-01 22:51:30 +0000, SteveC <steve at asklater.com> wrote:
>>>> Stefan de Konink wrote:
>>>>> SteveC wrote:
>>>>>>> one task of my diploma's thesis is to implement an algorithm, which
>>>>>>> can extract a topological structure - nodes and edges - out of
>>>>>>> gps-tracklogs. Do you know any literature concerning this problem?
>>>>>> OpenStreetMap, in general, has regarded that as a Hard Problem (TM). 
>>>>>> There was a open project to do it but I don't recall the name of it. 
>>>>>> Bouncing this to the OSM list who may be able to help.
>>>>>> Michael Stein wrote:
>>>>> http://mapgeneration.berlios.de/ ?
>>>>>
>>>>> http://uva.hobby-site.com/~skinkie/mgg.png
>>>>>
>>>>> It is a bit hard to compile.
>>>> yes mapgeneration was it! :-)
>>> The GPS parser is quite dumb, loads of bugs, wonky license, the UI
>>> will crash faster than you can see (at least on SMP, due to broken
>>> locking.)
>> Yes, the powerpc compile was much more stable than my AMD64 X2 is now. 
>> (I should read howto run the program only only on one processor?)
> 
> Either your system us UP, or it is SMP. There's currently no easy way
> to run a given multi-threaded application on only one core.
> 
>> I noticed the Academic Free License, why is that wonky?
> 
> Not GPL compatible. For me, that's pain in the ass since I cannot put
> parts of mapgeneration into any of my other code (which is purely
> GPL), nor can I sanely put own GPL code into mapgeneration (since I
> would need to dual-license, which I dislike, especially in this
> direction.)
> 
>>> However, it's a question about what you want. It *could* get you
>>> started quite fast with roads and their driving directions, but it
>>> won't help you a lot classifying those, applying names etc. Since the
>>> idea is nice, I thought about starting from scratch, but due to time
>>> constrains...
>> It is nice in two ways: one it stores directed paths/graphs so you can 
>> implement a pathfinder. It does draw it for you.
>> Now I contacted the authors, but noone responds. I think this 
>> application in great if it implements the functionality of path locking, 
>> quality traces and bezier paths.
> 
> I had contact with those two developers. Mapgeneration was written for
> a thesis, not to be put into the Free Software Community in the first
> place.  That's why the code quality is so "poor".  It only had to run
> one time in a highly controlled environment.
> 
> When I pumped in a dozend traces in parallel, it immediately died.
> Even pumping them in serialized may make it die, since processing of
> one trace may extend into importing the next one...

On my iBook I had a version of a year ago that contains most traces of 
Norway a user sent my and all my traces of The Netherlands. It is 
surprisingly stable.

> Though that's all mostly fixable. Just some locking (and maybe
> decoupling). But the license distracts me from doing that.

It isn't possible to get the authors to relicense it? Otherwise one 
could reimplement their thesis algorithm for combining traces.


>> Quality traces: if the nmea input has a better quality than the 
>> previous, ignore the previous and update the path to the new one.
> 
> Averaging a number of lower-quality traces /may/ give a better result
> than relying on a single "higher-quality" trace that's totally broken
> due to an undetected receiver problem...  Choosing a source of
> information is quite a hard task :)

True, but if I drive a road twice and my second trace has 1.2 and my 
first one has 5.0 then I thing the algorithm should think 'mmmmm, lets 
use the second one'. But a GUI showing the changes would be nice. Or 
only show the route and not *all* the other information.

>> Path locking: if someone did a manual trace it should have something als 
>> a ultimate quality, which can be override in case of better trace methods.
>>
>> Bezier paths: curved roads not stored as lines, but as curved paths. 
>> Here segment reducing.
> 
> I don't see number of segments as an ultimate problem, but bezier
> curves may indeed lead to less overall segments and more eye-candy
> without extra prices...
> 
>> ps. If someone wants to start with this... I want to help.
> 
> Post to the list again, please :)  You may even send this mail to the
> list.

Sorry, I handle Pine better than Mozilla Thunderbird. It was targeted 
for the list too.


Stefan