Периметр вокруг двумерной сетки

Question

Учитывая 2D сетку квадратных ячеек формы grid[x,y], я хотел бы алгоритм, который производит упорядоченный набор точек, которые формируют периметр формы. Другими словами, алгоритм будет создавать маршрут по периметру вокруг углов фигуры, как показано на этом рисунке:

.

Я посмотрел на сообщения типа this (где я получил вышеупомянутое изображение), и я могу найти углы формы. У меня есть два вопроса: 1) как только я найду углы фигуры, как бы я перебрал их, чтобы найти правильный (и правильный) маршрут? 2) Будет ли такой метод, чтобы найти маршрут последовательно производить по часовой стрелке / против часовой стрелки? Для меня не имеет значения, что порядок вершин по часовой стрелке / против часовой стрелки, только то, что они последовательно по часовой стрелке или против часовой стрелки.

Спасибо за любую помощь

Answer 1

Предполагается, что любой отдельный угол не будет посещаться более одного раза за контур.другими словами, нет углов, где есть два серых и два черных с двумя серыми квадратами в несмежных углах.

Получите ваши углы в некоторых структурах данных, которые позволяют быстро:

• получить список всех углов с заданной координатой x, упорядоченной по координате y.
• получить список всех углов с заданной координатой y, упорядоченной по координате x.

Вот алгоритм:

Start with arbitrary corner c. 
        We'll say it has 3 adjacent black squares and 1 grey, and that the 
        1 grey square is in the -x,+y direction.

Choose perimeter direction. We'll say clockwise.

Determine which direction the perimeter goes in that corner. This can be done 
        by looking at the direction of the adjacent tile there's only 1 color of.

        In our example, the perimeter goes -x/+y

Determine if c is concave or convex. 
        Convex has 3 adjacent black squares, concave has 3 adjacent grey squares. 
        In our example, c is convex because it has 3 adjacent black squares.

Knowing the direction of the perimeter from that corner and if it's concave or 
        not tells us what direction is clockwise:

    clockwise at convex +x/-y is +x,
    clockwise at convex +x/+y is +y,
    clockwise at convex -x/-y is -y,
    clockwise at convex -x/+y is -x 

If it is concave clockwise goes the other direction.  

(obviously if the desired perimeter direction is counterclockwise, it's the opposite)

Because c in our example is a convex corner and it goes -x/+y, 
        that means clockwise is along the x wall, so set current_axis = x, 

It goes negative in that direction so set current_direction = -1
        Otherwise, it would be set to 1


create list ordered_corner_list that only contains c

While length of ordered_corner_list < number of corners:

    Get list of all corners with same value of current_axis as c ordered by the other axis. 
            e.g. for the first iteration, get same x value as c ordered by y

    if current_direction = -1:
        find node with the next lowest ordered value from c.
                e.g. for the first iter, get corner with next lowest x from c

    else:
        find node with the next highest ordered value from c

    assign that node to c
    append c to ordered_corner_list

    set current_axis = the other axis  
            e.g. for the first iteration, current_axis = y here

    set current_direction to the direction that corner goes in the current_axis