C++有向最近接ソート

Question

私のコードでは、ポイントのxyz座標を取得します。これは輪郭を形成するはずです。問題は、この点が正しい方法でソートされていないことです。座標を取得すると、x値とy値の上昇によってソートされます。したがって、最初にx値がソートされ、2つのポイントが同じx値を持つ場合、それらのy値によってソートされます。 z値は常に同じなので、無視することができます。 輪郭を形成するために点をソートするには、最近隣のアルゴリズムのバリエーションを使用します。 だからここにソートするために私のコードです：

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); 
    } 

} 

だから、これは立方体や円のように、標準の輪郭のために完璧に動作します。しかし、私はまた、これは動作しません輪郭を持っています。

は、私はすでに私のコードの考え方に問題が見つかりました： だからここで私は私が提供ソートコードを使用すると、私はこの結果を受け、ソートされていない輪郭

の絵です。輪郭は幅よりも実質的に長いので、ソートアルゴリズムも常に間違った場所の最も近い点になります。 だから、正しい絵は次のようになります。ここ

私のアプローチは、一点で始まる最も近い点を検索し、ポイントがくれた方向に従うことでした。私はこれをすべて手動で行いました。 今私の問題は、コードを最適化する方法がわからないため、ソート時の方向に従います。 誰かが私を助けてくれることを願っています。また、ソートされソートされた点を持つ.csvファイルを送信することもできます。

Answer 1

ここでは最後の反復時に間違ったデータ領域にアクセスしています：(it + 1)==matrix.end()その場合=>未定義の動作です。

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