Suppose i have currently a group of cells which can be considered "on" or "off", something like this picture (White means off, black means on)

Cells

The cells are basically squares with size = 1, and each corner can be calculated by:

p0 = p
p1 = p   (0, 1)
p2 = p   (1, 1)
p3 = p   (1, 0)

so each cell is actually a polygon in itself with 4 vertices

I want to generate an ordered list of vertices that creates a polygon in which all cells are grouped together, removing internal and redundant vertices, something like this:

Cells Grouped

So, the algorithm i came upon while trying to solve this only detects the verticies, and they detect correctly, and its quite simple code actually. It works like this:

foreach cell
    foreach corner of the cell //each corner is a vertex of a square cell
        if !vertex_list.contains(corner) 
            vertex_list.add(corner)
        else 
        vertex_list.remove(corner)
            endif
        endfor
endfor

BUT, it doesnt sort them correctly, If i iterate over every vertex drawing a line from it to the previous one, it generates a mess

How can i create an algorithm that generates a SORTED list of vertices to create a polygon?

CodePudding user response：

You can take this approach:

1. Create node objects for each vertex (corner). Each node will have (unique) x, y coordinates, and four references to neighbors: up, right, down, left. Each of those either references another node (pointer), or is null (when there is no edge in that direction). If for instance you have two adjacent cells, this step will create 6 nodes (not 8, because 2 vertices are shared by these cells and only one node should be created for each unique vertex). You would create a hashtable (dictionary/map) for these nodes, keyed by their x, y coordinates, so to avoid creating multiple nodes for the same vertex.

2. Find the north most node. This is the starting node. Name this also the current node.

3. Set the current direction to "right"

4. While the current node has a neighbor in the current direction, do:

   • Make that neighbor the current node
   • Add the (now) current node to the solution
   • Change the direction in counter-clockwise rotation, so that if it was right, make it up. If it was up, make it left, ...etc.
   • If the current node is the starting node, end the algorithm

5. As the current node has now no neighbor in the current direction, change the current direction in clockwise rotation, so that if it was right, make it down. If it was down, make it left, ...etc.

6. Repeat from step 4.

This assumes that all cells are connected, and the formed shape has no holes that are completely surrounded.