Clustern einer Punktwolke

Hallo zusammen,

ich habe folgendes Problem:
Ich habe eine Punktwolke von ca. 200.000 Punkten. Diese Punkte möchte ich nach der Entfernung clustern. D.h. ich möchte jeweils alle Punkte zusammenfügen, die untereinander nicht weiter als 1000m voneinander entfernt sind und daraus dann Flächen erzeugen.

Die Punkte (1000, 1000), (2000, 1000), (3000, 1000), (4000, 1000), (5000, 1000) würden z.B. zu Cluster 1 gehören. Die Punkte (8000, 8000) und (8000, 9000) wären dann ein neuer Cluster.

Bisher habe ich das über ein umständliches und langsames Python Script mit vielen Loops in Verbindung mit PostGIS gelöst. Habt Ihr eine Idee, wie man das relativ fix über eine PostGIS-Query lösen könnte? Ich stehe irgendwie auf dem Schlauch und bekomme keine Query hin, die das macht was ich will.

Für Hilfe wäre ich sehr dankbar!

Hallo Maik!

Du könntest einen Multipoint daraus erstellen etwa in dieser Art:

select collect(select * from punkte where y=1000)

Da könnte man auch noch Gruppierung einfügen, z.B. einen Bereich.

Oder suchst du eher was in der Form einer Indizierungnach Entfernung?
Wenn die ‘Rasterzellen’ irgendwie darstellbar sind, könnte man das Ganze auch über eine Within-Abfrage lösen.

Gruß Uwe

Das mit dem Collect zieht nicht, da die Punkte ja nicht unbedingt alle in einer Reihe liegen und auch sonst im 2d-Raum zufällig angeordnet sind.

Ich hatte mir das ganze so vorgestellt, dass ich das ganze buffere und dann die enstandenen Kreise miteinander Verschneide.

Aber irgendwie bekomme ich das nicht richtig umgesetzt ohne ewig lange Schleifen zu konstruieren.

Wie genau meinst du Indizierung nach Entfernung?

Hm, gute Frage :wink: war eher ein Gedanke an eine räumlich orientierte Sortierung der Daten.

Zwischenfrage: dürfen die Punkte in mehreren Clustern vorkommen oder ausschliesslich in einem?
Wenn sie mehrfach vorkommen dürfen, könnte man sowas wie

select collect(select t2.punkte from punkte t1, punkte t2 where distance(t1.geom, t2.geom)<1000)

versuchen(ohne Gewähr, das ist nur so ein Gedanke :wink: ). Die sollte zu jedem Punkt die liefern, die weniger als 1000 m entfernt sind und als Multipoint ausgeben. Wie die Performance allerdings aussieht weiß ich nicht.

Gruß Uwe

So etwas habe ich auch schon probiert. Die Performance ist ziemlich mies. :confused:

Du könntest eine Art Topologie-Tabelle aus Punkt-ids erzeugen. Das liese sich sicher relativ schnell aufbauen und abfragen. Im Anschluß an die Abfrage der Cluster werden erst die Geometrien aus der ‘Haupttabelle’ gesucht.

Also irgendwie so:

Punkt d<1000
1 2
1 4
1 1500
.
.
.
5000 276543
5000 56789

Gruß Uwe

Das wäre eine Idee! Ich werde es mal ausprobieren.

Was ich auch noch ausprobieren werde: Ich werde meine Schleifen beibehalten und die Punkte einfach mal nach lon und lat ordnen bevor ich durch die Schleife durchgehe. Das sollte die Sache deutlich verschnellern. Keine Ahnung warum ich da nicht gleich drauf gekommen bin :confused: :confused: :confused:

Also das ganze lag eine Weile auf Eis. Aber ich habe es jetzt letztendlich hinbekommen. Es läuft zwar immernoch eine ganze Weile. Aber ich habe es so optiomieren können, dass es annehmbar ist.

Letztendlich hat es dadurch funtioniert, dass die Punkte nach Latitude und Longitude geordnet wurden und dann nochmal nach verschiedenen räumlichen Kriterien gefiltert wurde.

Ich habe noch eine andere Möglichkeit gefunden:
Man kann auch mit MultiPoints und Buffering arbeiten. Dadurch erhält mal Multipolygone, die man dann wieder aufsplitten und mit den Einzelpunkten verschneiden kann. Fertig ist die Clusterung. Ist aber deutlich langsamer als die andere Methode. Aber je nach Anwedung und Punktmenge einfacher und ausreichend schnell.