C++ gerichtete Nächste Nachbarsortierung

Question

Also in meinem Code bekomme ich die xyz-Koordinaten von Punkten, die eine Kontur bilden sollten. Das Problem ist, dass diese Punkte nicht korrekt sortiert sind. Wenn ich die Koordinaten bekomme, werden sie nach steigenden x- und y-Werten sortiert. Zuerst werden die x-Werte sortiert, und wenn zwei Punkte denselben x-Wert haben, werden sie nach ihrem y-Wert sortiert. Der z-Wert ist immer gleich und kann daher ignoriert werden. Um die Punkte zu sortieren, um die Kontur zu bilden, verwende ich eine Variation des nächsten Nachbaralgorithmus. hier ist also mein Code für die Sortierung:

double squareDistancePoints(const std::array<double, 3>& a, const std::array<double, 3>& b) 
{ 
    assert(a.size() == b.size()); 
    double sum = 0; 
    for(size_t i = 0; i < a.size(); ++i) 
     sum += pow(b[i]-a[i], 2); 
    return sum; 
} 


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

    double bestSquareDistance = DBL_MAX; 

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

} 

Also das perfekt für Standardkonturen funktioniert, wie ein Würfel oder einem Kreis. Aber ich habe auch Konturen, wo das nicht funktioniert. Also hier ist ein Bild von einer unsortierten Kontur

Wenn ich den Sortiercode verwende ich zur Verfügung gestellt ich dieses Ergebnis erhalten:

Ich fand das Problem schon in der Idee von meinem Code. Die Kontur ist wesentlich länger als breit, daher ist der Sortieralgorithmus auch immer der nächste Punkt am falschen Ort. Also das richtige Bild würde wie folgt aussehen:

Mein Ansatz war hier mit einem Punkt zu beginnen, für den nächsten Punkt suchen und die die Richtung der Punkte gaben mir folgen. Ich habe das alles manuell gemacht. Also mein Problem ist jetzt, ich weiß nicht, wie ich meinen Code optimieren soll, damit er beim Sortieren eine Richtung einhält. Ich hoffe, dass mir jemand helfen kann. Ich könnte auch eine CSV-Datei mit den unsortierten und sortierten Punkten senden, wenn das helfen würde.

Answer 1

Sie greifen hier auf den falschen Datenbereich zu, wenn es in der letzten Iteration ist: (it + 1)==matrix.end() in diesem Fall => undefined Verhalten.

for(auto it = matrix.begin(); it != matrix.end(); ++it) 
{ 
    ... 
    if(bestIt != matrix.end()) 
    { 
     std::swap(*(it + 1), *bestIt); 
    }