如何訂購正交多邊形點列表？例如，我有一個正交多邊形點列表data = [(2, 0), (5, 0), (5, 7), (4, 7), (4, 5), (3, 5),(3, 3), (2, 3), (2, 2), (3, 2), (3, 7), (2, 7)]不順。我想以這樣的逆時針方式訂購它：out = [(2,0),(5,0),(5,7),(4,7),(4,5),(3,5),(3,7),(2,7),(2,3),(3,3),(3,2),(2,2)]我已經(jīng)嘗試使用deflate _hull但它不正確。有什么算法可以解決這個問題嗎？我明白了：但預(yù)期：
1 回答
SMILET
TA貢獻1796條經(jīng)驗 獲得超4個贊
您可以使用以下遞歸函數(shù)：
def sort_ortho_poly(points, current=None, start=None, go_x=True):
# initialize the starting point at the bottom left, which should have the least sum of x and y
if not current:
start = current = min(points, key=sum)
# if we're going x-wards, v would be the y index (1), h would be the x index (0), and vice versa
v, h = go_x, not go_x
# remove the current point from the list of points so the next recursion would be processing the remaining points
remaining = points[:]
remaining.remove(current)
# if there is no more remaining point
if not remaining:
# we've found a path if we are able to connect back to the starting point, or else we don't
return [current] if start[v] == current[v] else []
# try each point in the remaining points that goes in the right direction from the current point
for next in [p for p in remaining if p[v] == current[v]]:
# recursively find a valid path from the remaining points after flipping the direction
path = sort_ortho_poly(remaining, next, start, not go_x)
# if we get a path that does go back to the starting point, we have to make sure the path is valid
if path:
# the current edge (e1, e2)
e1, e2 = current, next
# make sure e1 is lower than or left of e2
if e1[h] > e2[h]:
e1, e2 = e2, e1
# for each edge (p1, p2) in the path, including the final edge connecting to the starting point
for p1, p2 in zip(path, path[1:] + [start]):
# make sure p1 is lower than or left of p2
if p1[0] == p2[0] and p1[1] > p2[1] or p1[1] == p2[1] and p1[0] > p2[0]:
p1, p2 = p2, p1
# if the edge is in the same line as the current edge
if p1[v] == p2[v] == e1[v]:
# make sure the two edges don't overlap
if e1[h] < p1[h] < e2[h] or e1[h] < p2[h] < e2[h] or p1[h] < e1[h] < p2[h] or p1[h] < e2[h] < p2[h]:
break
# if the edge is perpendicular to the current edge, make sure they don't cross over
elif p1[h] == p2[h] and e1[h] < p1[h] < e2[h] and p1[v] < e1[v] < p2[v]:
break
else:
# the path is valid! we append the path to the current point and return
return [current, *path]
# return empty if it's a dead end
return []
以便：
data = [(2, 0), (5, 0), (5, 7), (4, 7), (4, 5), (3, 5),(3, 3), (2, 3), (2, 2), (3, 2), (3, 7), (2, 7)]
print(sort_ortho_poly(data))
會輸出：
[(2, 0), (5, 0), (5, 7), (4, 7), (4, 5), (3, 5), (3, 7), (2, 7), (2, 3), (3, 3), (3, 2), (2, 2)]
添加回答
舉報
0/150
提交
取消