Sortierung eines Vektors um eine geometrischen Kontur zu erzeugen

bekinect

Hallo allezusammen

Ich hab ein kleines Problem bei einem Nearest-Neigbor-Algorithmus. Ich habe in einem Vektor, in dem ich die Koordinaten von Punkten gespeichert hab. Dieser Vektor soll nun so sortiert werden, dass die Punkte wieder eine geometrische Kontur formen. Das Problem ist, dass es zwar bei einer Kugel oder einem Würfel gut funktioniert, bei konplexeren Figuren aber komplet versagt. Da ich leider nicht weiß ob und wie man Bilder hier hochlädt, hab ich einmal ein Codebeispiel geschrieben. Den Code hab ich hier.
http://www.tutorialspoint.com/compile_cpp11_online.php?PID=0Bw_CjBb95KQMVHZEZHBzdWFtUkk

Die Funktion in der das Problem liegt ist der folgende Codeabschnitt:

for(auto it = matrix_cube.begin(); it != matrix_cube.end(); ++it)
{
  auto bestIt = matrix_cube.end();

  double bestSquareDistance = DBL_MAX;

  for(auto nextIt = it + 1; nextIt != matrix_cube.end(); ++nextIt)
  {
    const auto squareDistance = squareDistancePoints(*it, *nextIt);
    if( squareDistance < bestSquareDistance)
    {
      bestSquareDistance = squareDistance;
      bestIt = nextIt;
    }
  }
  if(bestIt != matrix_cube.end())
  {
    std::swap(*(it + 1), *bestIt);
  }
}

Dieser Code soll den Vektor so sortieren, dass ausgehend von dem ersten Element das am nächsten liegende Element gesucht wird. Ist es gefunden tauschen das zweite und das gefundene Element die Plätze. Eigentlich funktioniert diese Funktion komplett richtig, mein Problem ist aber, das ich die Sortierung bei Konturen, bei denen die Punkte weit auseinander liegen in eine bestimmte Richtung lotsen müsste. In dem Codebeispiel von mir ist eine sehr lange und dünne Figur beschrieben. Die Funktion hupft dabei immer von einer Seite zur anderen und der Vektor wird nicht richtig sortiert.
Kann mir vielleicht jemand einen Tipp geben, wie ich die Sortierung verbessern könnte?

Gruß
Bernhard

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Mathematik und Physik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Werner Salomon

Hallo Bernhard,

spontaner Gedanke: Stelle zunächst eine zweite Punkteliste auf, die die konvexe Hülle enthält (s. https://de.wikipedia.org/wiki/Graham_Scan). Falls die geometrische Kontur selbst bereits konvex ist, so ist die konvexe Hülle bereits die Lösung. Wenn Du jetzt zur Sortierung der Original-Punkte schreitest, so sortierst Du die fehlenden Punkte so ein, dass sie jeweils vom aktuellen Punkt aus gesehen 'in Richtung' der konvexen Hülle liegen. Z.B. indem Du nicht den Punkt mit dem geringsten Abstand, sondern den mit dem größten Skalarprodukt mit dem Richtunsvektor Richtung der konvexen Hülle nimmst.

Funktioniert aber zunächst nur in 2D - evt. hilft es nur die Projektion der Punkte auf eine Ebene zu betrachten.
IMHO ist das Problem für 3D gar nicht eindeutig lösbar.

Gruß
Werner

bekinect

Hallo Werner

Danke für den Tipp. Nur kurz um es für mich genauer zu erklären. Du schlägst vor, zunächst einen Graham Scan durchzuführen, um die konvexe Hülle zu finden. Die Konvexe Hülle wird in einem zweiten Vektor gespeichert. Anschließend vergleiche ich die beiden Vektoren. Sind die Größen des unsortierten und des nach Graham sortierten Vektors gleich groß, ist die Kontur gleich der konvexen Hülle. Wenn der unsortierte Vektor größer ist, lösche ich beispielsweise die Punkte aus dem unsortierten Vektor, die in der konvexen Hülle sind.
Das Vorgehen mit dem Skalarprodukt ist mir hier aber nicht ganz klar. Wie kann ich damit entscheiden wo ich den Punkt einsortieren soll.

Bezüglich deiner Anmerkung: Ich arbeite immer nur im 2D. Ich habe zwar mehrere Ebenen (mit steigender z-Koordinate), die Punkte sortiere ich aber immer nur in einer Ebene. Also zuerst alle Punkte mit z=0, dann mit z=1, usw. Ich mache also aus einem 3d Problem, viele 2D Probleme, da die wie du richtig sagst einfacher zu lösen sind.

lg
Bernhard

Werner Salomon

Hallo Bernhard,

bekinect schrieb:

Danke für den Tipp. Nur kurz um es für mich genauer zu erklären. Du schlägst vor, zunächst einen Graham Scan durchzuführen, um die konvexe Hülle zu finden. Die Konvexe Hülle wird in einem zweiten Vektor gespeichert. Anschließend vergleiche ich die beiden Vektoren. Sind die Größen des unsortierten und des nach Graham sortierten Vektors gleich groß, ist die Kontur gleich der konvexen Hülle. Wenn der unsortierte Vektor größer ist, lösche ich beispielsweise die Punkte aus dem unsortierten Vektor, die in der konvexen Hülle sind.

ja - genau so.

Jetzt beginnst Du beim ersten Punkt aus der konvexen Hülle $p_{i}$ und vergleichst den folgenden Punkt $p_{i+1}$ und jeden Punkt $q_j$ aus der verbleibenden unsortierten Menge jeweils paarweise. Du suchst also einen Punkt $q_j$ , der besser als nächster Punkt von $p_i$ geeignet ist, als $p_{i+1}$ selbst. Falls keiner gefunden wird, bleibt $p_{i+1}$ der nächste Punkt und das Spiel geht bei $p_{i+1}$ und $p_{i+2}$ weiter. Findest Du einen, so wird der Punkt zwischen $p_i$ und $p_{i+1}$ einsortiert, und der neue Punkt wird zum aktuellen Punkt.

Als Vergleichsfunktion kannst Du z.B. den Abstand von $p_i$ und das Skalarprodukt $(q\_j-p\_i)(p_{i+1}-p_i)$ berechnen und aus letzterem wiederum den Winkel, den der Weg nach $q_j$ von dem Weg nach $p_{i+1}$ abweicht. Ist der Abstand nach $q_j$ kleiner als der nach $p_{i+1}$ ist das gut; ist aber der Winkel zu groß, ist es wiederum schlecht. Gewichte beides und vergleiche.

Gruß
Werner