Punkte in 2D-Array sortieren

Treue Seele

04.11.2021, 11:24

Punkte in 2D-Array sortieren

Hi,

ich habe hier ein Sortierproblem mit Koordinatenpunkten, welches sich nicht mit einfachem Vergleichen der minimalen X/Y-Koordinate erreichen lässt. Folgendes Beispiel: Die Koordinaten kommen unsortiert in einem Array aus 25 Elementen, welche folgendes Muster ergeben:

(Link)

Sortiert werden soll jetzt in ein 2D 5x5 Array zeilenweise von links nach rechts und von oben nach unten. Wie zu sehen ist (farblich hervorgehoben), sind diese Koordinatenpunkte tasächlich in Reihen angeordnet. Mein Problem: der in Y höchste Punkt aus z.B. der zweiten Reihe (rot) kann höher angeordnet sein als der in Y niedrigste Punkt der ersten Reihe, die Reihen überlappen sich in der Höhe also. Trotzdem sollen in sortiertem Zustand die Reihen (schwarz, rot, grün usw.) erhalten bleiben, d.h. die erste Reihe des sortierten Ziel-Arrays soll nur die schwarzen Punkte enthalten, egal wie weit diese sich in Y mit den roten Punkten überlappen.

Ich muss die Koordinaten also irgendwie reihenweise "abtragen" - nur wie stelle ich das am cleversten an?

Eine (vereinfachende?) Vorbedingung ist, dass dieses Array immer quadratisch ist, also es gibt immer genau so viele Reihen wie Spalten.

Danke!

Zum Seitenanfang

Administrator

David Scherfgens Website | Konzentrationstest Polizei

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

04.11.2021, 12:33

In deinem Bild sind sämtliche Punkte der Spalte 1 links von sämtlichen Punkten der Spalte 2, usw.
Trifft das immer zu? Wenn ja, dann einfach alle Punkte nach x sortieren. Die ersten 5 gehören zur ersten Spalte, die zweiten 5 zur zweiten Spalte, usw. Innerhalb der Spalten dann nach y sortieren, fertig.

Meine ursprüngliche Antwort

Gibt's irgendwelche Aussagen zur maximalen Abweichung eines Punktes von seiner "vorgesehenen" Position im Gitter?
Wenn die Punkte beliebig stark gestreut sein können, dann ist das Problem im Allgemeinen unlösbar.

Ansonsten würde ich sowas machen wie: Beginne mit einem gut identifizierbaren Punkt, z. B. demjenigen mit geringster Distanz zur linken oberen Ecke des Bounding Rectangles aller Punkte. Das wäre im Beispiel der linke obere schwarze Punkt.
Dann versuche den besten Kandidaten für den rechten Nachbarpunkt zu finden. Dazu kannst du Kriterien nutzen wie Winkel zum Punkt (sollte möglichst nah an 0° sein) und Distanz zum Punkt (sollte möglichst nah an der "perfekten" Distanz sein). Wiederhole das so lange, bis du die erste Zeile abgearbeitet hast. Dann wiederhole das Ganze, wobei du die schon zugeordneten Punkte bei der Ermittlung des Bounding Rectangles ignorierst. Wie du die Kriterien (Winkel, Distanz) am besten gewichtest, damit es gut funktioniert, musst du schauen.

Du könntest auch die Punkte in 5 Cluster clustern. Wenn das normalerweise so aussieht wie in deinem Bild, dann sollte jedes Cluster einer Spalte entsprechen. Dann brauchst du nur noch die Cluster nach ihrer mittleren x-Koordinate zu sortieren und innerhalb der Cluster die Punkte anhand ihrer y-Koordinate. Siehe https://stats.stackexchange.com/question…umber-of-points

Und hier hat jemand ein ähnliches Problem: https://stackoverflow.com/questions/1421…oints-to-a-grid

Zum Seitenanfang

Treue Seele

04.11.2021, 13:15

Zitat von »David Scherfgen«

In deinem Bild sind sämtliche Punkte der Spalte 1 links von sämtlichen Punkten der Spalte 2, usw.
Trifft das immer zu?

Leider nein, das ist wie bei den Zeilen - die können ineinander verschoben sein.

Zum Seitenanfang

Jonathan

Community-Fossil

Beiträge: 3 820

04.11.2021, 18:49

Klingt kniffelig.

Ich denke, man könnte sowas vermutlich mit Ganzzahlige lineare Optimierung lösen, indem man darüber optimiert, welche Punkte durch Kanten miteinander verbunden werden um ein Grid zu bilden. Da formuliert man dann so Bedingungen wie "Jeder Punkt in der Mitte muss mit 4 anderen Punkten verbunden sein" und "Verbindungen müssen kürzer als eine Maximallänge sein", und muss dann aber ggf. schon die Auflösung (finde 5x6 Punkte) vorgeben. Das ist eine ziemlich allgemeine Lösung die auch bei ziemlich krassen Verzerrungen funktioniert, aber auch sehr aufwändig aufzusetzen, wenn man noch nie damit gearbeitet hat.

Ansonsten hilft es natürlich, mehr über das Problem zu wissen. Warum liegen die Punkte nicht auf einem Grid? Ist das Rauschen oder eine systematische Verzerrung? In deinem Beispiel könnte man sich etwa die konvexe Hülle der Punktwolke anschauen und eine Abbildung finden, die diese auf ein Rechteck warpt. Dadurch wären dann alle Spalten auf einer Höhe, im Beispiel sind ja die mittleren tiefer.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

Administrator

David Scherfgens Website | Konzentrationstest Polizei

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

04.11.2021, 20:57

Zitat von »Elmi«

Zitat von »David Scherfgen«

In deinem Bild sind sämtliche Punkte der Spalte 1 links von sämtlichen Punkten der Spalte 2, usw.
Trifft das immer zu?

Leider nein, das ist wie bei den Zeilen - die können ineinander verschoben sein.

In meiner ersten Antwort hatte ich noch eine Frage gestellt und eine mögliche Lösung skizziert. Ist aber ausgeblendet, weil mir dann die Sache mit den Spalten auffiel. Klick in meiner Antwort mal auf „Meine ursprüngliche Antwort“.

Zusätzlich dazu noch eine Frage: Ist denn wenigstens garantiert, dass wenn ein Punkt im originalen, nicht verzerrten Gitter rechts/links/oben/unten von einem direkt benachbarten Punkt liegt, dies dann auch im verzerrten Gitter gilt? Wenn ja, dann müsste es auf jeden Fall eine eindeutige Lösung geben, wo diese Bedingung für alle Paare von benachbarten Punkten erfüllt ist.

Und ja, ein paar mehr Hintergrundinfos wären hilfreich. Worum handelt es sich da, wie kommt die Verzerrung zustande? Ist das eine Art Kalibrierungsverfahren?

Zum Seitenanfang

Treue Seele

05.11.2021, 07:06

OK, vielleicht noch ein paar Hintergrundinfos zu dem Problem: es handelt sich bei den Punkten um ein Grid, d.h. die gehören zeilen- und spaltenweise zueinander. Urpsrünglich (Solldaten) stehen die perfekt unter- und nebeneinander und haben auch exakt identische Abstände. Die vorliegenden Punkte hingegen sind die tatsächlichen, gemessenen Daten. Das Ganze dient im weiterne Sinne einer Art Kalibrierung.

Der Kackpunkt: die gemessenen Daten kommen aus einem Bild und werden dort per Konturerkennung (OpenCV) detektiert. Dort werden die in irgend einer Reihenfolge erkannt, es ist also nicht möglich, die Eingangsdaten auf Grund Ihrer Reihenfolge schon irgendwie ihrer Position zuzuordnen.

Zum Seitenanfang

Administrator

David Scherfgens Website | Konzentrationstest Polizei

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

05.11.2021, 08:30

Wie gesagt, in meiner ersten Antwort hatte eine mögliche Lösung skizziert:

Zitat von »"David Scherfgen"«

Ansonsten würde ich sowas machen wie: Beginne mit einem gut identifizierbaren Punkt, z. B. demjenigen mit geringster Distanz zur linken oberen Ecke des Bounding Rectangles aller Punkte. Das wäre im Beispiel der linke obere schwarze Punkt.
Dann versuche den besten Kandidaten für den rechten Nachbarpunkt zu finden. Dazu kannst du Kriterien nutzen wie Winkel zum Punkt (sollte möglichst nah an 0° sein) und Distanz zum Punkt (sollte möglichst nah an der "perfekten" Distanz sein). Wiederhole das so lange, bis du die erste Zeile abgearbeitet hast. Dann wiederhole das Ganze, wobei du die schon zugeordneten Punkte bei der Ermittlung des Bounding Rectangles ignorierst. Wie du die Kriterien (Winkel, Distanz) am besten gewichtest, damit es gut funktioniert, musst du schauen.

(...)

Und hier hat jemand ein ähnliches Problem: https://stackoverflow.com/questions/1421…oints-to-a-grid

Noch eine Idee: In OpenCV gibt's die Funktion cv::findChessboardCorners zur Erkennung eines Schachbrettmusters. Dort müssen nach dem Finden der Eckpunkte (die möglicherweise stark verzerrt sind) diese einem Gitter zugeordnet werden. Die müssen also ein ähnliches Problem lösen. Du kannst im Quellcode ja mal nachschauen, wie das gelöst ist. Evtl. funktiniert das auch bei dir.

Und noch eine Idee: Kannst du das Kalibrierungsmuster frei definieren? Wenn ja, dann könntest du das Gitter horizontal so weit strecken, bis es dann wirklich so ist, dass die Punkte der n. Spalte immer allesamt links von den Punkten der (n+1). Spalte liegen. Dann ist die Lösung trivial.

Meine Frage hast du nicht beantwortet:

Zitat von »David Scherfgen«

Zusätzlich dazu noch eine Frage: Ist denn wenigstens garantiert, dass wenn ein Punkt im originalen, nicht verzerrten Gitter rechts/links/oben/unten von einem direkt benachbarten Punkt liegt, dies dann auch im verzerrten Gitter gilt? Wenn ja, dann müsste es auf jeden Fall eine eindeutige Lösung geben, wo diese Bedingung für alle Paare von benachbarten Punkten erfüllt ist.

Wenn du Hilfe möchtest, dann solltest du schon ein bisschen mehr mitwirken und dir nicht alles aus der Nase ziehen lassen ... Und wozu die ganze Geheimniskrämerei? Sag doch klar, was Sache ist, denn daraus lassen sich möglicherweise sehr wichtige Informationen ableiten. So habe ich fast das Gefühl, dass es hier um deine Abschlussarbeit oder Ähnliches geht.

Zum Seitenanfang

Treue Seele

05.11.2021, 11:08

Zitat von »David Scherfgen«

Und wozu die ganze Geheimniskrämerei? Sag doch klar, was Sache ist, denn daraus lassen sich möglicherweise sehr wichtige Informationen ableiten.

Ganz einfach: weil es sich um technische Details handelt, die 1. nichts zur Sache tun und 2. Fachwissen abseits dieses Algorithmus erfordern, das hier bestimmt keiner hat. Oder was genau ändert sich für dich, wenn ich dir verrate, dass diese Verzerrungen durch eine spezielle Optik entstehen? Oder wenn ich dir den exakten Aufbau dieser Optik zeige? Hast du hier detaillierte Kenntnisse?

Zitat von »David Scherfgen«

So habe ich fast das Gefühl, dass es hier um deine Abschlussarbeit oder Ähnliches geht.

Ja, nee, ist schon klar...lass gut sein!

Zum Seitenanfang

Administrator