Ergebnis 1 bis 9 von 9

Thema: Clustern einer Punktwolke

  1. #1
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard 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!

  2. #2
    Gisman ist offline Erfahrener Benutzer
    Registriert seit
    20.01.2006
    Ort
    Pfalz
    Beiträge
    794

    Standard

    Hallo Maik!

    Du könntest einen Multipoint daraus erstellen etwa in dieser Art:
    Code:
    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
    Have a lot of fun!

  3. #3
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard

    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.

  4. #4
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard

    Wie genau meinst du Indizierung nach Entfernung?

  5. #5
    Gisman ist offline Erfahrener Benutzer
    Registriert seit
    20.01.2006
    Ort
    Pfalz
    Beiträge
    794

    Standard

    Zitat Zitat von Maik Beitrag anzeigen
    Wie genau meinst du Indizierung nach Entfernung?
    Hm, gute Frage 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

    Code:
    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 ). 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
    Have a lot of fun!

  6. #6
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard

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

  7. #7
    Gisman ist offline Erfahrener Benutzer
    Registriert seit
    20.01.2006
    Ort
    Pfalz
    Beiträge
    794

    Standard

    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
    Have a lot of fun!

  8. #8
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard

    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

  9. #9
    Maik ist offline Benutzer
    Registriert seit
    20.07.2006
    Beiträge
    74

    Standard

    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.

Ähnliche Themen

  1. Antworten: 4
    Letzter Beitrag: 16.07.2011, 23:55
  2. Antworten: 2
    Letzter Beitrag: 25.08.2010, 13:47
  3. Polygon aus Punktwolke
    Von Otfrid im Forum PostGIS
    Antworten: 5
    Letzter Beitrag: 04.09.2009, 13:07
  4. Antworten: 1
    Letzter Beitrag: 06.12.2007, 17:08
  5. Tabellenzeilen nach IDs clustern
    Von gnoerz im Forum SQL
    Antworten: 6
    Letzter Beitrag: 24.10.2007, 20:49

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  

Links: Tobias Bauer - IT- und Funkdienstleistungen   -   Bilderrahmen-kaufen.de - Der Onlineshop für Bilderrahmen & Fotorahmen   -   Funkforum