订购正交多边形python

Question

如何订购正交多边形点列表？

例如，我有一个正交多边形点列表

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

我已经尝试使用deflate _hull但它不正确。有什么算法可以解决这个问题吗？

我明白了：

但预期：

Answer 1

您可以使用以下递归函数：def sort_ortho_poly(points, current=None, start=None, go_x=True):&nbsp; &nbsp; # initialize the starting point at the bottom left, which should have the least sum of x and y&nbsp; &nbsp; if not current:&nbsp; &nbsp; &nbsp; &nbsp; start = current = min(points, key=sum)&nbsp; &nbsp; # if we're going x-wards, v would be the y index (1), h would be the x index (0), and vice versa&nbsp;&nbsp; &nbsp; v, h = go_x, not go_x&nbsp; &nbsp; # remove the current point from the list of points so the next recursion would be processing the remaining points&nbsp; &nbsp; remaining = points[:]&nbsp; &nbsp; remaining.remove(current)&nbsp; &nbsp; # if there is no more remaining point&nbsp; &nbsp; if not remaining:&nbsp; &nbsp; &nbsp; &nbsp; # we've found a path if we are able to connect back to the starting point, or else we don't&nbsp; &nbsp; &nbsp; &nbsp; return [current] if start[v] == current[v] else []&nbsp; &nbsp; # try each point in the remaining points that goes in the right direction from the current point&nbsp; &nbsp; for next in [p for p in remaining if p[v] == current[v]]:&nbsp; &nbsp; &nbsp; &nbsp; # recursively find a valid path from the remaining points after flipping the direction&nbsp; &nbsp; &nbsp; &nbsp; path = sort_ortho_poly(remaining, next, start, not go_x)&nbsp; &nbsp; &nbsp; &nbsp; # if we get a path that does go back to the starting point, we have to make sure the path is valid&nbsp; &nbsp; &nbsp; &nbsp; if path:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # the current edge (e1, e2)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; e1, e2 = current, next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # make sure e1 is lower than or left of e2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if e1[h] > e2[h]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; e1, e2 = e2, e1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # for each edge (p1, p2) in the path, including the final edge connecting to the starting point&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for p1, p2 in zip(path, path[1:] + [start]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # make sure p1 is lower than or left of p2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if p1[0] == p2[0] and p1[1] > p2[1] or p1[1] == p2[1] and p1[0] > p2[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p1, p2 = p2, p1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # if the edge is in the same line as the current edge&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if p1[v] == p2[v] == e1[v]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # make sure the two edges don't overlap&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 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]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # if the edge is perpendicular to the current edge, make sure they don't cross over&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif p1[h] == p2[h] and e1[h] < p1[h] < e2[h] and p1[v] < e1[v] < p2[v]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # the path is valid! we append the path to the current point and return&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return [current, *path]&nbsp; &nbsp; # return empty if it's a dead end&nbsp; &nbsp; 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)]