凸凸 - 確定點的順序

Question

因此，我正在學習凸凸Hull算法，並將所有算法從天真的Bruteforce寫入Graham Scan。

這是我的Bruteforce O（n^4）算法。在開始時，假設所有的點都是船體的一部分。對於每個可能的三角形，消除三角形內的所有點。在最後，那些未被消除的點將成爲船體的一部分。

這裏的Java代碼（FIXED：隨着Thomash的解決方案）

public List<Point> naive(List<Point> points) { 
    if (points == null) 
     return Collections.emptyList(); 
    if (points.size() <= 3) 
     return points; 
    boolean[] extremePoints = new boolean[points.size()]; 
    Arrays.fill(extremePoints, true); 
    for (int i = 0, sz = points.size(); i < sz; i++) { 
     if (extremePoints[i]) 
      for (int j = 0; j < sz; j++) { 
       if (i != j && extremePoints[j]) { 
        for (int k = 0; k < sz; k++) { 
         if (k != i && k != j) { 
          for (int l = 0; l < sz; l++) { 
           if (extremePoints[l] && l != i && l != j 
             && l != k) { 
            // Check if P[l] lies in triangle formed 
            // by 
            // P[i],P[j],P[k] 

            Polygon p = new Polygon(); 
            p.addPoint(points.get(i).x, 
              points.get(i).y); 
            p.addPoint(points.get(j).x, 
              points.get(j).y); 
            p.addPoint(points.get(k).x, 
              points.get(k).y); 
            if (p.contains(points.get(l))) 
             extremePoints[l] = false; 
           } 
          } 
         } 
        } 
       } 
      } 
    } 

    Point centerOfHull = null; // Arbitrary point inside the hull 
    // Order? 
    for (int i = 0; i < extremePoints.length; i++) { 
     if (!extremePoints[i]) { 
      centerOfHull = points.get(i); 
      break; 
     } 
    } 
    List<Point> convexHull = new ArrayList<Point>(); 
    for (int i = 0; i < extremePoints.length; i++) { 
     if (extremePoints[i]) { 
      convexHull.add(points.get(i)); 
     } 
    } 
    Collections.sort(convexHull, new PointComp(centerOfHull)); 
    // or use a heap. still O(nlogn) 
    return convexHull; 
} 

private class PointComp implements Comparator<Point> { 

    private Point center; 

    public PointComp(Point center) { 
     this.center = center; 
    } 

    @Override 
    public int compare(Point o1, Point o2) { 
     double angle1 = Math.atan2(o1.y - center.y, o1.x - center.x); 
     double angle2 = Math.atan2(o2.y - center.y, o2.x - center.x); 
     if (angle1 < angle2) 
      return 1; 
     else if (angle2 > angle1) 
      return -1; 
     return 0; 
    } 
} 

我試圖在視覺上看到這些點，他們似乎是正確的，但我不知道如何建立點的順序繪製凸包多邊形？任何幫助表示讚賞。

Answer 1

選擇凸包內O點和另一點A.對於凸包中的每個B，計算角度AθB並使用這些角度對點進行分類（如果A∩B<AÔB'則我們認爲B < B'）。

Answer 2

如果你正在暴力破解找到這點是船體的一部分，你還不如繼續做醜陋的東西，找到點的順序。

1. 開始左上角點。
2. 計算從該點到所有其他點的角度。
3. 選取角度最接近0度的點。這是船體順時針方向的下一個點。
4. 沖洗，起泡，重複。

你必須爲你去船體周圍的調整目標的角度，但這個工程（而且這是你寫在紙上的一種方式。）