Laden...

Koordinaten nach ihrem Abstand zueinander aber ich richtiger Richtung sortieren

Erstellt von Gimmick vor 7 Jahren Letzter Beitrag vor 7 Jahren 5.514 Views
G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren
Koordinaten nach ihrem Abstand zueinander aber ich richtiger Richtung sortieren

Hallo,

ich habe hier eine Liste Koordinaten<Point> mit [N]-Punkten, die ich, ausgehen von einem Startpunkt, nach ihrem Abstand zueinander sortieren möchte.

Ein Bild zur Veranschaulichung hängt an. Die richtigen Koordinaten sind noch etwas mehr verwurschtelt.

Bisher mache ich es so, dass ich von Punkt[0] jeden Abstand Punkt[0]<->Punkt[N-1] berechne, den kürzesten Abstand merke, Punkt[0] + Punkt[minAbstand_1] in eine neue Liste Sortiert<Point> stecke und aus der Liste Koordinaten<Point> lösche.
Dann nehme ich Punkt[minAbstand_1] und berechne jeden Abstand Punkt[minAbstand_1]<->Punkt[N-2]. Punkt[minAbstand_2] wird wieder an Liste Sortiert<Point> angehängt und aus Liste Koordinaten<Point> gelöscht.
.
.
.
usw.

Das funktioniert auch, ist aber langsam.

Habt ihr Tips, wie das schneller gehen könnte?

Listen nehme ich weil die Anzahl der Punkte flexibel sein muss. Ich könnte aber die Punkte nach speichern in der Liste in ein Array überführen, wenn das was bringt.

P
40 Beiträge seit 2011
vor 7 Jahren

Hallo,

gehören die Punkte zu einer Funktion?
Wenn ja, ist es das Ziel die Punkte der Reihe nach (wie sie auf der Funktion vorkommen) zu sortieren oder wirklich anhand des Abstandes zwischen einzelnen Punkten?

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

gehören die Punkte zu einer Funktion?

Ne, kommen nicht als Ergebnis aus einer Funktion, werden dann nach der Sortierung teilweise genutzt um eine Regression durchzuführen.

Hinweis von Coffeebean vor 7 Jahren

Keine Full-Quotes bitte [Hinweis] Wie poste ich richtig?

O
79 Beiträge seit 2011
vor 7 Jahren

Eigentlich ganz einfach.

Man nehme Punkt[0]. Nun berechne Er alle Entfernungen der Punkte[1..n]. Der, der am dichtesten dran ist, wird dann Punkt[1].

Man nehme Punkt[1]. Nun berechne Er alle Entfernungen der Punkte[2..n]. Der, der am dichtesten dran ist, ist Punkt[2].

Und so weiter.

Entfernungen nur einmal berechnet, Ergebnis-Liste gleich sortiert.

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Verstehe jetzt nicht den Unterschied zu meiner Methode. 🤔
Und ich bin mir auch nicht sicher was du mit "Entfernungen nur einmal berechnet" meinst.

Für jeden Punkt zu jedem anderen Punkt berechne ich doch auch nur einmal. Bin verwirrt ^^.

3.003 Beiträge seit 2006
vor 7 Jahren

Wenn deine Skizze tatsächlich dein Vorhaben abbildet, solltest du vielleicht einfach nach X-Koordinate sortieren, statt dich mit Abstandsberechnungen abzugeben.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

T
314 Beiträge seit 2013
vor 7 Jahren

Also anhand der Skizze könnte ich nun nicht erkennen, dass der letzte Punkt eine andere X-Koordinate hat 😃

Bevor Du dir Gedanken über die Geschwindigkeit machst, sollte erstmal das korrekte Ergebnis raus kommen.

3.003 Beiträge seit 2006
vor 7 Jahren

Also anhand der Skizze könnte ich nun nicht erkennen, dass der letzte Punkt eine andere X-Koordinate hat 😃

*lach* Nicht ganz falsch, ich meinte aber: wenn die Punkte sich durch eine Funktion interpolieren lassen können, dann muss man sie einfach nach x sortieren. Wenn dem nicht so ist, kann man davon ausgehen, dass auch die Abstandsermittlung für einige Fälle ein falsches Ergebnis liefert.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

2.298 Beiträge seit 2010
vor 7 Jahren

Fällt mir ja direkt eine ganz einfache Lösung ein. - Erst nach X-Sortieren und dann bei Punkten mit gleicher X-Koordinate nach Y-Sortieren. - Ach halt warte, hier bleibt ja das Problem, dass man nicht weiß in welche Richtung.

Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Bevor Du dir Gedanken über die Geschwindigkeit machst, sollte erstmal das korrekte Ergebnis raus kommen.

Also nach meiner bisherigen Methode kommt das richtige Ergebnis raus.

*lach* Nicht ganz falsch, ich meinte aber: wenn die Punkte sich durch eine Funktion interpolieren lassen können, dann muss man sie einfach nach x sortieren. Wenn dem nicht so ist, kann man davon ausgehen, dass auch die Abstandsermittlung für einige Fälle ein falsches Ergebnis liefert.

Für die Punkte wird nur in zwei Intervallen eine Regression durchgeführt.

Die Punkte entstehen durch drei Abtastungen:

1.

for(y=Image.Height-1;y>=0;y--)
  {
        for(x = 0; x < Image.Width; x++)
      {
Farbe = Pxielfarbe
if(Farbe = gesuchte Farbe && List.Contains(x,y) =false)
{List.Add(x,y)
break;}
       }
  }

for (x = 0; x < Image.Width; x++)
                {
                    for (int y = 0; y < Image.Height; y++)
                    {
Farbe = Pxielfarbe
if(Farbe = gesuchte Farbe && List.Contains(x,y) =false)
{List.Add(x,y)
break;}
                    }
                }
for (int y = 0; y < Image.Height; y++)
                {
                    for (int x =Image.Width - 1; x >= 0; x--)
                    {
Farbe = Pxielfarbe
if(Farbe = gesuchte Farbe && List.Contains(x,y) =false)
{List.Add(x,y)
break;}
}
                 }

Das ergibt den äußeren Rand der gesuchten Form.
Da der Rand Lücken aufweißt, gibts auch Treffer auf der gegenüberliegenden Seite. Der Abstand bei einem "Durchschuss" ist aber stehts größer, als zum nächsten richtigen Punkt.

Die Punkte müssten sortiert werden, über ~3-4 Punkte wird dann jeweils gemittelt. Mit diesern gröberen Punkten wird dann an zwei Stellen eine Regression dritten Grades ausgeführt.

Die Regression wird für den "geraden" Rand links und rechts durchgeführt, wobei die Achsen getauscht werden: x_regression = y_Bild ; y_regression = x_Bild

P
1.090 Beiträge seit 2011
vor 7 Jahren

Mir ist jetzt nicht klar wie so du 3x über das Bild läufst.

Wenn du nur mit Variante 1 über das Bild läufst hast du ja schon eine gewisse Ordnung in X-Richtung.

An dem Punkt hast du dann für eine Sortierung eine Weitere Abbruch Bedingung. Der Abstand (r) zum zum nächsten geprüften Punkt ist dir ja bekannt und du brauchst nur nicht mehr alle Punkte prüften sondern nur die im Intervall x +- r. (Das kann man natürlich noch weiter optimieren).

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Mir ist jetzt nicht klar wie so du 3x über das Bild läufst.

Das liegt evtl. daran, dass ich da ein break; vergessen hatte. 😦
Der Inhalt der anderen Schleifen ist identisch mit der ersten, nur die Richtung ändert sich.

Ich editier das besser mal rein.

Die Idee dahinter ist, nur die äußeren Pixel einer breiteren Linie zu finden. Daher taste ich mich quasi von link, rechts und oben an die Form ran.

Wäre die Linie komplett geschlossen hätte ich dann schon meine korrekte Reihenfolge.

T
314 Beiträge seit 2013
vor 7 Jahren

In deinem Eingangspost sagst Du, dass es bereits eine Liste von Koordinaten gibt. Wieso postest Du dann nun Code, der mit dem Bild arbeitet!?

Ein passendes Vorgehen, wenn Du eine Richtung haben möchtest, hat OlafSt ja bereits genannt.

P
1.090 Beiträge seit 2011
vor 7 Jahren

@Gimmick

Damit hast du dann aber maximal 4 Punkte. Da sollte das Sortieren des Abstandes, nicht wirklich lange dauern?

Aktuell hab ich ehrlich gesagt ein wenig den überblicke Verloren, was genau dein Problem ist.

Kannst du dass noch mal genau beschreiben und vielleicht den dazu gehörigen Code Posten?

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Wieso postest Du dann nun Code, der mit dem Bild arbeitet!?

Um deutlich zu machen wie das Problem entsteht, evtl. gibt es ja intelligente Methoden, die aus dem Problem raus entstehen.

Ein passendes Vorgehen, wenn Du eine Richtung haben möchtest, hat OlafSt ja bereits genannt.

Und ich verstehe den Unterschied zu meinem Vorgehen nicht.

@Gimmick
Aktuell hab ich ehrlich gesagt ein wenig den überblicke Verloren, was genau dein Problem ist.

Kannst du dass noch mal genau beschreiben und vielleicht den dazu gehörigen Code Posten?

Ja verstehe ich. Ich werde das mal etwas umfangreicher mit Bildchen (omg :<) ausführen:

Ich habe ein Bild mit einer bestimmten Form (keine bestimmte stetige Funktion oder sowas) und extrahiere über Grauwertbestimmung den äußersten Rand.
Dazu gehe ich vor wie in dem Bild.

Ich laufe also in der untersten Bildzeile von links nach rechts und stoppe bei einem Pixel mit gesuchtem Grauwert -> gehe eine Zeile nach oben wieder von links nach rechts:


for (int y = Image.Height - 1; y >= 0; y--)
                {
                    for (int x = 0; x < Image.Width; x++)
                    {

                        Grauwert = Farbe;
                        if(Grauwert = ok && Liste.Contains(X/Y) == false)
                         {
                          Liste.Add(X/Y) 
                          }
                          break;
                    }
                 }

Zusammen mit den drei anderen Schleifen erhalte ich bei einer geschlossenen Linie den äußeren Rand in korrekter Reihenfolge.

Jetzt hat die Linie aber Lücken und somit treffe ich auf dem weg von links nach rechts den rechten Rand von innen.

Beispiel:

Viereck mit linker Seite senkrecht in X=1 nach oben und mit Lücke in (1/4) -> Inhalt der Liste: [(1/1), (1/2), (1/3), (5/4), (1/5) ...]

Die Koordinate (5/4) ist von der rechten Seite des Vierecks.

Bisher gehe ich dann so vor, dass ich den Punkt (1/1) aus der Liste entferne und in eine neue Liste2 stecke. Dann berechne ich den Abstand von (1/1) zu jedem anderen Punkt in Liste1.
Der mit dem kürzesten Abstand wird in Liste2 angefügt und aus Liste1 entfernt - in dem Fall (1/2) usw.

Für viele Punkte dauert das.

Evtl. könnte ich schon Zeit sparen wenn ich das nur machen wenn der Abstand zum nächsten Punkt >Wurzel(2) ist. 😐
Aber den Suchvorgang an sich, wenn er nötig ist würde ich dennoch gerne beschleunigen - wenn das geht.

P
1.090 Beiträge seit 2011
vor 7 Jahren

Wie wäre es erst nach X-Sortieren und dann bei Punkten mit gleicher X-Koordinate nach Y-Sortieren

Jetzt kannst du dir den nächsten Punkt der in der nähe der X-Kordinate liegt suchen, zu ihm den Abstand (r) bestimmen und brauchst dann nur die Punkte deren X-Wert um +-r um deinen Punkt herumliegen. Das sollte schon mal die Anzahl reduzieren.

Bevor du nun den Abstand berechnest kannst du Wahrscheinlich besser vorher Prüfen ob dY > r ist.
Dann kann es der Punkt auch nicht sein.

[edit]
Ich wollte grade mal googlen wie eine Sorted List mit Punkten als Key umgeht.
Bin dann darauf gestoßen.
Order a list of points by closest distance

Sollte man mal gelesen haben:

Clean Code Developer
Entwurfsmuster
Anti-Pattern

5.657 Beiträge seit 2006
vor 7 Jahren

Hi Gimmick,

erklär uns doch mal, was du eigentlich damit vor hast. Willst du Objekte bzw. Formen in einem Bild erkennen? Dafür gibt es bereits fertige Lösungen.

Oder willst du diese Aufgabe selbst zu Übungszwecken lösen? Dann beschreib mal, welche Formen damit erkannt werden sollen. Handelt es sich dabei immer um geschlossene Kurven? Sind die Ränder der Formen immer konvex oder kann es auch konkave Objekte geben?

Für nicht-geschlossene oder konkave Formen sind dein Ansatz und die bisherigen Lösungsvorschläge allerdings nicht geeignet. Bei konkaven Umrissen kann es pro X- bzw. Y-Koordinate mehrere Punkte auf dem Umriss geben. Das müßtest du in deinem Algorithmus mit beachten.

Für geschlossene konvexe Objekte kannst du dir jedoch sehr einfach in O(n log n) die Konvexe Hülle berechnen lassen, und hättest damit das Ergebnis.

Weeks of programming can save you hours of planning

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Wie wäre es erst nach X-Sortieren und dann bei Punkten mit gleicher X-Koordinate nach Y-Sortieren

Jetzt kannst du dir den nächsten Punkt der in der nähe der X-Kordinate liegt suchen, zu ihm den Abstand (r) bestimmen und brauchst dann nur die Punkte deren X-Wert um +-r um deinen Punkt herumliegen. Das sollte schon mal die Anzahl reduzieren.

Bevor du nun den Abstand berechnest kannst du Wahrscheinlich besser vorher Prüfen ob dY > r ist.
Dann kann es der Punkt auch nicht sein.

Bin mir nicht sicher ob ich das richtig verstanden habe.
Ich hätte dann zwei Listen: Eine enthält meine Koordinaten wie sie rauskommen und die andere enthält die Koordinaten erst nach X und bei gleichen X nach Y sortiert.

Dann nehme ich P1 in Liste1 und prüfe im Prinzip nur die Punkte auf Abstand mit dx<r, wobei ich mir r dann überlegen müsste.

dy wird evtl schwer wenn man nicht vorher schon weiß wie groß die Lücken sein können.

Werde ich morgen mal testen ob ich das richtig hinbekomme und obs was bringt.

Hi Gimmick,

erklär uns doch mal, was du eigentlich damit vor hast. Willst du Objekte bzw. Formen in einem Bild erkennen? Dafür gibt es bereits fertige Lösungen.

Oder willst du diese Aufgabe selbst zu Übungszwecken lösen?

Selber machen, Projektarbeit quasi und die Formen varrieren auch nur in Position und Lage, aber eben nicht in der Form.
Die Schwierigkeit ist in dem Fall auch eher mal die gesuchten Punkte vom Hintergrund zu unterscheiden ^^. Aber das hat alles soweit funktioniert.

Nur die Sortiererei der Punkte für die Regression dauert immer etwas lange.
Ich schätze mal, dass das so ca. 4000 Punkte sind und der Gesamtprozess (in Graubildumwandeln, Sobel, Farblevel anpassen, Randpixel finden, Rand glätten, Regression durchführen, und eine kleine Suche über Bisektion + Linie einzeichnen) dauert momentan ca. 7s auf meinem kleinen Notebook.

Da würde ich gerne noch ein paar Sekunden sparen.
Hatte erst überlegt die Gesamtmenge an Punkten zu senken und nur jede 3. Zeile oder so abzusuchen, aber ich brauche zwei Punkte so genau es geht, reduzieren kann ich erst danach.
Und die Punkte hab ich auch erst wenn ich alle Punkte sortiert habe, glaube ich - bin mir gerade beim Schreiben garnicht mehr so sicher ^^.

Werde morgen mit Palins Tip mal was versuchen ^^.

D
985 Beiträge seit 2014
vor 7 Jahren

Eventuell hilft das hier


    class Program
    {
        static void Main( string[] args )
        {

            var rng = new Random();
            // Simulation von x/y Messpunkten
            var pointQuery = Enumerable
                .Range( 0, 101 )
                .Select( x => new Point( x, 2500 - ( x - 50 ) * ( x - 50 ) ) )
                .Shuffle();

            // Das ist die ermittlete Punkt-Wolke
            var pointCollection = pointQuery.ToList();
            
            var ordered_grouped_PointCollection = pointCollection
                // Gruppieren nach X
                .GroupBy( e => e.X )
                // Durchschnitt der Y-Werte ergibt den neuen Y Wert
                .Select( g => new PointF( g.Key, g.Average( e => Convert.ToSingle( e.Y ) ) ) )
                // Sortieren nach X
                .OrderBy( e => e.X ).ToList();

        }
    }

    public static class EnumerableExtensions
    {
        private static readonly Random _rng = new Random();

        public static IEnumerable<T> Shuffle<T>( this IEnumerable<T> collection, Random rng = null )
        {
            rng = rng ?? _rng;

            var list = collection.ToList();
            for (int i = 0; i < list.Count; i++)
            {
                var j = i + rng.Next( list.Count - i );
                yield return list[j];
                if (i != j)
                {
                    list[j] = list[i];
                }
            }
        }
    }

5.657 Beiträge seit 2006
vor 7 Jahren

Werde morgen mit Palins Tip mal was versuchen ^^.

Wie gesagt, damit kommst du nicht weit, wenn es sich um eine konkave Form handelt. Und wenn es sich um eine konvexe Form handelt, dann gibt es dafür bereits einen Algorithmus, den du auch in wenigen Codezeilen selbst umgesetzt hast.

Weeks of programming can save you hours of planning

G
Gimmick Themenstarter:in
154 Beiträge seit 2015
vor 7 Jahren

Und wenn es sich um eine konvexe Form handelt, dann gibt es dafür bereits einen Algorithmus, den du auch in wenigen Codezeilen selbst umgesetzt hast.

Das wirft halt im Prinzip erstmal alles durcheinander, aber mehrere Varianten im Vergleich sind wahrscheinlich für die Arbeit auch nicht schlecht.

Muss ich mal schauen wie sich das zeitlich noch ausgeht und wenn möglich dann testen und mal die Rechenzeiten vergleichen. Kann aber eine Weile dauern =)