Kachelauswahl zur Straßensuche

Abbildung 5.1: Auswahl der Kacheln abhängig von der Position.

Aufgrund der Kachelstruktur der Kartendaten genügt es, nur einen Teil der Straßenzüge zu untersuchen. Im ersten Ansatz wurden zu einem Punkt alle Straßen betrachtet, die auf der gleichen Kachel wie dieser Punkt, oder auf einer der acht benachbarten Kacheln lagen.

So viele Kacheln sind aber garnicht erforderlich; um alle Straße in einer Entfernung $d$ um den Punkt $(p_x,p_y)$ zu finden genügt es, alle Kacheln zwischen $(p_x-d,p_y-d)$ und $(p_x+d,p_y+d)$ betrachtet. Falls $d$ kleiner ist als die Kachelgröße sind das eine, zwei oder vier Kacheln. Eigentlich wäre es ausreichend, alle Kacheln im Umkreis $d$ um $P$ zu bestimmen, allerdings wird die Berechnung bei einem Umgebungsrechteck statt einem Umgebungskreis einfacher und es wird nur in wenigen Fällen eine Kachel mehr als mit Umgebungskreis ausgewählt.

Betrachtet werden muss eine Kachel für alle Punkte, die von allen Kachelrändern mindestens $d$ entfernt sind. Position 1 in Abbildung 5.1 ist ein solcher Punkt, es wird nur Kachel A gewählt. Zwei Kacheln müssen für alle Punkte betrachtet werden, die von genau einem Kachelrand weniger als $d$ entfernt sind, wie es an den Positionen 2 und 3 der Fall ist. Von Position 2 aus sind die Kacheln A und B zu betrachten. Auch in Position 3 werden zwei Kacheln benötigt: B und E. Falls zwei Kachelränder vom Punkt aus weniger als $d$ entfernt sind, müssen vier Kacheln untersucht werden, wie das an Position 4 der Fall ist. Im Beispiel sind das die Kacheln A, B, D und E. In der Abbildung sind die Suchrechtecke grün, die Kachelgrenzen rot eingezeichnet.

Es werden maximal vier Kacheln ausgewählt, das ist eine deutliche Verbesserung zu den im ersten Ansatz gewählten neun Kacheln.

Damit bei der Kachelauswahl im Programm keine Fallunterscheidung gemacht werden muss, und damit die Routine unabhängig von der Größe des Suchrechtecks und der Kachelgröße funktioniert, wird von der zu verbessernden Position aus berechnet, auf welcher Kachel die linke obere Ecke des Suchrechtecks liegt. Es werden alle Kacheln zwischen dieser Kachel und der Kachel, auf der die rechte untere Ecke des Suchrechtecks liegt, betrachtet. Da jede Kachel über zwei Koordinaten identifiziert wird, können alle zu prüfenden Kacheln durch zwei geschachtelte for-Schleifen durchlaufen werden. Dieses Verfahren funktioniert auch, falls $d$ größer als die Kachelgröße sein sollte.

Eine weiter Vorauswahl der Straßenabschnitte innerhalb der Kachel würde zusätzliche Daten über die Begrenzung des Straßenzugs erfordern. Zu jedem Straßenzug das zugehörige Begrenzungsrechteck in den Daten abzulegen würde mehr Speicherplatz verbrauchen, dafür wäre weniger Rechenzeit zur Straßensuche erforderlich. Da das verwendete Verfahren zur Straßensuche auch ohne diese Verbesserung schnell genug ist, wird auf eine weitere Rechenzeitoptimierung verzichtet um Speicherplatz zu sparen.