How to use the BFS algorithm to keep only the outer points?

Question

Let's say I have a 500x500 2D grid (from -250 to 250).

Each cell of the grid has a certain value, from 0 to 100.

What I've been trying to do is keep a list of all the cell with a value lower than 50 starting at the point (0, 0), but I would like not to keep all the points, but only the outer points (perimeter, bounds, a cell with a value lower than 50 that does not have 4 adjacent cells with a value lower than 50).

The way I implemented the algorithm, I keep a list of all the points. How should I modify it? I would like to optimize the code if possible (I can have bigger grids), so I would prefer not to iterate again.

pointList pointsWithValueBelow50; // The list of points with a value below 50
map<point, bool> pointDiscovered; // A map of the points we already passed through
point a = {0,0};
point b;
int value;
Queue q;

q.enqueue(a);
pointDiscovered[a] = true;
while(!q.isEmpty())
{
    a = q.dequeue(a)
    value = calculateValue(a); // Random method that verify if the points has a value below 50 in the grid
    if (value < 50)
    {
         pointsWithValueBelow50.add(a);
         b[0] = a[0]+1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0]-1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]+1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]-1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
    }     
}

As you can see, I keep in my list all the points with a value below 50, instead of the outer points. How can I modify this code? Should I use another algorithm?

Answer 1

Let us consider the cell array as a grey-scale image (where cell values are pixel intensities). What you are attempting to do ("find borders") is a common problem in graphics, and there is a well-known algorithm (Marching Squares) to find such borders as lists (with the additional property of the lists being ordered, so that when you traverse the list, you are going around the vertexes of a polygon that contains the interesting area.

Marching squares is O(cells) (it only needs to look at each cell-neighbourhood once in the worst case), and can be parallelized for even greater performance. There are many variations, based on what is considered a relevant transition and whether you want to find only one boundary or all boundaries.

There are many implementations out there. One of the cleanest that I have read is here (LGPL; returns all boundaries; configurable threshold) - translating it from Java to C++ should be relatively straightforward.

Answer 2

Sorry, I forgot to add my solution to the problem. Unfortunately, I think it's memory heavy, so any new answers will be glady accepted!

pointList pointsWithValueBelow50; // The list of points with a value below 50
pointList pointsBorder;
map<point, bool> pointDiscovered; // A map of the points we already passed through
map<point, bool> pointVisible; // The final visible points
map<point, point> pointParent; // A map of the parent point
point a = {0,0};
point b;
int value;
Queue q;

q.enqueue(a);
pointDiscovered[a] = true;
while(!q.isEmpty())
{
    a = q.dequeue(a)
    value = calculateValue(a); // Random method that verify if the points has a value below 50 in the grid
    if (value < 50)
    {
         pointsWithValueBelow50.add(a);
         b[0] = a[0]+1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0]-1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]+1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]-1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
    }
    else     
    {
        if(pointVisible[pointParent[a]] == false)
        {
            pointVisible[pointParent[a]] = true;
            pointsBorder.add(poinParent[a]);
        }
    }
}

the idea is simply that if I'm at a point that has a value higher than 50, we let the parent point know that he has to be visible since he is "border" point.