Graham Scan Convex Hull 附加了太多的顶点

Question

如上所述，我正在尝试实现 Graham Scan Convex Hull 算法，但我遇到了堆栈附加太多顶点的问题。这些点是从 .dat 文件中读取的 here

阅读积分我的功能如下：

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

我的 graham 扫描如下：

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

当我运行它使用以前 50 行作为输入的数据集时，它会生成堆栈：

[(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)]

但它应该产生（按此顺序）：

[(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)]

有什么想法吗？

Answer 1

角度排序要针对某个极值参考点（比如最底下和最左边）进行，无疑是包含在凸包中的。但是您的实现使用列表的第一点作为参考。

维基摘录：

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

Graham Scan Convex Hull 附加了太多的顶点

Graham Scan Convex Hull appending too many vertices

python

algorithm

convex-hull

grahams-scan