Suche Algorithmus zur Gruppierung von Punkten (Bild)
Hallo,
ich habe ein Array of Point.
Die Punkte sind nicht zufällig verteilt.
Die Punkte sind in Gruppen angeordnet.
Ich möchte jetzt die Punkte in neue Arrays sortiert.
Ich weiß nicht wieviele Gruppen es gibt. Es gibt keine Ausreißer.... also keine Störungen oder sowas, die Punkte lassen sich eindeutig zu einer Gruppe hinzufügen.
Gruppen sollen durch den Pixelabstand unterschieden werden, wenn der Abstand über einem Schwellwert ist, dann ist der Punkt nicht Element der Gruppe.
Hat jemand eine smarte Idee für sowas?
Hier mal ein Beispiel
DANKE
(2 * b) || ! (2 * b) that = question
Ist doch easy, irgend einen Punkt nehmen, und für jeden anderen Punkt den abstand berechnen. Alle Punkte die Nah genug sind kommen in die Liste Gruppe 1 plus Startpunkt. Nun vergleicht man noch jeden punkt in Gruppe eins mit den anderen, und findet so vielleicht neue Gruppe 1 Punkte.
Wenn nicht macht man Gruppe zwei auf und wählt neuen Zufälligen Punkt aus den verbleibenden. oder alle Punkte sind weg. Dann ist man fertig.
Wenn es nicht um Millionen Punkte geht, dürfte das auch schnell genug sein.
Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!
Und was ist, wenn der Abstand von diesem gewähltem Punkt zu einem anderen Punkt zu groß ist, aber dieser andere Punkt trotzdem zu der Gruppe gehört? Wie zum Beispiel bei großen Mengen?
(2 * b) || ! (2 * b) that = question
Deswegen vergleicht man ja den Abstand der neu Aufgenommenen Punkte auch mit den Restlichen!
Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!
Das hätte eine Laufzeit von n*n
(2 * b) || ! (2 * b) that = question
Was du suchst, nennt sich Cluster-Analyse.
Dafür gibt es ganz unterschiedliche Algorithmen.
Ein ganz simpler wäre der K-Means Algorithmus, der allerdings vorher die Anzahl der Clustern kennen muss.
Deswegen vergleicht man ja den Abstand der neu Aufgenommenen Punkte auch mit den Restlichen!
Das hätte eine Laufzeit von n*n
Das muss aber nicht sein, da wir ja einen metrischen Raum haben.
Hier gibt es also (dank der Dreieckungleichung bei den Abständen) wesentlich bessere Algorithmen.
Zum speichern der Punkte könnte man beispielsweise k-d-Bäume verwenden, der das "Finde den Punkt, der am dichtesten liegt" wesentlich schneller erledigt.
Wenn du sogar nur ein diskretes Raster der Punkte mit begrenztem Ausmaß hast, (nennen wir es mal Bild) kannst du auch für jeden Pixel einmalig den dichtesten Punkt bestimmen.
Quasi ein diskretes Voronoi-Diagramm. Dann ist die Abfrage nach dem dichtesten Punkt in O(1) möglich.
beste Grüße
zommi
PS: die Beiträge auf der englischen Wiki sind natürlich auch immer gut als Ergänzung.