<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
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:<br>
<br>
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).<br>
<br>
L := lijst van punten uit Q gesorteerd op OL<br>
p := element uit P, dus punt waarvan we dichtstbijzijnde punt uit Q
willen weten<br>
<br>
i := punt met |p.OL - L[i].OL| zo klein mogelijk, deze kun je in
logaritmische tijd vinden<br>
d := afstand(p, L[i])<br>
q := L[i]<br>
j := i + 1;<br>
while ( |p.OL - L[j].OL| < d ) {<br>
d2 := afstand(p, L[j])<br>
if ( d2 < d ) {<br>
d := d2<br>
q := L[j]<br>
}<br>
j += 1<br>
}<br>
j := i - 1;<br>
while ( |p.OL - L[j].OL| < d ) {<br>
d2 := afstand(p, L[j])<br>
if ( d2 < d ) {<br>
d := d2<br>
q := L[j]<br>
}<br>
j -= 1<br>
}<br>
<br>
return q<br>
<br>
<br>
Dit algoritme is natuurlijk nog niet volledig, zo moet je nog nadenken
over een paar punten:<br>
* |p.OL - L[j].OL| heeft waarschijnlijk een andere eenheid dan d, dat
moet je even omrekenen<br>
* eventueel kun je in deze while loop i.p.v. tegen d, degen minimum(d,
MAX-AFSTAND) controleren<br>
* 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)<br>
<br>
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.<br>
<br>
Steven<br>
<br>
<br>
Rob schreef:
<blockquote
cite="mid:f3970e6e0802080011o59c287eid7b0ec01fbd82446@mail.gmail.com"
type="cite">hoe wil je dit gaan sorteren.. b/r-tree ? geef eens een
hint<br>
ondertussen ga ik xpath eens pesten<br>
<br>
Groeten<br>
Rob<br>
<br>
<div><span class="gmail_quote">Op 07-02-08 heeft <b
class="gmail_sendername">Steven te Brinke</b> <<a
moz-do-not-send="true" href="mailto:s.tebrinke@student.utwente.nl">s.tebrinke@student.utwente.nl</a>>
het volgende geschreven:</span>
<blockquote class="gmail_quote"
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div bgcolor="#ffffff" text="#000000">Hallo,<br>
<br>
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.<br>
<br>
Groeten,<br>
Steven<br>
<br>
<br>
Rob schreef:
<blockquote type="cite">
<div><span class="e" id="q_117f5bc2ee34cddb_1">ik heb die
wpned-zuid.gpx (1701 waypoints) eens tegen de
places.osm (8875) laten draaien, om een indruk te krijgen van
performance<br>
en dit is een stukje output<br>
...<br>
wpt 52C37 close to Pannenschop @ 587m<br>
wpt 52C39 close to Vreewijk @ 300m<br>
wpt 52C43 close to Leensel @ 714m<br>
wpt 52C44 close to Leensel @ 1885m<br>
wpt 52C45 close to Heitrak @ 2708m<br>
wpt 52C46 close to Ommel @ 50m<br>
<br>
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<br>
de search loop
begint nu al te kraken (lees 155 seconden) aangezien we nu al 15miljoen
itteraties hebben.<br>
<br>
ik ben een andere manier aan het bedenken<br>
bereken van elk waypoint de
5meter boundingbox coordinaten en laat de node selectie door xml parser
(xpath) doen, dit moet veel efficienter zijn.<br>
<br>
<br>
<div><span class="gmail_quote">Op 07-02-08 heeft <b
class="gmail_sendername">Rob</b> <<a moz-do-not-send="true"
href="mailto:rob@coolbegin.com" target="_blank"
onclick="return top.js.OpenExtLink(window,event,this)">rob@coolbegin.com</a>>
het volgende
geschreven:</span>
<blockquote class="gmail_quote"
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">dank
u, heb nu de netherlands.osm van 600MB<br>
dat wordt flink stampen voor xml parser ;)<br>
<br>
<div><span class="gmail_quote">Op 07-02-08 heeft <b
class="gmail_sendername">Lambertus</b> <<a moz-do-not-send="true"
href="mailto:osm@na1400.info" target="_blank"
onclick="return top.js.OpenExtLink(window,event,this)">osm@na1400.info</a>>
het volgende geschreven:</span>
<div><span>
<blockquote class="gmail_quote"
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Rob
wrote:<br>
> weet iemand (kleptog?) de locatie van de nederlandse osm file ?<br>
> heb even op de wiki rondgekeken maar helaas nog niet gevonden<br>
><br>
Hier staan allemaal up-to-date excerpts:<br>
<a moz-do-not-send="true"
href="http://download.geofabrik.de/osm/europe/" target="_blank"
onclick="return top.js.OpenExtLink(window,event,this)">http://download.geofabrik.de/osm/europe/</a><br>
<br>
_______________________________________________<br>
Talk-nl mailing list<br>
<a moz-do-not-send="true"
href="mailto:Talk-nl@openstreetmap.org" target="_blank"
onclick="return top.js.OpenExtLink(window,event,this)">Talk-nl@openstreetmap.org</a><br>
<a moz-do-not-send="true"
href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl"
target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl</a><br>
</blockquote>
</span></div>
</div>
<br>
</blockquote>
</div>
<br>
</span></div>
<pre><hr size="4" width="90%"><span class="q">
_______________________________________________
Talk-nl mailing list
<a moz-do-not-send="true" href="mailto:Talk-nl@openstreetmap.org"
target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Talk-nl@openstreetmap.org</a>
<a moz-do-not-send="true"
href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl"
target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl</a>
</span></pre>
</blockquote>
</div>
<br>
_______________________________________________<br>
Talk-nl mailing list<br>
<a moz-do-not-send="true"
onclick="return top.js.OpenExtLink(window,event,this)"
href="mailto:Talk-nl@openstreetmap.org">Talk-nl@openstreetmap.org</a><br>
<a moz-do-not-send="true"
onclick="return top.js.OpenExtLink(window,event,this)"
href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl"
target="_blank">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl</a><br>
<br>
</blockquote>
</div>
<br>
<pre wrap="">
<hr size="4" width="90%">
_______________________________________________
Talk-nl mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Talk-nl@openstreetmap.org">Talk-nl@openstreetmap.org</a>
<a class="moz-txt-link-freetext" href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/talk-nl</a>
</pre>
</blockquote>
</body>
</html>