How to write Graham Algorithm in Python?

Question

I am trying to write Graham algorithm (convex hull) in Python. I have some function generating random points:

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)

then I have a function which finds the point with lowest Y value:

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)

another function sorts the list of points (excluding startingPoint) for alpha (angle according to startingPoint) and if both has same alpha it also sorts for X value of the point. It also moves all the points for (0,0) -> startingPoint vector before sort and moves them back to their previous state after sort:

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

So now I have startingPoint and sorted list of points. I also have a function checking whether next point is on the right or on the left of the line which connects 2 previous points (as the algorithm says):

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

Here comes the problem. My algorithm function looks like this:

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)

It just goes for "stack is empty exception" (sometimes it works for 1-for iteration). What is wrong with my program?

willeM_ Van Onsem · Accepted Answer · 2015-02-14 22:35:11Z

The problem is the while loop:

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

Since you don't increment the i, it will repeat popping from the stack until it is empty (and beyond).

You made a semantical error. It's not the pointLists that must provide the first two points, but the stack. As a result each time you need to pop one element from the stack (keep it in memory), peek the stack for the first point, the second is the element just popped from the stack and the last is the pointList[i]'th one. In case your stack is implemented as a list, you can thus use:

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

A final aspect is that you need to add the offset point to the pointList as well as the last point so that when you return, you can optionally remove the point with the largest alpha.

You can also optimize your sorting function by using the isRight function on the points with the offset point as p1.

Collectives™ on Stack Overflow

How to write Graham Algorithm in Python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related