Landkarte sortieren

07/01/2010 - 12:34 von Ralf . K u s m i e r z | Report spam
X-No-Archive: Yes

begin Thread


Moin,

ich brauch mal 'nen Rippenstoß, mir fàllt nichts ein.

Problem: Jemand hat (mehrfach) mit Schrot auf die Landkarte
geschossen, die hat jetzt ein paar tausend Löcher. Ich habe eine Liste
mit den Koordinaten der Löcher (wir nehmen der Einfachheit halber
kartesische). Außerdem habe ich eine Liste der Koordinaten der
zehntausende von (punktförmigen) Stàdten. Und nun möchte ich an die
Liste der Löcher eine Liste derjenigen Stàdte dranmachen, die von dem
jeweiligen Loch einen Abstand von bis zu a, b, c... km haben.

Nun könnte man natürlich einfach für /jedes/ Loch die gesamte
Stàdteliste "durchklappern" und dann eine Indexdatei anlegen. Mit l
Löchern und s Stàdten ist man damit schon nach l*s Durchlàufen fertig.

Aber das sollte doch mit einer Baumstruktur auch einfacher gehen: Man
teilt die Landkarte auf in Nord- und Süddeutschland, die Teilgebiete
wieder in West und Ost usw. Wenn ich von einem Loch schon weiß, daß es
in Ostfriesland liegt, dann brauche ich in der Umgebung von München
gar nicht erst zu suchen, wenn ich bloß die Stàdte bis 100 km Abstand
haben will. Problem dabei: Auf jeder Hierarchiestufe des Baums könnte
das Loch nahe der Grenze zwischen zwei (oder gar mehr) Teilgebieten
liegen, dann muß man doch wieder in den anderen nachschauen.

Verstanden? - Gut.

Also: Wie heißt das, und wo steht das?

Oder doch brute force?


Gruß aus Bremen
Ralf
R60: Substantive werden groß geschrieben. Grammatische Schreibweisen:
adressiert Appell asynchron Atmosphàre Autor bißchen Ellipse Emission
gesamt hàltst Immission interessiert korreliert korrigiert Laie
nàmlich offiziell parallel reell Satellit Standard Stegreif voraus
 

Lesen sie die antworten

#1 Christopher Creutzig
07/01/2010 - 18:15 | Warnen spam
Ralf . K u s m i e r z wrote:

Aber das sollte doch mit einer Baumstruktur auch einfacher gehen: Man
teilt die Landkarte auf in Nord- und Süddeutschland, die Teilgebiete
wieder in West und Ost usw. Wenn ich von einem Loch schon weiß, daß es
in Ostfriesland liegt, dann brauche ich in der Umgebung von München
gar nicht erst zu suchen, wenn ich bloß die Stàdte bis 100 km Abstand
haben will. Problem dabei: Auf jeder Hierarchiestufe des Baums könnte
das Loch nahe der Grenze zwischen zwei (oder gar mehr) Teilgebieten
liegen, dann muß man doch wieder in den anderen nachschauen.

Verstanden? - Gut.

Also: Wie heißt das, und wo steht das?



Keine Ahnung, aber ich habe so etwas mal (wimre nach einer Anregung in
einem Paper zu Streamlines) so implementiert: Über die Landkarte wird
ein Gitter von Quadraten gelegt, deren Seitenlànge dem maximal gesuchten
Abstand entspricht. Dann braucht man nur die Stàdte aus neun Quadraten
anzuschauen. (Durch kleinere Quadrate kann man die Auswahl natürlich
beliebig weit vor-verfeinern, im Grenzwert bis zu einer perfekten
auswahl, auf Kosten des Speicherbedarfs.) Für Streamlines besonders
nützlich ist dabei, dass man im laufenden Prozess die Liste der Stàdte
wunderbar billig aktualisieren kann.

Für 10 EUR im Jahr erfahre ich hier sogar was meine Meinung ist.
Andere Leute müssen dafür heiraten.
[Lars Friedrich über UseNet]

Ähnliche fragen