imageFill.cpp

#include <iostream>

typedef unsigned char pixel[3];
typedef pixel** Image;
/// Typedef for fully const pixel array to avoid long type
typedef const pixel * const* const ConstImage;

/// 2D matrix of booleans, used to mark pixels as visited
typedef bool** BoolMatrix;

/// Controls if input/output is done by intensity or color, useful for debugging
enum Mode {
	Color, Intensity,
};

/// Deallocate 2d image of pixel
/// @param image - pointer to the 2d array
/// @param height - number of rows in the image
void freeImage(Image image, int height) {
	for (int c = 0; c < height; c++) {
		delete[] image[c];
	}
	delete[] image;
}

/// Allocate 2d array of pixels
/// @param width - pixels in a row
/// @param height - number of rows
/// @return pointer to the image data or nullptr on failure
Image allocateImage(int width, int height) {
	Image image = new (std::nothrow) pixel*[height];
	if (!image) {
		freeImage(image, 0);
		return nullptr;
	}
	for (int c = 0; c < height; c++) {
		image[c] = new (std::nothrow) pixel[width];
		if (!image[c]) {
			freeImage(image, c);
			return nullptr;
		}
	}
	return image;
}

/// Get the intensity of a single pixel
/// @param p - pointer to the pixel
/// @return average of the pixel components
int getIntensity(const pixel p) {
	return (p[0] + p[1] + p[2]) / 3;
}

/// Read image from input
/// @param image [out] - pointer to the data where to read input into
/// @param width - number of pixels in a row
/// @param height - number of rows
/// @param mode - control if data is read as 1 value per pixel (intensity - used for debugging) or 3 values (r, g, b)
void readImage(Image image, int width, int height, Mode mode = Color) {
	for (int r = 0; r < height; r++) {
		for (int c = 0; c < width; c++) {
			if (mode == Color) {
				for (int comp = 0; comp < 3; comp++) {
					std::cin >> image[r][c][comp];
				}
			} else {
				int intensity;
				std::cin >> intensity;
				for (int comp = 0; comp < 3; comp++) {
					image[r][c][comp] = intensity;
				}
			}
		}
	}
}

/// Print image data to cout
/// @param image - pointer to the pixels
/// @param width - number of pixels in a row
/// @param height - number of rows
/// @param mode - control if pixels will be printed as intensity or color (r, g, b)
void printImage(ConstImage image, int width, int height, Mode mode = Color) {
	for (int r = 0; r < height; r++) {
		for (int c = 0; c < width; c++) {
			if (mode == Color) {
				for (int comp = 0; comp < 3; comp++) {
					std::cout << image[r][c][comp] << ' ';
				}
			} else {
				std::cout << getIntensity(image[r][c]) << ' ';
			}
		}
		std::cout << std::endl;
	}
}

/// Check if two pixels are similar
/// @param a - first pixel
/// @param b - second pixel
/// @return true if the difference in intensity of a and b is no more than 1
bool isSimilar(const pixel a, const pixel b) {
	const int intensityA = getIntensity(a);
	const int intensityB = getIntensity(b);
	return abs(intensityA - intensityB) <= 1;
}

/// Allocate and copy an image
/// @param source - pointer to the source image
/// @param width - number of pixels in a row
/// @param height - number of rows
/// @return pointer to the image copy or nullptr if allocation fails
Image copyImage(ConstImage source, int width, int height) {
	Image dest = allocateImage(width, height);
	if (!dest) {
		return nullptr;
	}
	for (int r = 0; r < height; r++) {
		memcpy(dest[r], source[r], sizeof(pixel) * width);
	}
	return dest;
}

/// Check if given coordinate is inside a give image size
/// @param width - width of the image
/// @param height - height of the image
/// @param x - x component of the coord
/// @param y - y component of the coord
/// @return true if (x, y) is in the image
bool isValidCoord(int width, int height, int x, int y) {
	return x >= 0 && x < width && y >= 0 && y < height;
}

/// Set single pixel to black color
/// @param p [out] - the pixel to set
void setBlack(pixel p) {
	p[0] = p[1] = p[2] = 0;
}

/// Free memory allocate for matrix
/// @param matrix - pointer to the matrix
/// @param height - number of rows in the matrix
void freeMatrix(BoolMatrix matrix, int height) {
	for (int c = 0; c < height; c++) {
		delete[] matrix[c];
	}
	delete[] matrix;
}

/// Allocate boolean matrix will all values set to false
/// @param width - number of booleans in a row
/// @param height - number of rows
/// @return pointer to the matrix or nullptr on failure
BoolMatrix newZeroMatrix(int width, int height) {
	BoolMatrix matrix = new (std::nothrow) bool*[height];
	if (!matrix) {
		return nullptr;
	}

	for (int r = 0; r < height; r++) {
		matrix[r] = new (std::nothrow) bool[width];
		if (!matrix[r]) {
			freeMatrix(matrix, r);
			return nullptr;
		}
		for (int c = 0; c < width; c++) {
			matrix[r][c] = false;
		}
	}
	return matrix;
}

/// Flood-fill with black color if source image pixels are similar
/// @param source - image source where to check for similar pixels
/// @param visited - boolean matrix to ensure pixels are not checked more than once
/// @param dest [out] - output image where to fill with black pixels
/// @param width - width of both images
/// @param height - height of both images
/// @param row - current row
/// @param col - current col
void recursiveFill(ConstImage source, BoolMatrix visited, Image dest, int width, int height, int row, int col) {
	if (visited[row][col]) {
		return;
	}
	visited[row][col] = true;
	setBlack(dest[row][col]);

	int coords[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	for (int c = 0; c < 4; c++) {
		const int nRow = row + coords[c][0];
		const int nCol = col + coords[c][1];
		if (isValidCoord(width, height, nRow, nCol) && isSimilar(source[row][col], source[nRow][nCol])) {
			recursiveFill(source, visited, dest, width, height, nRow, nCol);
		}
	}
}

/// Fill an area of similar pixels with black and return a copy
/// @param image - pointer to the source image
/// @param width - width of the image
/// @param height - height of the image
/// @param row - starting row of the fill
/// @param column - starting column of the fill
/// @retunr pointer to the edited image copy or nullptr on allocation failure
pixel **fillArea(
	const pixel *const *const image,
	size_t width, size_t height,
	size_t row, size_t column) {

	Image newImage = copyImage(image, width, height);
	if (!newImage) {
		return nullptr;
	}
	BoolMatrix visited = newZeroMatrix(width, height);
	if (!visited) {
		freeImage(newImage, height);
		return nullptr;
	}

	recursiveFill(image, visited, newImage, width, height, row, column);
	freeMatrix(visited, height);
	
	return newImage;
}

int main() {
	// change to Intensity to test with given example
	const Mode mode = Color;
	int width, height;
	std::cin >> width >> height;
	Image image = allocateImage(width, height);
	if (!image) {
		std::cout << "Failed to allocate image " << width << "x" << height << " stopping...";
		return 1;
	}
	readImage(image, width, height, mode);
	std::cout << "Image:" << std::endl;

	int x, y;
	std::cin >> x >> y;
	Image newImage = fillArea(image, width, height, y, x);
	// done with image data, deallocate
	freeImage(image, width);

	if (!newImage) {
		std::cout << "Failed to allocate new image" << width << "x" << height << " stopping...";
		return 1;
	}

	printImage(newImage, width, height, mode);
	freeImage(newImage, height);
	return 0;
}