我一直在尝试用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
计算极坐标:
^{pr2}$问题是代码似乎永远不会离开while循环,我不知道为什么。有人知道吗?在
谢谢。在
(是的,代码很劣质,我只是很快就拼凑起来了)
编辑:打印出的坐标似乎显示它们在两个坐标之间跳跃。在
根据http://en.wikipedia.org/wiki/Gift_wrapping_algorithm你需要这样做:
你说得对:
^{pr2}$还有这个:
但我不确定的是:
取而代之的是它与所有其他点所形成的角中最小的角。但是根据维基百科,你想要的是所有角度中最左边的角度。我有一些处理角度的代码:
arcdir
将告诉您某个角度是在另一个角度的左侧还是右侧,因此您可以使用它来查看某个角度是否更左,因此应该使用该角度。在如果您沿着这些点移动,总是选择最左边的角度到下一个点,您将围绕多边形的周长再次到达起点(因为您选择了最左边的点,您知道它必须在周长上,并且会再次到达)
相关问题 更多 >
编程相关推荐