点のリストを時計回りに並べる

Question

私は問題に遭遇しましたが、解決方法はわかりません。

私はすべてのポイントがパスを形成するためにポイントのリストをソートしようとしています。私がこれまで行ってきたことは、リスト内のすべての点の中心点を計算した後、ソートが行われたthis postのコードを使用したことです。ここでは、コードスニペットを借りている。いくつかの例において

public int Compare(Point3D pointA, Point3D pointB) 
{ 
    if (pointA.X - CenterPoint.X >= 0 && pointB.X - CenterPoint.X < 0) 
     return 1; 
    if (pointA.X - CenterPoint.X < 0 && pointB.X - CenterPoint.X >= 0) 
     return -1; 

    if (pointA.X - CenterPoint.X == 0 && pointB.X - CenterPoint.X == 0) 
    { 
     if (pointA.Y - CenterPoint.Y >= 0 || pointB.Y - CenterPoint.Y >= 0) 
      if (pointA.Y > pointB.Y) 
       return 1; 
      else return -1; 
     if (pointB.Y > pointA.Y) 
      return 1; 
     else return -1; 
    } 

    // compute the cross product of vectors (CenterPoint -> a) x (CenterPoint -> b) 
    double det = (pointA.X - CenterPoint.X)*(pointB.Y - CenterPoint.Y) - 
        (pointB.X - CenterPoint.X)*(pointA.Y - CenterPoint.Y); 
    if (det < 0) 
     return 1; 
    if (det > 0) 
     return -1; 

    // points a and b are on the same line from the CenterPoint 
    // check which point is closer to the CenterPoint 
    double d1 = (pointA.X - CenterPoint.X)*(pointA.X - CenterPoint.X) + 
        (pointA.Y - CenterPoint.Y)*(pointA.Y - CenterPoint.Y); 
    double d2 = (pointB.X - CenterPoint.X)*(pointB.X - CenterPoint.X) + 
        (pointB.Y - CenterPoint.Y)*(pointB.Y - CenterPoint.Y); 
    if (d1 > d2) 
     return 1; 
    else return -1; 
} 

それが正常に動作しますが、時にはそれは驚異をうまくいく、添付の写真を参照してください、黒い点が計算された中心点：画像Aでは

すべてがOKですが、私は2本の水平線を構成する点を上に移動することにした場合、私はこれに実行します。

緑色の線はどのように見えるのですか、黒色の線は実際にどのように見えるのですか、なぜ私はそれがどういうものなのか理解できません。私もatan()のソリューションを試しましたが、同じ結果が出ました。どんな助けでも本当に感謝しています。

Answer 1

ポイントは両方の例で時計回りによくソートされています。しかし、2番目の例では、それは適切でない方法です。時計回りのアルゴリズムは、凸面図に対してのみ機能します。

ここには、サポートされていない図のサンプルがあり、利用可能な中心点はありません。あなたはいくつかの点セットを持っているし、それらをリンクする方法がわからない、とあなたは、元の姿を復元することはできません数字については何も知らないので、場合

。