禮品包裝算法在Python從未終止

Question

我一直想在Python中實現禮品包裝算法，目前，我有以下代碼：

def createIslandPolygon(particleCoords): 

    startPoint = min(particleCoords.iteritems(),key = lambda x: x[1][1])[1] 

    check = 1 

    islandPolygon = [] 

    particleList = [] 

    for key in particleCoords: 

     particleList.append(particleCoords[key]) 

    currentPoint = startPoint 

    while(currentPoint != startPoint or check == 1): 

     islandPolygon.append(currentPoint) 

     check = 0 

     angleDict = {} 
     angleList = [] 

     for point in particleList: 

      if point != currentPoint: 

       angleDict[(angleBetweenTwoPoints(currentPoint, point))] = point 
       angleList.append(angleBetweenTwoPoints(currentPoint, point)) 

     smallestAngle = min(angleList) 

     currentPoint = angleDict[smallestAngle] 

    return islandPolygon 

，並計算極座標：

def angleBetweenTwoPoints(p1, p2): 

    p3 = (p1[0], p1[1] + 2) 

    a = (p1[0] - p2[0], p1[1] - p2[1]) 
    b = (p1[0] - p3[0], p1[1] - p3[1]) 

    theta = ((a[0]*b[0]) + (a[1]*b[1])) 
    theta = theta/(sqrt((a[0]*a[0]) + (a[1]*a[1])) * sqrt((b[0]*b[0]) + (b[1]*b[1]))) 
    theta = math.acos(theta) 

    return theta 

問題是，代碼似乎永遠不會離開while循環，我不知道爲什麼。有人有什麼主意嗎？

謝謝。

（是啊，漂亮以次充好的代碼，我只是把它扔一起快速）

編輯：打印出的座標似乎表明他們只是兩個座標之間跳躍。

Answer 1

根據http://en.wikipedia.org/wiki/Gift_wrapping_algorithm你需要這樣做：

pointOnHull = leftmost point in S 
    i = 0 
    repeat 
     P[i] = pointOnHull 
     endpoint = S[0]   // initial endpoint for a candidate edge on the hull 
     for j from 1 to |S|-1 
     if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) 
      endpoint = S[j] // found greater left turn, update endpoint 
     i = i+1 
     pointOnHull = endpoint 
    until endpoint == P[0]  // wrapped around to first hull point 

你有這個正確的：

pointOnHull = leftmost point in S 

而且這樣的：

P[i] = pointOnHull 

但這裏我不是部分當然有：

(S[j] is on left of line from P[i] to endpoint) 

相反，您會發現其所有角度中的最小角度爲。但根據維基百科，你想要的是最左邊的角度與所有其他點的角度。我有一些代碼與角度的工作：

def normalizeangle(radians): 
    return divmod(radians, math.pi*2)[1] 



def arclength(radians1, radians2 = 0): 
    radians1, radians2 = normalizeangle(radians1), normalizeangle(radians2) 
    return min(normalizeangle(radians1 - radians2), normalizeangle(radians2 - radians1)) 



def arcdir(radians1, radians2 = 0): 
    radians1, radians2 = normalizeangle(radians1), normalizeangle(radians2) 
    return cmp(normalizeangle(radians1 - radians2), normalizeangle(radians2 - radians1)) 

arcdir會告訴你，如果一個角上左邊或他人的權利，所以你可以用它來查看是否有角度更左等應使用。

如果沿着點總是選擇最左邊的角度移動到下一個點，那麼您將圍繞多邊形的邊界再次到達起點（因爲您選擇了最左邊的點，您知道它必須處於打開狀態周邊，將再次達到）