排序頂點順時針

我使用該算法排序點順時針列表：排序頂點順時針

private List<Point2D> SortClockWise(List<Point2D> Points) { 
    // First Calculate Center of Points 
    double CenterX = 0; 
    double CenterY = 0; 
    for (int i = 0; i < Points.size(); i++) { 
     CenterX += Points.get(i).getX(); 
     CenterY += Points.get(i).getY(); 
    } 
    Point2D Center = new Point2D(CenterX/Points.size(), CenterY 
      /Points.size()); 
    int n = Points.size(); 
    int k; 
    for (int m = n; m >= 0; m--) { 
     for (int i = 0; i < n - 1; i++) { 
      k = i + 1; 
      if (!less(Points.get(i), Points.get(k), Center)) { 
       Point2D tmp = new Point2D(); 
       tmp = Points.get(i); 
       Points.set(i, Points.get(k)); 
       Points.set(k, tmp); 
      } 
     } 
    } 
    for (int i = 0; i < Points.size(); i++) { 
     mTempShape.add(Points.get(i)); 
    } 
    return mTempShape; 
} 

private Boolean less(Point2D a, Point2D b, Point2D center) { 
    if (a.getX() - center.getX() >= 0 && b.getX() - center.getX() < 0) 
     return true; 
    if (a.getX() - center.getX() < 0 && b.getX() - center.getX() >= 0) 
     return false; 
    if (a.getX() - center.getX() == 0 && b.getX() - center.getX() == 0) { 
     if (a.getY() - center.getY() >= 0 || b.getY() - center.getY() >= 0) 
      return (a.getY() > b.getY()); 
     return b.getY() > a.getY(); 
    } 

    // compute the cross product of vectors (center -> a) x (center -> b) 
    double det = (a.getX() - center.getX()) * (b.getY() - center.getY()) 
      - (b.getX() - center.getX()) * (a.getY() - center.getY()); 
    if (det < 0) 
     return true; 
    if (det > 0) 
     return false; 

    // points a and b are on the same line from the center 
    // check which point is closer to the center 
    double d1 = (a.getX() - center.getX()) * (a.getX() - center.getX()) 
      + (a.getY() - center.getY()) * (a.getY() - center.getY()); 
    double d2 = (b.getX() - center.getX()) * (b.getX() - center.getX()) 
      + (b.getY() - center.getY()) * (b.getY() - center.getY()); 
    return d1 > d2; 
}

問題是在一些情況下，像這樣：

算法給我的黑線畫在圖片中，但是我想要得到的是圖片中的編號頂點。

來源

2016-03-27 Alireza.pir

黑線看起來像對我來說正確的預期行爲。點順時針排列成一個圓圈（或至少儘可能接近）。我看到它能夠得到你想要的東西的唯一方法就是如果'Center'是7-3-6三角形中間的某個點。但是，這只是在這種情況下 - 我認爲對於其他形狀，沒有'中心'可以工作。所以你可能需要一個完全不同的，更先進的算法，它知道點的角色作爲形狀的頂點，而不僅僅是位置。目前的形狀如何？ –

您的中心位於點3（同一x座標）上方的某處。這使得該中心的排序正確。 – fabian

是的排序是正確的這個算法，但我想知道如何我可以得到我想要的結果 –

我會嘗試一種方法，首先將所有元素分解爲多邊形。從第1點開始，然後穿過多邊形中的頂點，直到到達共享的頂點。然後你必須改變多邊形。畢竟，如果你只有點，沒有定義邊（隱式或顯式），你只能有一個凸形。

來源

2016-03-27 11:51:17 Mao

排序頂點順時針

回答

相關問題