Graham Scan Convex Hull appending too many vertices

Question

As above I am trying to implement a Graham Scan Convex Hull algorithm but I am having trouble with the stack appending too many vertices. The points are read from a .dat file here

For reading points my function is as follows:

def readDataPts(filename, N):
    """Reads the first N lines of data from the input file
          and returns a list of N tuples
          [(x0,y0), (x1, y1), ...]
    """
    count = 0
    points = []
    listPts = open(filename,"r")
    lines = listPts.readlines()
    for line in lines:
        if count < N:
            point_list = line.split()
            count += 1
            for i in range(0,len(point_list)-1):
                points.append((float(point_list[i]),float(point_list[i+1])))

    return points

My graham scan is as follows:

def theta(pointA,pointB):
    dx = pointB[0] - pointA[0]
    dy = pointB[1] - pointA[1]
    if abs(dx) < 0.1**5 and abs(dy) < 0.1**5:
        t = 0
    else:
        t = dy/(abs(dx) + abs(dy))
    if dx < 0:
        t = 2 - t
    elif dy < 0:
        t = 4 + t
    return t*90



def grahamscan(listPts):
    """Returns the convex hull vertices computed using the
         Graham-scan algorithm as a list of 'h' tuples
         [(u0,v0), (u1,v1), ...]  

    """
    listPts.sort(key=lambda x: x[1]) 
    p0 = listPts[0]
    angles = []
    for each in listPts:
        angle = theta(p0,each)
        angles.append((angle,each))
    angles.sort(key=lambda angle: angle[0])
    stack = []
    for i in range(0,3):
        stack.append(angles[i][1])
    for i in range(3, len(angles)):
        while not (isCCW(stack[-2],stack[-1],angles[i][1])):
            stack.pop()
        stack.append(angles[i][1])
    merge_error = stack[-1]
    #stack.remove(merge_error)
    #stack.insert(0,merge_error)
    return stack #stack becomes track of convex hull

def lineFn(ptA, ptB, ptC):
    """Given three points, the function finds the value which could be used to determine which sides the third point lies"""
    val1 = (ptB[0]-ptA[0])*(ptC[1]-ptA[1])
    val2 = (ptB[1]-ptA[1])*(ptC[0]-ptA[0])
    ans = val1 - val2
    return ans 

def isCCW(ptA, ptB, ptC):
    """Return True if the third point is on the left side of the line from ptA to ptB and False otherwise"""    
    ans = lineFn(ptA, ptB, ptC) > 0
    return ans

When I run it using the data set taking the first 50 lines as input it produces the stack:

[(599.4, 400.8), (599.0, 514.4), (594.5, 583.9), (550.1, 598.5), (463.3, 597.2), (409.2, 572.5), (406.0, 425.9), (407.3, 410.2), (416.3, 405.3), (485.2, 400.9)]

but it should produce (in this order):

[(599.4, 400.8), (594.5, 583.9), (550.1, 598.5), (472.6, 596.1), (454.2, 589.4), (410.8, 564.2), (416.3, 405.3), (487.7, 401.5)]

Any ideas?

Answer 1

Angle sorting should be made against some extremal reference point (for example, the most bottom and left), that is undoubtedly included in convex hull. But your implementation uses the first point of list as reference.

Wiki excerpt:

swap points[1] with the point with the lowest y-coordinate