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

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

Разберитесь в некоторых структурах данных, которые позволят вам быстро:

• получить список всех углов с заданной координатой 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