Getting the edge-cells in a list of cells on a 2d grid, and knowing which neighbor is missing

Question

I create a "circle" on my 2d-grid using this code:

public List<Cell> GetSurroundingCellsCircle(Coord originCoord, int distance)
{
    List<Cell> matches = new List<Cell>();
    int EX = distance + coord.x;
    int EY = distance + coord.z;
    int SQ = distance * distance;

    for (int x = coord.x - distance; x <= EX; x++)
    {
        for (int z = coord.z - distance; z <= EY; z++)
        {
            int c = x - coord.x;
            int d = z - coord.z;

            if ((c * c + d * d) < SQ)
            {
                Cell cell = GetCell(new Coord(x, z));
                if (cell != null)
                    matches.Add(cell);
            }
        }
    }

    return matches;
}

This code works fine and returns a list of cells that together create a circle-shape. Now I want to get all the edge-cells of this circle, and not only that, but I also need to know which side of the edge-cell that has no neighbor, so I know where to draw the line. I want a result that looks like this red line:

I wrote this code that would work for a square (it just finds the max/min of X/Z and draws a sphere there, but as you can see in my image, its missing the "rounding" cells:

int maxX = 0, maxZ = 0, minX = 0, minZ = 0;

        for (int i = 0; i < cells.Count; i++)
        {
            int cX = cells[i].coord.x;
            int cZ = cells[i].coord.z;

            if (i == 0)
            {
                minX = cX;
                minZ = cZ;
            }
            else
            {
                if (cX < minX)
                    minX = cX;

                if (cZ < minZ)
                    minZ = cZ;
            }

            if (cX > maxX)
                maxX = cX;

            if (cZ > maxZ)
                maxZ = cZ;
        }

        for (int i = 0; i < cells.Count; i++)
        {
            int cX = cells[i].coord.x;
            int cZ = cells[i].coord.z;

            if (cX == maxX || cZ == maxZ || cX == minX || cZ == minZ)
            {
                Gizmos.DrawSphere(
                    new Vector3((cells[i].coord.x * GridBase.WORLD_CELL_SIZE) + GridBase.WORLD_CELL_OFFSET,
                    1,
                    (cells[i].coord.z * GridBase.WORLD_CELL_SIZE) + GridBase.WORLD_CELL_OFFSET),
                    1);
            }
        }

Answer 1

Okay. Once again, this is what I think should work, but maybe you need to shift the positions a bit around. The reason for the bloated array size is to get border cells to spit out, well, borders, instead of arrayOutOfBounds exceptions.

If you want to use this for anything else than circles, take the middle of the figure, use that as x and y (has to be int), distance becomes the bigger difference between xmax-xmin and ymax-ymin.

Remember, this is just what I think could work, and if it does not, it should at the very least provide you with an idea of what to do.

List<Cell> edgecells (int distance, int centerx, int centery, List<Cell> matches){//The list matches needs to contain ALL cells of the circle
//the functoin takes the distance, as well as the coordinates of the location of the center of the circle.
List<Cell> edgec = new List<Cell>();
int shiftx = centerx - distance+1;
int shifty = centery - distance+1;
Cell locationgrid[distance*2+2][distance*2+2];//SHOULD work, if not initialze the array somehow else. Has to be NULL.
for(int i = 0; i<matches.count; i++){ 
    locationgrid[matches[i].x-shiftx][matches[i].y-shifty] = matches[i];//This line puts all the cells ordererd in the locationgrid, instead of a list
    //Meaning a list of coords like 0|0 1|0 0|1 1|1 gets turned in an array useful for other stuff
}

for(Cell l1[] : locationgrid){//this iterates through all the grid parts. Since it's now a grid, adjacent cells can be used in calculation.
    for(Cell l : l1){
        //Assumption here is that each cell has four extra values, 'up', 'down', 'right', 'left', all responsible for storing if there's a border.
        //WARNING: the comparison method may not work and always return true!
        if(locationgrid[l.x+1][l.y]==NULL){
            l.right = true;
            edgec.Add(l);
        }
        if(locationgrid[l.x-1][l.y]==NULL){
            l.left = true;
            edgec.Add(l);
        }
        if(locationgrid[l.x][l.y+1]==NULL){
            l.up = true;
            edgec.Add(l);
        }
        if(locationgrid[l.x][l.y-1]==NULL){
            l.down = true;
            edgec.Add(l);
        }
    }
}

return edgec;//this list now contains only edge cells who have their information set about where the border is.
}

Answer 2

Just for anyone interested, I ended up getting the edges before creating the list:

public struct EdgeCell
{
    public bool north;
    public bool south;
    public bool west;
    public bool east;
    public InfoCell cell;
}

public List<EdgeCell> GetSurroundingCellsCircleEdge(Coord coord, int distance)
{
    bool CheckIfCoordInCircle(int x, int z)
    {
        int c = x - currentCoord.x;
        int d = z - currentCoord.z;

        if ((c * c + d * d) < SQ)
        {
            return true;
        }

        return false;
    }

    List<EdgeCell> matches = new List<EdgeCell>();
    int EX = distance + coord.x;
    int EY = distance + coord.z;
    int SQ = distance * distance;

    for (int x = coord.x - distance; x <= EX; x++)
    {
        for (int z = coord.z - distance; z <= EY; z++)
        {
           if(CheckIfCoordInCircle(x, z))
           {
                EdgeCell eCell = new EdgeCell();
                InfoCell cell = GetCell(new Coord(x, z));

                if (!CheckIfCoordInCircle(x - 1, z))
                {
                    eCell.cell = cell;
                    eCell.west = true;
                }
                if (!CheckIfCoordInCircle(x + 1, z))
                {
                    eCell.cell = cell;
                    eCell.east = true;
                }
                if (!CheckIfCoordInCircle(x, z - 1))
                {
                    eCell.cell = cell;
                    eCell.south = true;
                }
                if (!CheckIfCoordInCircle(x, z + 1)) 
                {
                    eCell.cell = cell;
                    eCell.north = true;
                }

                if (eCell.cell != null)
                    matches.Add(eCell);
            }
        }
    }

    return matches;
}