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* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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@openstreetmap.org <mailto:Talk-nl@openstreetmap.org>
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
------------------------------------------------------------------------
_______________________________________________
Talk-nl mailing list
Talk-nl@openstreetmap.org <mailto:Talk-nl@openstreetmap.org>
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
_______________________________________________
Talk-nl mailing list
Talk-nl@openstreetmap.org <mailto:Talk-nl@openstreetmap.org>
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
------------------------------------------------------------------------
_______________________________________________
Talk-nl mailing list
Talk-nl@openstreetmap.org
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
_______________________________________________
Talk-nl mailing list
Talk-nl@openstreetmap.org
http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl
