title: Polygon from a grid of squares
body: <p>I'm looking for an algorithm to find the polygon that surrounds a contiguous grid of squares without holes as shown here:</p>
  <p><img src="https://i.stack.imgur.com/pfDnb.png" alt="Problem Illustration" />.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p><a href="https://stackoverflow.com/questions/33472951/outline-circumference-polygon-extraction-from-geometry-constructed-from-equal/33473452#33473452">Outline (circumference) polygon extraction from geometry constructed from equal squares</a></p>
  <p><strong>EDIT:</strong> 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.</p>