我试图用Python编写Graham算法（凸包）。我有一些生成随机点的函数：
def generatePoints(n):
global pointsList
for x in range(0, n):
rPoint = Point(random.randint(-10, 10), random.randint(-10, 10))
if(rPoint not in pointsList):
pointsList.append(rPoint)
那么我有一个函数可以找到Y值最低的点：
def findStartingPoint():
global startingPoint
global pointsList
for pt in pointsList:
if(pt.y < startingPoint.y):
startingPoint = pt
elif(pt.y == startingPoint.y):
if(pt.x < startingPoint.x):
startingPoint = pt
for pt in pointsList:
if(startingPoint == pt):
pointsList.remove(pt)
另一个函数对alpha的点列表（不包括startingPoint）进行排序（根据startingPoint的角度），如果两者具有相同的alpha，则还会对点的X值进行排序。它还将排序前的（0,0）-> startingPoint向量的所有点移动，并在排序后将它们移回到其先前的状态：
def sortPoints():
global startingPoint
global pointsList
moveX = startingPoint.x
moveY = startingPoint.y
for pt in pointsList:
pt.x = pt.x - moveX
pt.y = pt.y - moveY
d = math.fabs(pt.x) + math.fabs(pt.y)
if(pt.x >= 0 and pt.y >= 0):
pt.alfa = pt.y / d
elif(pt.x < 0 and pt.y >= 0):
pt.alfa = 2 - (pt.y / d)
elif(pt.x < 0 and pt.y < 0):
pt.alfa = 2 + (math.fabs(pt.y) / d)
elif(pt.x >= 0 and pt.y < 0):
pt.alfa = 4 - (math.fabs(pt.y) / d)
pointsList = sorted(pointsList, key=attrgetter('alfa', 'x'))
for pt in pointsList:
pt.x = pt.x + moveX
pt.y = pt.y + moveY
所以现在我有了startingPoint和点的排序列表。我还有一个函数检查下一个点是在连接两个先前点的线的右边还是左边（如算法所示）：
def isRight(p1, p2, p3):
vecA = [(p2.x - p1.x), (p2.y - p1.y)]
print "vecA: " + str(vecA[0]) + " " + str(vecA[1])
vecB = [(p3.x - p1.x), (p3.y - p1.y)]
print "vecB: " + str(vecB[0]) + " " + str(vecB[1])
ilo = vecA[0] * vecB[1] - vecA[1] * vecB[0]
if(ilo > 0):
return True
else:
return False
问题来了。我的算法功能如下所示：
def graham():
global pointsStack
global pointsList
pointsStack.push(0)
pointsStack.push(1)
pointsStack.push(2)
for i in range(3, len(pointsList)):
while isRight(pointsList[i-2], pointsList[i-1], pointsList[i]):
pointsStack.pop()
pointsStack.push(i)
它只适用于“堆栈为空异常”（有时适用于1迭代）。我的程序有什么问题？
问题是while循环：
while isRight(pointsList[i-2], pointsList[i-1], pointsList[i]):
pointsStack.pop()
由于您不增加i，它将重复从堆栈中弹出，直到其为空（或超出）为止。
您犯了一个语义错误。不是pointLists必须提供前两点的是堆栈。结果，每次您需要pop从堆栈中保留一个元素（将其保留在内存中）时，peek堆栈就指向第一个点，第二个是刚从堆栈中弹出的元素，最后一个是pointList[i]第一个元素。如果将堆栈实现为列表，则可以使用：
while isRight(pointsList[pointsStack[-2]], pointsList[pointsStack[-1]], pointsList[i]):
pointsStack.pop()
最后一个方面是，您需要向pointList以及最后一个点添加偏移点，以便在返回时可以选择删除具有最大alpha值的点。
您还可以通过isRight在偏移点为的点上使用该函数来优化排序功能p1。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句