如上所述，我正在尝试实现 Graham Scan Convex Hull 算法，但我遇到了堆栈附加太多顶点的问题。这些点是从此处的 .dat 文件中读取的
对于阅读点，我的功能如下：
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
我的格雷厄姆扫描如下：
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)]
有任何想法吗？