[Talk-de] Algorithmus für Kachelsuche entlang eines Tracks

Frederik Ramm frederik at remote.org
Sa Sep 5 20:23:56 UTC 2009


Hi,

> kennt einer von Euch einen Algorithmus um alle Kacheln zu ermitteln die 
> bei einer bestimmten Zoomstufe von einem Track berührt werden ???

Man koennte mit einem Skript schnell alle Kacheln als Rechtecke in einer 
PostGIS anlegen, und dann einfach einen PostGIS-Query machen, der sagt 
"gib mir alle Rechtecke, die sich mit diesem Linestring schneiden".

Wenn ich es selber programmieren wuerde, dann aehnlich, wie Gary es 
vorschlug:

for i = 0; i < punkte.anzahl - 1; i++
{
    beruehre_kacheln(punkt[i], punkt[i+])
}

sub beruehre_kacheln(p0, p1)
{
    kachel0 = finde_kachel(p0)
    kachel1 = finde_kachel(p1)
    if (kachel0 == kachel1)
    {
       vermerke_kachel_als_benutzt(kachel0)
       return
    }
    mittelpunkt = (p0 + p1) / 2
    beruehre_kacheln(p0, mittelpunkt)
    beruehre_kacheln(mittelpunkt, p1)
}

Damit erwischst Du garantiert alle Kacheln, die der Track beruehrt, aber 
  natuerlich kann es sein, dass Du manchmal, wenn ein Track ganz knapp 
an einer Kachelkante vorbeifuehrt, noch etwas mehr haben moechtest. Das 
waere mit der PostGIS-Loesung wieder recht trivial (Buffer um Track, 
dann Schnitt-Tiles berechnen)...

Bye
Frederik




Mehr Informationen über die Mailingliste Talk-de