I am creating a flood fill algorithm in C++ using Eclipse IDE. The algorithm contains a vector of vectors called image. A square is drawn in this image based on user input, segmenting the image to two regions (inside and outside the square). A clicked point is taken in as input. If this point is inside the square, all points inside the square will be changed to a fill_value (in this case, 25). If it is outside the square, all pixels outside the square changes to fill_value. Here is the code:
#include <iostream>
#include <vector>
#include <queue>
#include <cstddef>
#include <stdexcept>
class Point
{
std::size_t x_cord;
std::size_t y_cord;
public:
Point(std::size_t x, std::size_t y):x_cord{x}, y_cord{y}
{
}
std::size_t x() const
{
return x_cord;
}
std::size_t y() const
{
return y_cord;
}
};
bool check_point(Point pt, std::size_t x_dim, std::size_t y_dim)
{
if(pt.x() >= 0 && pt.x() < x_dim && pt.y() >= 0 && pt.y() < y_dim)
{
return true;
}
return false;
}
void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val)
{
std::vector<Point> neighbors;
std::size_t x_dim = image.size();
std::size_t y_dim;
if(x_dim > 0)
{
y_dim = image[0].size();
}
if(check_point(Point{curr_point.x() - 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val)
{
q.push(Point{curr_point.x() - 1, curr_point.y()});
}
if(check_point(Point{curr_point.x(), curr_point.y() - 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val)
{
q.push(Point{curr_point.x(), curr_point.y() - 1});
}
if(check_point(Point{curr_point.x() + 1, curr_point.y()}, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val)
{
q.push(Point{curr_point.x() + 1, curr_point.y()});
}
if(check_point(Point{curr_point.x(), curr_point.y() + 1}, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val)
{
q.push(Point{curr_point.x(), curr_point.y() + 1});
}
}
void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val)
{
int old_val = image[clicked.x()][clicked.y()];
std::queue<Point> q;
q.push(clicked);
while(!q.empty())
{
Point curr_point = q.front();
get_neighbors(curr_point, q, image, old_val);
image[curr_point.x()][curr_point.y()] = new_val;
q.pop();
}
}
void draw_square(std::vector<std::vector<int>>& image, Point top_left_corner, int length)
{
std::size_t x_0 = top_left_corner.x();
std::size_t y_0 = top_left_corner.y();
std::size_t x;
std::size_t y;
for(x = x_0; x < x_0 + length; x++)
{
image[x][y_0] = 1;
image[x][y_0 + length - 1] = 1;
}
for(y = y_0; y < y_0 + length; y++)
{
image[x_0][y] = 1;
image[x_0 + length - 1][y] = 1;
}
}
void print_image(std::vector<std::vector<int>>& image, std::size_t x_dim, std::size_t y_dim)
{
for(std::size_t i = 0; i < x_dim; i++)
{
for(std::size_t j = 0; j < y_dim; j++)
{
std::cout << image[i][j] << "\t";
}
std::cout << "\n";
}
std::cout << "\n";
}
int main()
{
try
{
std::size_t x_dim, y_dim;
std::size_t x, y;
std::size_t c_x = 0;
std::size_t c_y = 0;
int length;
int fill_value = 25;
std::cout << "Enter the dimensions of the image: \n";
std::cin >> x_dim >> y_dim;
std::vector<std::vector<int>> image(x_dim, std::vector<int>(y_dim, 0));
std::cout << "Enter the top left point coordinates and length for the square: \n";
std::cin >> x >> y >> length;
Point top_left_corner{x, y};
if(!check_point(top_left_corner, x_dim, y_dim) || !check_point(Point{top_left_corner.x() + length - 1, top_left_corner.y() + length - 1}, x_dim, y_dim))
{
throw std::out_of_range{"Invalid Access"};
}
draw_square(image, top_left_corner, length);
std::cout << "Before Flood Fill: \n";
print_image(image, x_dim, y_dim);
std::cout << "Enter point to be clicked: \n";
std::cin >> c_x >> c_y;
Point clicked{c_x, c_y};
//std::cout << "here1\n";
if(!check_point(clicked, x_dim, y_dim))
{
throw std::out_of_range{"Invalid Access"};
}
std::cout << "here2\n";
flood_fill(image, clicked, fill_value);
std::cout << "After Flood Fill: \n";
print_image(image, x_dim, y_dim);
}
catch(std::out_of_range& e)
{
std::cerr << e.what() << "\n";
}
return 0;
}
It works fine for some input. However, consider the following input (The array after Before Flood Fill is a program output, not an input):
Enter the dimensions of the image:
20 20
Enter the top left point coordinates and length for the square:
15 15 4
Before Flood Fill:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Enter point to be clicked:
1 2
The program takes up a lot of processing after this and does not proceed or does not get terminated. My idea was that this is due to inefficient implementation of flood_fill function. When I use a debugger std::cout << "here2\n"; statement prints here2 on the console while it does not get printed while I simply run the program. So, I am not sure if it is flood_fill which is causing this issue or is it something else.
Why is the behavior different while running and debugging?
Kindly provide suggestions to debug.
Note: My idea was that since the value is being changed, they will automatically fail the check for being an eligible neighbor. But I see the problem with my code. By the time, the value is changed, a particular neighbor might be added many times. Both answers helped me identify this. Thank you to both.
std::size_t is an unsigned integral type. When it reaches a negative value, it wraps around to its max value, a positive one. Therefore all your x >= 0 and y >= 0 are always true. Try swapping out all your size_t for something like int.
Your other problem is that your flood fill queue are reaching tremendous sizes. This is because points are added faster than they are removed. You need some way to tell if a point has been flood filled before:
void get_neighbors(Point& curr_point, std::queue<Point>& q, std::vector<std::vector<int>>& image, int old_val, std::vector<std::vector<bool>> &visited)
{
std::vector<Point> neighbors;
int x_dim = image.size();
int y_dim;
if (x_dim > 0)
{
y_dim = image[0].size();
}
if (check_point(Point{ curr_point.x() - 1, curr_point.y() }, x_dim, y_dim) && image[curr_point.x() - 1][curr_point.y()] == old_val && !visited[curr_point.x() - 1][curr_point.y()])
{
q.push(Point{ curr_point.x() - 1, curr_point.y() });
visited[curr_point.x() - 1][curr_point.y()] = true;
}
if (check_point(Point{ curr_point.x(), curr_point.y() - 1 }, x_dim, y_dim) && image[curr_point.x()][curr_point.y() - 1] == old_val && !visited[curr_point.x()][curr_point.y() - 1])
{
q.push(Point{ curr_point.x(), curr_point.y() - 1 });
visited[curr_point.x()][curr_point.y() - 1] = true;
}
if (check_point(Point{ curr_point.x() + 1, curr_point.y() }, x_dim, y_dim) && image[curr_point.x() + 1][curr_point.y()] == old_val && !visited[curr_point.x() + 1][curr_point.y()])
{
q.push(Point{ curr_point.x() + 1, curr_point.y() });
visited[curr_point.x() + 1][curr_point.y()] = true;
}
if (check_point(Point{ curr_point.x(), curr_point.y() + 1 }, x_dim, y_dim) && image[curr_point.x()][curr_point.y() + 1] == old_val && !visited[curr_point.x()][curr_point.y() + 1])
{
q.push(Point{ curr_point.x(), curr_point.y() + 1 });
visited[curr_point.x()][curr_point.y() - 1] = true;
}
}
void flood_fill(std::vector<std::vector<int>>& image, Point clicked, int new_val)
{
if (image.empty()) return;
int old_val = image[clicked.x()][clicked.y()];
std::vector<std::vector<bool>> visisted(image.size(), std::vector<bool>(image[0].size(), false));
std::queue<Point> q;
q.push(clicked);
while (!q.empty())
{
Point curr_point = q.front();
get_neighbors(curr_point, q, image, old_val, visisted);
image[curr_point.x()][curr_point.y()] = new_val;
q.pop();
}
}