Creating a new array from a Flood Fill operation in JavaScript

Question

Creating a new array from a Flood Fill operation in JavaScript

I am seeking guidance on modifying this algorithm to generate a new array of updated elements instead of altering the global map array. This is the JavaScript implementation of the Flood Fill algorithm.

Starting Array:

var map = [
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1]
];

Desired Result after calling floodFill function:

result = [
    [0, 2, 2],
    [0, 2, 0],
    [2, 2, 0],
    [0, 2, 0]
];

Below is the code snippet (which changes connected ones in the original array to twos):

var map = [
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1]
];

function floodFill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];

    function flow(x,y) {
        // bounds check what we were passed
        if (x >= 0 && x < data.length && y >= 0 && y < data[x].length) {
            if (data[x][y] === target) {
                data[x][y] = newValue;
                flow(x-1, y);
                flow(x+1, y);
                flow(x, y-1);
                flow(x, y+1);
            }
        }
    }

    flow(x,y);
}

var result = floodFill(map, 1, 3, 2);
/*
result = [
    [0, 2, 2],
    [0, 2, 0],
    [2, 2, 0],
    [0, 2, 0]
]
*/

javascript arrays algorithm flood-fill

Answer 1

Answer №1

The initial step is to create a duplicate of the 2D array. This involves executing a process known as a deep-clone on the data, which will copy its contents into a fresh 2D array named newData. Subsequent changes can then be made to this duplicated version.

function floodFill(data, x0, y0, newValue) {
    var minX = x0, maxX = x0;
    var minY = y0, maxY = y0;

    // Deep clone operation to replicate data in newData
    var newData = [];
    for (var i = 0; i < data.length; i++)
        newData[i] = data[i].slice();

    // All modifications are done on newData moving forward
    var target = newData[x0][y0];
    function flow(x,y) {
        if (x >= 0 && x < newData.length && y >= 0 && y < newData[x].length) {
            if (newData[x][y] === target) {
                minX = Math.min(x, minX);
                maxX = Math.max(x, maxX);
                minY = Math.min(y, minY);
                maxY = Math.max(y, maxY);

                newData[x][y] = newValue;
                flow(x-1, y);
                flow(x+1, y);
                flow(x, y-1);
                flow(x, y+1);
            }
        }
    }
    flow(x0,y0);

    // Adjusting array size by cutting out a square
    var result = [];
    for (var i = minX; i < maxX + 1; i++)
        result[i] = newData[i].slice(minY, maxY + 1);
    return result;
}

To eliminate the zeros surrounding the outcome, it is essential to monitor and record the minimum and maximum x and y coordinates reached during the flood fill process. Subsequently, a square within the dimensions of [minX..maxX] x [minY..maxY] needs to be removed from the final result.

Answer 2

The initial step is to create a duplicate of the 2D array. This involves executing a process known as a deep-clone on the data, which will copy its contents into a fresh 2D array named newData. Subsequent changes can then be made to this duplicated version.

function floodFill(data, x0, y0, newValue) {
    var minX = x0, maxX = x0;
    var minY = y0, maxY = y0;

    // Deep clone operation to replicate data in newData
    var newData = [];
    for (var i = 0; i < data.length; i++)
        newData[i] = data[i].slice();

    // All modifications are done on newData moving forward
    var target = newData[x0][y0];
    function flow(x,y) {
        if (x >= 0 && x < newData.length && y >= 0 && y < newData[x].length) {
            if (newData[x][y] === target) {
                minX = Math.min(x, minX);
                maxX = Math.max(x, maxX);
                minY = Math.min(y, minY);
                maxY = Math.max(y, maxY);

                newData[x][y] = newValue;
                flow(x-1, y);
                flow(x+1, y);
                flow(x, y-1);
                flow(x, y+1);
            }
        }
    }
    flow(x0,y0);

    // Adjusting array size by cutting out a square
    var result = [];
    for (var i = minX; i < maxX + 1; i++)
        result[i] = newData[i].slice(minY, maxY + 1);
    return result;
}

To eliminate the zeros surrounding the outcome, it is essential to monitor and record the minimum and maximum x and y coordinates reached during the flood fill process. Subsequently, a square within the dimensions of [minX..maxX] x [minY..maxY] needs to be removed from the final result.

Answer 3

Answer №2

Presented below is a stack-based, iterative flood fill algorithm that operates out-of-place and returns the area of interest as a 2D sub-array post executing the flood fill with newValue:

function floodFill (data, x, y, newValue) {
  const target = data[y][x]
  const stack = []
  const fill = []
  const directions = {
    0: { x: -1, y:  0 },
    1: { x:  1, y:  0 },
    2: { x:  0, y: -1 },
    3: { x:  0, y:  1 }
  }
  const { X = 0, Y = 1, DIR = 2 } = {}
  let [minX, maxX, minY, maxY] = [x, x, y, y]

  function isChecked (x, y) {
    const hash = `${x},${y}`
    const checked = isChecked[hash]

    isChecked[hash] = true

    return checked
  }

  // validates spot as target
  function isValid (x, y) {
    return (
      x >= 0 && x < data[0].length &&
      y >= 0 && y < data.length &&
      data[y][x] === target &&
      !isChecked(x, y)
    )
  }

  // start with x, y  
  stack.push([x, y, [0, 1, 2, 3]])

  // continue flood fill while stack is not empty
  while (stack.length > 0) {
    let top = stack.pop()

    // if there are directions left to traverse
    if (top[DIR].length > 0) {
      // get next direction
      let dir = top[DIR].pop()
      let delta = directions[dir]
      // remember this spot before traversing
      stack.push(top)
      // calculate next spot
      top = [top[X] + delta.x, top[Y] + delta.y, [0, 1, 2, 3]]

      // if next spot doesn't match target value, skip it
      if (!isValid(...top)) continue

      // traverse to next spot
      stack.push(top)
    } else {
      // we're done with this spot
      // expand area of interest
      minX = Math.min(minX, top[X])
      maxX = Math.max(maxX, top[X])
      minY = Math.min(minY, top[Y])
      maxY = Math.max(maxY, top[Y])

      // and remember it for filling the copied sub-array later
      fill.push([top[X], top[Y]])
    }
  }

  // now that flood fill is completed, fetch result sub-array and fill it
  const result = []

  // generate result sub-array by copying data
  for (let i = minY; i <= maxY; i++) {
    result.push(data[i].slice(minX, maxX + 1))
  }
  // fill each remembered spot with newValue
  for (let i = 0; i < fill.length; i++) {
    let [gx, gy] = fill[i]
    let [rx, ry] = [gx - minX, gy - minY]

    result[ry][rx] = newValue
  }

  return result
}

const map = [
  [0, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1]
]

let result = floodFill(map, 3, 1, 2)

console.log(stringify(map))
console.log(stringify(result))

// for console.log(), ignore this
function stringify(data) {
  return data.map(row => row.join(', ')).join('\n')
}

The usage of isChecked() in this implementation prevents infinite iteration cycles by ensuring any single spot is considered only once during the flood fill process.

Answer 4

Presented below is a stack-based, iterative flood fill algorithm that operates out-of-place and returns the area of interest as a 2D sub-array post executing the flood fill with newValue:

function floodFill (data, x, y, newValue) {
  const target = data[y][x]
  const stack = []
  const fill = []
  const directions = {
    0: { x: -1, y:  0 },
    1: { x:  1, y:  0 },
    2: { x:  0, y: -1 },
    3: { x:  0, y:  1 }
  }
  const { X = 0, Y = 1, DIR = 2 } = {}
  let [minX, maxX, minY, maxY] = [x, x, y, y]

  function isChecked (x, y) {
    const hash = `${x},${y}`
    const checked = isChecked[hash]

    isChecked[hash] = true

    return checked
  }

  // validates spot as target
  function isValid (x, y) {
    return (
      x >= 0 && x < data[0].length &&
      y >= 0 && y < data.length &&
      data[y][x] === target &&
      !isChecked(x, y)
    )
  }

  // start with x, y  
  stack.push([x, y, [0, 1, 2, 3]])

  // continue flood fill while stack is not empty
  while (stack.length > 0) {
    let top = stack.pop()

    // if there are directions left to traverse
    if (top[DIR].length > 0) {
      // get next direction
      let dir = top[DIR].pop()
      let delta = directions[dir]
      // remember this spot before traversing
      stack.push(top)
      // calculate next spot
      top = [top[X] + delta.x, top[Y] + delta.y, [0, 1, 2, 3]]

      // if next spot doesn't match target value, skip it
      if (!isValid(...top)) continue

      // traverse to next spot
      stack.push(top)
    } else {
      // we're done with this spot
      // expand area of interest
      minX = Math.min(minX, top[X])
      maxX = Math.max(maxX, top[X])
      minY = Math.min(minY, top[Y])
      maxY = Math.max(maxY, top[Y])

      // and remember it for filling the copied sub-array later
      fill.push([top[X], top[Y]])
    }
  }

  // now that flood fill is completed, fetch result sub-array and fill it
  const result = []

  // generate result sub-array by copying data
  for (let i = minY; i <= maxY; i++) {
    result.push(data[i].slice(minX, maxX + 1))
  }
  // fill each remembered spot with newValue
  for (let i = 0; i < fill.length; i++) {
    let [gx, gy] = fill[i]
    let [rx, ry] = [gx - minX, gy - minY]

    result[ry][rx] = newValue
  }

  return result
}

const map = [
  [0, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1]
]

let result = floodFill(map, 3, 1, 2)

console.log(stringify(map))
console.log(stringify(result))

// for console.log(), ignore this
function stringify(data) {
  return data.map(row => row.join(', ')).join('\n')
}

The usage of isChecked() in this implementation prevents infinite iteration cycles by ensuring any single spot is considered only once during the flood fill process.

Creating a new array from a Flood Fill operation in JavaScript

Answer №1

Answer №2

Similar questions

Alter the hue of the div

Tips for importing numerous text files to an array using Ruby

Tips on passing a variable into a controller using jQuery AJAX from the URL

Tips on showing the prior user entry in addition to the latest input

Why is it that one of my useQuery hooks is returning a value while the other one is returning undefined?

Stop Jade from collapsing the directory hierarchy

Interfacing Electron Frontend with Python Backend through seamless communication

Ensure AngularJS creates a controller just once

What are the potential disadvantages of relocating the login logic from the 'signIn()' function in NextAuth.js?

Identifying the completion of loading a HTML page using an object tag

Error: The function nodemailer.createTransport is not defined or does not exist

Error in Jquery Ajax autocomplete script

What is the best way to minimize the number of requests sent in AngularJS?

Intensive analysis of objects comparing their characteristics

How can I achieve a "tab selector" effect with "input" elements on a website?

Explore the data visualization capabilities of Angular Elements

identifying which rows in an array have infinity values in all columns

Solving layout issues / Techniques for determining element heights

Inspecting the session array to identify a specific value

Error messages arising from JSON files generated by PHP