文章/答案/技术大牛

发布

社区首页 >问答首页 >如何用Python编写Graham算法？

问如何用Python编写Graham算法？
EN

Stack Overflow用户

提问于 2015-02-14 22:04:13

回答 1查看 556关注 0票数 1

我试图用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)

另一个函数对α的点列表(不包括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迭代)。我的节目怎么了？

python

algorithm

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-02-14 22:19:25

问题是while循环：

while isRight(pointsList[i-2], pointsList[i-1], pointsList[i]):
    pointsStack.pop()

因为您没有增加i，所以它会从堆栈中重复弹出，直到它是空的(甚至更远)。

你犯了一个语义错误。必须提供前两点的不是pointLists，而是堆栈。因此，每次您需要从堆栈中pop一个元素(将其保存在内存中)时，将第一点放在堆栈上，第二个是刚刚从堆栈中弹出的元素，最后一个是pointList[i]'th元素。如果您的堆栈被实现为一个列表，则可以使用：

while isRight(pointsList[pointsStack[-2]], pointsList[pointsStack[-1]], pointsList[i]):
        pointsStack.pop()

最后一个方面是，您需要将偏移点添加到pointList以及最后一点，这样在返回时，您可以选择用最大的alpha删除点。

还可以通过在点上使用isRight函数来优化排序函数，偏移点作为p1。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28520825

复制

相似问题

问如何用Python编写Graham算法？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何用Python编写Graham算法？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何用Python编写Graham算法？
EN