Quickhull點以正確的順序

Question

我採取了以下網頁上找到的快速船體代碼不返回：

http://www.ahristov.com/tutorial/geometry-games/convex-hull.html

的算法返回凸包的正確的點，但它沒有返回他們正確的三角函數。由於點沒有有意義的順序，因此我不能用它們來畫線，從而畫出船體本身。

例如，當我運行以下幾點

(2,5) (9,2) (1,8) (0,5) (3,3) 

正確的順序，我希望他們在返回的算法是：

(0,5) (1,8) (9,2) (3,3) 

取而代之的是快速船體算法返回他們是這樣的：

(1,8) (0,5) (3,3) (9,2) 

任何人都可以請幫我

Answer 1

如果無法修改算法以正確的順序返回它們，則可以計算返回點的centroid（將它們全部加起來除以計數，凸包的質心總是位於船體），然後計算從質心的角度以這樣的各點：

point.angle = atan2(point.y - centroid.y, point.x - centroid.x); 

然後排序基於所述角點的列表。

而且，你的C＃代碼不符合Java的這一部分：

// Recursively proceed with new sets 
    HullSplit(minPt, farthestPt, leftSetMinPt, ref hull); 
    HullSplit(maxPt, farthestPt, leftSetMaxPt, ref hull); 
    // should be: 
    // HullSplit(farthestPt, maxPt, leftSetMaxPt, ref hull); 

Java是：

hullSet(A,P,leftSetAP,hull); 
    hullSet(P,B,leftSetPB,hull); 

而且，你已經有效扭轉了你點到線測試的跡象相比於Java的：

public int pointLocation(Point A, Point B, Point P) { 
    int cp1 = (B.x-A.x)*(P.y-A.y) - (B.y-A.y)*(P.x-A.x); 
    return (cp1>0)?1:-1; 
} 

if (pointLocation(A,B,p) == -1) // tests for negative 
if (pointLocation(A,P,M)==1) { // tests for positive 
if (pointLocation(P,B,M)==1) { // tests for positive 

C＃：

private static bool IsAboveLine(Point a, Point b, Point pt) 
{ 
    var result = ((b.X - a.X) * (pt.Y - a.Y)) 
       -((b.Y - a.Y) * (pt.X - a.X)); 

    return (result > 0) ? true : false; 
} 

if (IsAboveLine(minPt, maxPt, pt)) // tests for positive 
if (!IsAboveLine(minPt, farthestPt, set.ElementAt(i))) // tests for negative 
if (!IsAboveLine(farthestPt, maxPt, set.ElementAt(i))) // tests for negative