CODEWITHSUNDEEP
algorithmmultidimensional-arraygeometry
rbjacob
rbjacob

Reputation: 333

Perimeter around a 2D grid-shape

Given a 2D grid of square cells of the form grid[x,y], I would like an algorithm that produces an ordered set of points that form the perimeter of the shape. In other words, the algorithm would produce a perimeter route around the corners of the shape as shown in this image:

.

I have looked at posts like this (where I got the above image), and I can find the corners of the shape. I have two questions: 1) once I have found the corners of the shape, how would I iterate over them in order to find a correct (and valid) route? 2) Would such a method to find the route consistently produce clockwise/counterclockwise routes? It does not matter to me that order of the vertices is clockwise/counterclockwise, only that they are consistently either clockwise or counterclockwise.

Thanks for any help

Upvotes: 3

Views: 1820

Answers (1)

Ruzihm
Ruzihm

Reputation: 20249

This assumes that any single corner won't be visited more than once per circuit. in other words, no corners where there are two grey and two black with the two grey squares in non adjacent corners.enter image description here

Get your corners in some data structures that let you quickly :

  • get a list of all corners with a given x coordinate ordered by y coordinate.
  • get a list of all corners with a given y coordinate ordered by x coordinate.

Here's the algorithm:

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

Upvotes: 4

Related Questions