Folgendes Problem: Ich habe einen großen Haufen Punkte, die zu Linien gemacht werden müssen. Die Punkte entstammen geophysikalischen Peilungen, die mittels eines Schiffs gemacht werden und liegen in ASCII als x,x,z-Werte vor. Soweit, so gut. Unglücklicherweise kommt beim Postprocessing beim Erzeuger die Reihenfolge durcheinander und die Punkte besitzen auch keinen timestamp oder sowas, wonach man sie sortieren könnte. Die Sortierung nach Koordinaten funktioniert auch nicht, da die Linien nicht gerade sind. Nun dache ich, das ganze liesse sich in Postgres über eine Sortierfunktion lösen, da ich die Daten und Konvertierungen eh mit PostGIS bearbeite.
Der Ansatz, den ich mir vorstelle wäre, die Punkte jeweils in eine Liste einzusortieren, an der Stelle an der die Abstände zu den Nachbarn minimal sind. Kennt da jemand einen Ansatz (oder hat so ein Problem schon mal gelöst) der auch einigermassen in endlicher Zeit abläuft? Insgesamt sind es ca 1,5 Mio Punkte in ca. 1500 Profilen (nach oben gibts aber keine Grenzen ). Für Anregungen oder alternative Ideen wäre ich sehr dankbar.
Kannst du denn effektiv Linien bilden in den Daten? Also z.B. von Hafen zu Hafen und sind die Schiffe dann den direkten Kurs gefahren?
Ansonsten fällt ja deine Idee schon wieder in sich zusammen.
Alternativ würde ich folgenden Ansatz probieren: nimm dir einen Punkt x, der ein garantierter Startpunkt ist (z.B. ein Hafen) und suche den nächsten Punkt heraus, der die geringste Entfernung hat. Die Entfernung zwischen den Koordinaten sollte sich berechnen lassen, oder?
Sorry, der Vorgang war wohl etwas zu kurz beschrieben.
Also, das Peilschiff fährt immer einmal quer zum Fluß von rechts nach links und macht dabei seismische Messungen, und bestimmt seine Position über DGPS. Das ergibt ca. 500-1500 Punkte pro Profilfahrt im Abstand von <10 cm, d.h. ich kann auch nicht zwischen Punktabständen und Schwankungen der Schiffsposition unterscheiden (sonst könnte ich einfach nach koordinaten sortieren und gut wärs). Profile längs zum Fluß enthalten 5000 und mehr Punkte. Die Koordinaten werden in eine Datei geschrieben. Diese erhobenen Daten werden nach der Messung noch überarbeitet, dabei wird die Reihenfolge der Punkte zerwürfelt. Dabei ist es eben dummerweise nicht sicher, wo der Anfangspunkt des Profils liegt. Die Genauigkeit der Messung liegt im Bereich von 1-2 cm und muß so auch erhalten werden, ansonsten könnte man da was anderes finden. Leider habe ich auch weder Einfluß auf das Messen noch auf das Postprocessing , sondern krieg das hier nur auf den Schreibtisch.
Ich hatte mal den Ansatz (in ArcGIS) gemacht, mir in den Dateien ungestörte Blöcke zu suchen und die zu sortieren, was auch gut geklappt hat, jedoch noch einiges an händischer Nacharbeit benötigte. Ausserdem waren da mehrere Unterscheidungskriterien wie der Abstand nur hardcoded bzw nur von Hand festzulegen, was sich als großer Nachteil erwies. Da wir nun sukkzessive unsere Softwareplattform ändern und auch diese Sachen in einem WebGIS mit PostgreSQL weitgehend automatisiert bereitstellen wollen, muß ich da halt noch mal bei gehn.
Hmm, hört sich ja fast so an, als ob da jemand nicht mitgedacht hat beim Postprocessing.
Wie weit würdest du mit folgender Idee kommen: du nimmst einen beliebigen Punkt und suchst den am nächsten liegenden heraus. Das setzt du fort, bis du keine Punkte mehr hast, die in einer vernünftigen Reichweite (cm Bereich) liegen. Als Ergebnis hast du eine Reihe von Punkten, die du aufgeschlüsselt hast plus eine Menge Punkte x, die noch nicht sortiert sind (die andere Seite vom Startpunkt). Dort setzt du jetzt noch mal an und sortierst den Rest ein.
Exzellente Idee.
Warum denke ich nur immer von hinten durch die Brust ins Auge bis mir einer eine Tritt gibt…
Vielen Dank, you made my day.
Werde natürlich über das Ergebnis berichten.
). Für Anregungen oder alternative Ideen wäre ich sehr dankbar.
