[OSM-talk-nl] Fietsroutenetwerk-punten automatiseren?

[Steven te Brinke]

Coördinaten zijn niet makkelijk de sorteren, omdat ze 2-dimensionaal 
zijn. Hiermee heb ik ook niet zo veel ervaring. maar ik heb eens 
nagedacht wat volgens mij een aardig algoritme is. Ik zal beschrijven 
hoe ik het zou implementeren:

Stel we hebben een aantal punten P die niet in OSM zitten. Dan bepalen 
we de bouding box van deze punten en nemen alle punten Q die in OSM in 
deze bouding box zitten (hierbij kun je je eventueel beperken tot alle 
punten met een highway tag).

L := lijst van punten uit Q gesorteerd op OL
p := element uit P, dus punt waarvan we dichtstbijzijnde punt uit Q 
willen weten

i := punt met |p.OL - L[i].OL| zo klein mogelijk, deze kun je in 
logaritmische tijd vinden
d := afstand(p, L[i])
q := L[i]
j := i + 1;
while ( |p.OL - L[j].OL| < d ) {
    d2 := afstand(p, L[j])
    if ( d2 < d ) {
       d := d2
       q := L[j]
    }
    j += 1
}
j := i - 1;
while ( |p.OL - L[j].OL| < d ) {
    d2 := afstand(p, L[j])
    if ( d2 < d ) {
       d := d2
       q := L[j]
    }
    j -= 1
}

return q


Dit algoritme is natuurlijk nog niet volledig, zo moet je nog nadenken 
over een paar punten:
* |p.OL - L[j].OL| heeft waarschijnlijk een andere eenheid dan d, dat 
moet je even omrekenen
* eventueel kun je in deze while loop i.p.v. tegen d, degen minimum(d, 
MAX-AFSTAND) controleren
* ik heb het hier over een gesorteerde lijst, maar een boom zou ook 
kunnen, als je er maar in order doorheen kunt lopen (een boom laad wel 
veel sneller dan een lijst, maar aangezien je hier één keer deze 
lijst/boom laad en daarna voor alle punten de dichtstbijzijnde kunt 
vinden, is de snelheid van het laden niet heel belangrijk)

Mocht je nog een werkende XPath versie hebben, dan hoor ik graag of de 
snelheid nog een beetje goed was. De ervaring die ik ermee heb, is dat 
het niet heel snel is. Maar dat kan natuurlijk ook (gedeeltelijk) liggen 
aan de implementatie die ik gebruik. Misschien heb jij een snellere parser.

Steven


Rob schreef:
> hoe wil je dit gaan sorteren.. b/r-tree ? geef eens een hint
> ondertussen ga ik xpath eens pesten
>
> Groeten
> Rob
>
> Op 07-02-08 heeft *Steven te Brinke* <s.tebrinke at student.utwente.nl 
> <mailto:s.tebrinke at student.utwente.nl>> het volgende geschreven:
>
>     Hallo,
>
>     XPath is wel heel krachtig, maar niet heel snel. Ik denk dus dat
>     het gebruik van een gesorteerde lijst een beter idee is. Zelf heb
>     ik nog nooit .net gebruikt, dus daar heb ik niet zo veel verstand
>     van. Maar mocht het niet lukken, dan wil ik wel iets in Java
>     schrijven. Daarmee lees ik nu ook al OSM bestanden in.
>
>     Groeten,
>     Steven
>
>
>     Rob schreef:
>>     ik heb die wpned-zuid.gpx (1701 waypoints)  eens tegen de
>>     places.osm (8875) laten draaien, om een indruk te krijgen van
>>     performance
>>     en dit is een stukje output
>>     ...
>>     wpt 52C37 close to Pannenschop @ 587m
>>     wpt 52C39 close to Vreewijk @ 300m
>>     wpt 52C43 close to Leensel @ 714m
>>     wpt 52C44 close to Leensel @ 1885m
>>     wpt 52C45 close to Heitrak @ 2708m
>>     wpt 52C46 close to Ommel @ 50m
>>
>>     er wordt dus voor elk wapoint in de gpx de kortsbijzijnde plaats
>>     node gevonden in de osm file, hiervoor loopt een dubbele foreach
>>     loop, deze berekent de afstand tussen waypoint en node
>>     de search loop begint nu al te kraken (lees 155 seconden)
>>     aangezien we nu al 15miljoen itteraties hebben.
>>
>>     ik ben een andere manier aan het bedenken
>>     bereken van elk waypoint de 5meter boundingbox coordinaten en
>>     laat de node selectie door xml parser (xpath)  doen, dit moet
>>     veel efficienter zijn.
>>
>>
>>     Op 07-02-08 heeft *Rob* <rob at coolbegin.com
>>     <mailto:rob at coolbegin.com>> het volgende geschreven:
>>
>>         dank u, heb nu de netherlands.osm van 600MB
>>         dat wordt flink stampen voor xml parser ;)
>>
>>         Op 07-02-08 heeft *Lambertus* <osm at na1400.info
>>         <mailto:osm at na1400.info>> het volgende geschreven:
>>
>>             Rob wrote:
>>             > weet iemand (kleptog?) de locatie van de nederlandse osm
>>             file ?
>>             > heb even op de wiki rondgekeken maar helaas nog niet
>>             gevonden
>>             >
>>             Hier staan allemaal up-to-date excerpts:
>>             http://download.geofabrik.de/osm/europe/
>>
>>             _______________________________________________
>>             Talk-nl mailing list
>>             Talk-nl at openstreetmap.org <mailto:Talk-nl at openstreetmap.org>
>>             http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
>>
>>
>>
>>     ------------------------------------------------------------------------
>>
>>     _______________________________________________
>>     Talk-nl mailing list
>>     Talk-nl at openstreetmap.org <mailto:Talk-nl at openstreetmap.org>
>>     http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
>>       
>
>     _______________________________________________
>     Talk-nl mailing list
>     Talk-nl at openstreetmap.org <mailto:Talk-nl at openstreetmap.org>
>     http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Talk-nl mailing list
> Talk-nl at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
>   
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk-nl/attachments/20080208/03bef039/attachment.htm>