0

私は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 ループを離れないように見えることです。その理由はわかりません。誰にもアイデアはありますか？

ありがとう。

（ええ、コードはかなり粗雑です。すぐにまとめただけです）

編集：座標を印刷すると、2つの座標間でジャンプしているように見えます。

4

1 に答える 1

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角度が別の角度の左側にあるか右側にあるかを示します。これを使用して、角度がさらに左側にあるかどうかを確認できるため、使用する必要があります。

常に左端の角度を選択して次のポイントまでポイントに沿って移動すると、ポリゴンの周囲を回って再び最初に到達します（左端のポイントを選択したので、それが境界上にある必要があることがわかります。再び到達する）

于 2013-03-12T23:08:57.033 に答える