订购正交多边形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):

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