Apr 3, 2024 · Mar 25, 2024 · Mar 25, 2024 · Mar 26, 2024 · Mar 27, 2024
diff --git a/Recursive/FloodFill.js b/Recursive/FloodFill.js
 * @see https://www.techiedelight.com/flood-fill-algorithm/
 */

 constneighbors = [
 constneighborOffsets = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [1, 1]
 ]

 function isInside(rgbData, location) {
  const x = location[0]
  const y = location[1]
  return x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length
 }

 function checkLocation(rgbData, location) {
  if (!isInside(rgbData, location)) {
    throw new Error('location should point to a pixel within the rgbData')
  }
 }

 function* neighbors(rgbData, location) {
  for (const offset of neighborOffsets) {
    const neighborLocation = [location[0] + offset[0], location[1] + offset[1]]
    if (isInside(rgbData, neighborLocation)) {
      yield neighborLocation
    }
  }
 }

 /**
 * Implements the flood fill algorithm through a breadth-first approach using a queue.
 *
  targetColor,
  replacementColor
 ) {
  if (
    location[0] < 0 ||
    location[0] >= rgbData.length ||
    location[1] < 0 ||
    location[1] >= rgbData[0].length
  ) {
    throw new Error('location should point to a pixel within the rgbData')
  }
  checkLocation(rgbData, location)

  const queue = []
  queue.push(location)
  targetColor,
  replacementColor
 ) {
  if (
    location[0] < 0 ||
    location[0] >= rgbData.length ||
    location[1] < 0 ||
    location[1] >= rgbData[0].length
  ) {
    throw new Error('location should point to a pixel within the rgbData')
  }
  checkLocation(rgbData, location)

  depthFirstFill(rgbData, location, targetColor, replacementColor)
 }

  if (rgbData[currentLocation[0]][currentLocation[1]] === targetColor) {
    rgbData[currentLocation[0]][currentLocation[1]] = replacementColor

    for (let i = 0; i < neighbors.length; i++) {
      const x = currentLocation[0] + neighbors[i][0]
      const y = currentLocation[1] + neighbors[i][1]
      if (x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length) {
        queue.push([x, y])
      }
    for (const neighborLocation of neighbors(rgbData, currentLocation)) {
      queue.push(neighborLocation)
    }
  }
 }
 function depthFirstFill(rgbData, location, targetColor, replacementColor) {
  if (rgbData[location[0]][location[1]] === targetColor) {
    rgbData[location[0]][location[1]] = replacementColor

    for (let i = 0; i < neighbors.length; i++) {
      const x = location[0] + neighbors[i][0]
      const y = location[1] + neighbors[i][1]
      if (x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length) {
        depthFirstFill(rgbData, [x, y], targetColor, replacementColor)
      }
    for (const neighborLocation of neighbors(rgbData, location)) {
      depthFirstFill(rgbData, neighborLocation, targetColor, replacementColor)
    }
  }
 }
diff --git a/Recursive/test/FloodFill.test.js b/Recursive/test/FloodFill.test.js
  })
 })

 describe.each([breadthFirstSearch, depthFirstSearch])('%o', (floodFillFun) => {
  it.each([
    [1, -1],
    [-1, 1],
    [0, 7],
    [7, 0]
  ])('throws for start position [%i, %i]', (location) => {
    expect(() =>
      floodFillFun(generateTestRgbData(), location, green, orange)
    ).toThrowError()
  })
 })

 /**
 * Utility-function to test the function "breadthFirstSearch".
 *
Original file line number	Diff line number	Diff line change
Expand Up		@@ -9,7 +9,7 @@
		* @see https://www.techiedelight.com/flood-fill-algorithm/
		*/

		constneighbors = [
		constneighborOffsets = [
		[-1, -1],
		[-1, 0],
		[-1, 1],
Expand All		@@ -20,6 +20,27 @@ const neighbors = [
		[1, 1]
		]

		function isInside(rgbData, location) {
		const x = location[0]
		const y = location[1]
		return x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length
		}

		function checkLocation(rgbData, location) {
		if (!isInside(rgbData, location)) {
		throw new Error('location should point to a pixel within the rgbData')
		}
		}

		function* neighbors(rgbData, location) {
		for (const offset of neighborOffsets) {
		const neighborLocation = [location[0] + offset[0], location[1] + offset[1]]
		if (isInside(rgbData, neighborLocation)) {
		yield neighborLocation
		}
		}
		}

		/**
		* Implements the flood fill algorithm through a breadth-first approach using a queue.
		*
Expand All		@@ -34,14 +55,7 @@ export function breadthFirstSearch(
		targetColor,
		replacementColor
		) {
		if (
		location[0] < 0 \|\|
		location[0] >= rgbData.length \|\|
		location[1] < 0 \|\|
		location[1] >= rgbData[0].length
		) {
		throw new Error('location should point to a pixel within the rgbData')
		}
		checkLocation(rgbData, location)

		const queue = []
		queue.push(location)
Expand All		@@ -65,14 +79,7 @@ export function depthFirstSearch(
		targetColor,
		replacementColor
		) {
		if (
		location[0] < 0 \|\|
		location[0] >= rgbData.length \|\|
		location[1] < 0 \|\|
		location[1] >= rgbData[0].length
		) {
		throw new Error('location should point to a pixel within the rgbData')
		}
		checkLocation(rgbData, location)

		depthFirstFill(rgbData, location, targetColor, replacementColor)
		}
Expand All		@@ -98,13 +105,8 @@ function breadthFirstFill(

		if (rgbData[currentLocation[0]][currentLocation[1]] === targetColor) {
		rgbData[currentLocation[0]][currentLocation[1]] = replacementColor

		for (let i = 0; i < neighbors.length; i++) {
		const x = currentLocation[0] + neighbors[i][0]
		const y = currentLocation[1] + neighbors[i][1]
		if (x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length) {
		queue.push([x, y])
		}
		for (const neighborLocation of neighbors(rgbData, currentLocation)) {
		queue.push(neighborLocation)
		}
		}
		}
Expand All		@@ -120,13 +122,8 @@ function breadthFirstFill(
		function depthFirstFill(rgbData, location, targetColor, replacementColor) {
		if (rgbData[location[0]][location[1]] === targetColor) {
		rgbData[location[0]][location[1]] = replacementColor

		for (let i = 0; i < neighbors.length; i++) {
		const x = location[0] + neighbors[i][0]
		const y = location[1] + neighbors[i][1]
		if (x >= 0 && x < rgbData.length && y >= 0 && y < rgbData[0].length) {
		depthFirstFill(rgbData, [x, y], targetColor, replacementColor)
		}
		for (const neighborLocation of neighbors(rgbData, location)) {
		depthFirstFill(rgbData, neighborLocation, targetColor, replacementColor)
		}
		}
		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -21,6 +21,19 @@ describe('FloodFill', () => {
		})
		})

		describe.each([breadthFirstSearch, depthFirstSearch])('%o', (floodFillFun) => {
		it.each([
		[1, -1],
		[-1, 1],
		[0, 7],
		[7, 0]
		])('throws for start position [%i, %i]', (location) => {
		expect(() =>
		floodFillFun(generateTestRgbData(), location, green, orange)
		).toThrowError()
		})
		})

		/**
		* Utility-function to test the function "breadthFirstSearch".
		*
Expand Down