Polygon from a grid of squares

Question

I'm looking for an algorithm to find the polygon that surrounds a contiguous grid of squares without holes as shown here:

.

I already have each of the grid squares storing data about the kind of edges with the surrounding area that they are composed of (i.e. top, top-right, top-bottom, no edges, etc.), so I'm thinking that this data could be utilized by the algorithm. If someone could provide some pseudocode for such an algorithm that would also be great.

The input to the algorithm would be a list of data objects, each with a Vector2Int describing the grid positions (note that these are simply positions within a grid, not vertices) as well as an Enum that gives the type of edges that the square has with the surrounding area. The output would be an ordered list of Vector2s describing the vertices of the surrounding polygon, assuming that each grid square is one unit in size.

I have found a similar question in the link below, but I wanted some elaboration on the kind of algorithm that would be specific to my case, especially given the data that I already have stored about the edges. I'd also prefer the algorithm to avoid calculating each of the squares' vertices and running a bunch of straightforward searches to eliminate the shared ones, as I feel that this might be too computationally expensive for my particular application. I just have a suspicion that there has to be a better way.

Outline (circumference) polygon extraction from geometry constructed from equal squares

EDIT: Now I'm beginning to think that some sort of maze walking algorithm might actually be appropriate for my situation. I'm working on a solution that I think will work, but it's very cumbersome to write (involving a tonne of conditional checks against the square edges and the direction of travel around the circumference) and probably isn't as fast as it could be.

Ciapha

I don't understand what you're looking for at all. Could you post example input and output? (Are you operating on actual images?) – Biondo

I'm not operating on images. I'm operating on grid positions given by Vector2Ints. I've updated my question, so hopefully what I'm asking is clearer. – Ciapha

What do you mean by you have the kind of edges the squares are composed of? Aren't squares always composed of four edges? Do you mean that you already filtered out inner edges? Then all you need to do is start at an arbitrary edge and walk along the outline (continue to the edge that has the same start vertex as the current edge's end vertex). – Submissive

@NicoSchertler I mean the edges that are exposed to the surrounding area. The top right square in my example image would have an enum of top-left-bottom, for example. Squares with no exposed edges have an enum designating this, so yes, you could say that I've filtered out the inner edges. If what it takes is to walk along the outline, then I'd appreciate an outline of the algorithm that would accomplish this. I have tried writing such an algorithm but have run into some complications. – Ciapha

@NicoSchertler I should have said that I've filtered out SOME of the inner edges (just those of the squares that are not exposed to the outside at all, except perhaps in the corners). I have yet to calculate the actual vertices of the squares. My inputs are merely grid positions such as (0, 1), (0, 2), (0, 3) which would form a line of three squares in the grid. – Ciapha

Extremely close to this post. Accepted answer propose an algorithm with average O(N) time (N: number of squares) provided map/dictionaries with average amorted O(1) time for insertion/deletion/lookup (ex: hashtables). Ordering the edges can be done in average O(M) time (M number of edges in the output) with a map. It might be possible to do better, but I suggest you try this (simple) algorithm first, and start worrying about optimization if you do meet performance issues. – Euclid

Answer 1

Came across this post looking for alternatives to my solution. This is what I came up with:

For a cell:

     |             |
---(0, 0)--------(1, 0)---
     |             |
     |             |
     |    R0C0     |
     |             |
     |             |
---(0, 1)--------(1, 1)---
     |             |

Calculate the borders of each cell as a set of 2 of its corner coordinates:

• top: ((c, r), (c, r + 1))
• right: ((c, r + 1), (c + 1, r + 1))
• bottom: ((c + 1, r + 1), (c + 1, r))
• left: ((c + 1, r), (c, r))

Notice how these defined clock-wise, this is important

So for the grid

R0C0 R0C1 R0C2 R0C3
          R1C2 R1C3
     R2C1 R2C2

you'd get the following edges:

R0C0 (top, bottom, left): (0, 0)-(1, 0), (1, 1)-(0, 1), (0, 1)-(0, 0)
R0C1 (top, bottom): (1, 0)-(2, 0), (2, 1)-(1, 1)
R0C2 (top): (2, 0)-(3, 0)
R0C3 (top, right): (3, 0)-(4, 0), (4, 0)-(4, 1)
R1C2 (left): (2, 2)-(2, 1)
R1C3 (right, bottom): (4, 1)-(4, 2), (4, 2)-(3, 2)
R2C1 (top, bottom, left): (1, 2)-(2, 2), (2, 3)-(1, 3), (1, 3)-(1, 2)
R2C2 (right, bottom): (3, 2)-(3, 3), (3, 3)-(2, 3)

Now it's a question of ordering these in a way that the first coordinate of of one element is the same as second coordinate of its predecessor.

(0, 0)-(1, 0)          (0, 0)-(1, 0)
(1, 1)-(0, 1)          (1, 0)-(2, 0)
(0, 1)-(0, 0)          (2, 0)-(3, 0)
(1, 0)-(2, 0)          (3, 0)-(4, 0)
(2, 1)-(1, 1)          (4, 0)-(4, 1)
(2, 0)-(3, 0)          (4, 1)-(4, 2)
(3, 0)-(4, 0)          (4, 2)-(3, 2)
(4, 0)-(4, 1)    =>    (3, 2)-(3, 3)
(2, 2)-(2, 1)          (3, 3)-(2, 3)
(4, 1)-(4, 2)          (2, 3)-(1, 3)
(4, 2)-(3, 2)          (1, 3)-(1, 2)
(1, 2)-(2, 2)          (1, 2)-(2, 2)
(2, 3)-(1, 3)          (2, 2)-(2, 1)
(1, 3)-(1, 2)          (2, 1)-(1, 1)
(3, 2)-(3, 3)          (1, 1)-(0, 1)
(3, 3)-(2, 3)          (0, 1)-(0, 0)

Now in the result, let's take only the first coordinate, this is your polygon:

(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0)
(4, 1)
(4, 2)
(3, 2)
(3, 3)
(2, 3)
(1, 3)
(1, 2)
(2, 2)
(2, 1)
(1, 1)
(0, 1)

You can now simplify it by eliminating consecutive points that are on a single line (i.e. in three consecutive points that either have the same x or y coordinate, eliminate the middle one)

(0, 0)
(4, 0)
(4, 2)
(3, 2)
(3, 3)
(1, 3)
(1, 2)
(2, 2)
(2, 1)
(0, 1)

This is now your polygon in clock-wise order:

(0, 0)--------------------------------------(4, 0)
  |                                           |
  |                                           |
(0, 1)----------------(2, 1)                  |
                        |                     |
                        |                     |
           (1, 2)-----(2, 2)     (3, 2)-----(4, 2)
             |                     |
             |                     |
           (1, 3)----------------(3, 3)

This algorithm can be expanded to handle holes as well. You'd just need to account for multiple polygons when ordering the edges. Conveniently, holes will be defined counter-clock-wise, this is handy if you want to draw the result with svg paths or other d2 path algorithms that allow for polygons with overlap.

Sickness

Hi, apologies for posting almost a year later. How can this algorithm be converted to run in O(N) time ? – Clayberg

Answer 2

I am not sure to understand what your data structure contains, and I assume that you have a list of squares known by the coordinates of some point (corner or center).

Compute the bounding box and create a binary bitmap of the same size. Unless the geometry is really sparse, the area of the bitmap will be of the same order as the number of squares.

For every square, paint the corresponding pixel black. Then use a contouring algorithm. To obtain the outline of the squares, you will need to design a correspondence table between the pixl-to-pixel moves and the outline fragments to be appended.

Brewster