Koordinatenpunkte zusammenfassen

Hallo zusammen,

vielleicht kann mit jemand auf die Sprünge helfen.

Ich habe eine Liste mit X/Y Koordinaten die Punkte auf einer zweidimensionalen Fläche entsprechen. Nun möchte ich die Anzahl der Punkte reduzieren indem ich Häufungen zusammenfasse.
Also Punkte die < Abstand X zueinander haben werden zusammengefasst und durch einen "Mittelpunkt" ersetzt. Kennt jemand einen Ansatz wie man das lösen kann ohne den Abstand von jedem zu jedem Punkt zu überprüfen?
Ich habe schon überlegt die Fläche in Quadranten einzuteilen und so schon mal vorsortieren, wenn der "Haufen" dann aber mehrere Quadranten streift ist das auch nicht so einfach.

Ich programmiere in VB.NET, aber einen Ansatz wie man sowas angeht oder ein Stichwort mit dem ich weitersuchen kann würden mir schon weiterhelfen.

Gruß Tek

Schau mal nach KD-Bäumen im Raytracing-Kontext. Damit sollte sich das Problem sehr effizient lösen lassen. Gibt noch Tonnenweise andere mögliche Datenstrukturen aber die scheint mir am schnellsten (wenn auch nicht am unkompliziertesten) zu sein. Der Baum macht übrigens genau das was du beschrieben hast: "in Quadranten einteilen".

Am Ende musst du in dem Baum eine Nearest-Neigbour-Search durchführen und müsstest damit die gesuchten Punkte finden. Werte aufaddieren, teilen und den neuen Punkt einsetzen.

Vielleicht findest du unter dem Begriff "Clustering" passende Ansätze.
Ich kenne leider auch nur die bisher von dir genannten.

Danke für die bisherigen Antworten.
Die KD_Baumgeschichte werde ich mir mal genauer anschauen.

Und danke auch für das Stichwort "Clustering" hab dazu was gefnuden das fast genau mein Problem beschreibt:
Hier hatte wohl jemand ein ähnliches Problem. Da werd ich mich mal einlesen.

Hallo,

du könntest auch Quadranten nehmen und dazu einen Sicherheitsbereich in der Größe deines maximalen Abstands dazu zählen.

Skizze:


Angenommen dein maximaler Abstand ist "d".

Der innere Bereich ist dein Quadrant (sollte etwa 10d*10d oder so groß sein) und darum herum gibt es den Sicherheitsbereich (der dann insgesamt 12d*12d groß ist).

So musst du natürlich einige Punkte doppelt untersuchen, aber hast kein wirkliches n²-Problem mehr. Vielleicht hilft dir der Ansatz weiter.

Oder eine Baumstruktur bauen, ähnlich einem Suchbaum, nur halt deinen Bedürfnissen angepasst.
Dann kannst beim einfügen eines Wertes schauen wie groß der Abstand vom Wert des Eltern Knotens ist und reagieren.

Damit hättest du eine wesentlich bessere Laufzeit (log n -> Ergebnismenge nach jedem Knoten halbiert) als alles mit allem zu vergleichen (n^2). Sehr praktisch wenn du verschiedene Abstände testen willst, wäre dann nur eine einzige Variable.

Die Quadranten würden auch gehen, lässt sich dann halt nicht so gut regulieren. Und mit Pech hast den Punkt genau auf der Linie, dann musst wieder den Fall im Falle beachten etc. Wartungstechnisch ungünstig und Laufzeittechnisch eventuell auch, da man immer die Quadrantenübertritte berechnen oder hardcoden müsste.

/edit
Ok, KD Bäume sind sowas...siehst, man muss nicht alles lernen, man erfindet es einfach neu

Ich habe mich mal versucht in die KD-Tree Geschichte einzulesen, das is aber wohl etwas zu hoch für mich und wäre für meine Anwendung aber auch overkill.

Habe jetzt mit Hilfe des Lösungsansatzes aus meinem Link und den Tips hier einen einfachen Algorithmus geschrieben mit dem ich ganz gut zurecht komme:

Ich habe mir eine Clusterliste erstellt die pro Element einen X/Y Mittelwert und einen Punktezähler enthält.
Der erste Koordinatenpunkt wird in die Liste eingetragen und ist dann automatisch auch der erste Clustermittelpunkt.
Nun wird in einer Schleife über alle Punkte der Abstand des aktuellen Punktes zu den Clustermittelpunkten überprüft. Wird mein Schwellwert überschritten wird ein neuer Cluster erzeugt, wenn nicht bilde ich aus dem entsprechenden Clustermittelpunkt und dem aktuellen Punkt den neuen Clustermittelpunkt und erhöhe den Zähler.

Mit der Mittelwertbildung bin ich noch etwas am experimentieren und möchte versuchen die weiter entfernten Punkte weniger stark zu gewichten.

Alles in allem funktioniert es aber so wie ich es möchte, vielen dank an alle Tipgeber!

Tekwar schrieb:

Mit der Mittelwertbildung bin ich noch etwas am experimentieren und möchte versuchen die weiter entfernten Punkte weniger stark zu gewichten.

Zum Vergrößern anklicken....

Wenn du einfach den Durchschnitt (aufsummieren und durch die Anzahl teilen) ausrechnest werden die Mittelpunkte ja automatisch in Richtung der Häufungspunkte gezogen.
Wenn dir das nicht ausreicht, wäre ein einfacher Ansatz, zuerst die Mittelpunkte mittels Durchschnitt und dann iterativ gewichtete Mittelpunkte z.B. auf Basis der "Sum of squared differences" zu berechnen. Kann man natürlich besser machen, z.B. mit Kernel Density Estimation, aber das willst du vermutlich eher nicht.

Matlab kann das unter der Funktion meshgrid bzw. griddata. Wenn Du die Daten also nur einmalig verarbeiten musst, ist das vielleicht was für Dich.

schdrom schrieb:

Wenn du einfach den Durchschnitt (aufsummieren und durch die Anzahl teilen) ausrechnest werden die Mittelpunkte ja automatisch in Richtung der Häufungspunkte gezogen.

Zum Vergrößern anklicken....

Jep das ist das Problem. Ich hab aber jetzt eine brauchbare Lösung gefunden. Ich berechne eh die Bounding Box für jedes Cluster indem ich mir die absoluten max und min X/Y Werte merke. Davon der Mittelpunkt funktioniert echt super.

@Kanibal

Ne das reicht leider nicht, muss das immer wieder frisch berechnen.

Das ganze gibt eine Visualisierung für ein Bildverarbeitungssystem bei dem die Oberfläche von Bauteilen geprüft wird.
Bei einem Fehler findet das System aber teilweise recht viele Fehlstellen die aber von der gleichen Ursache ausgehen. Diese möchte ich zusammenfassen damit der Bediener jeden Fehler nur einmal angezeigt bekommt.

Hast du dir eigentlich schon mal k-means-custering angesehen? Das lässt sich eigentlich sehr einfach implementieren.

@Miuwa

Habs grade bei Wikipedia mal überflogen, sieht interessant aus. Da man aber, so wie ich es verstanden habe, vor dem Start schon die Anzahl der Cluster irgendwie festlegen muss passt das für meine Anwendung nicht wirklich.