python - 如何用 Python 编写格雷厄姆算法？

Question

我正在尝试用 Python 编写格雷厄姆算法(凸包)。我有一些生成随机点的函数:

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-for 迭代)。我的程序有什么问题？

Answer 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 的点。

您还可以通过在偏移点为 p1 的点上使用 isRight 函数来优化排序功能。