NOT IMPLEMENTED YET

NOT IMPLEMENTED YET

NOT IMPLEMENTED YET

floodFill.js

A non-recursive, n-dimensional implementation of flood fill.

Usage

Let's say we'd like to call the flood fill algorithm on a two-dimensional data structure.

// Some data structure that we'd like to flood fill.
var data = [
  [0, 0, 1],
  [0, 1, 1],
  [1, 1, 0]
];

// Define our getter for accessing the data structure.
var getter = function (x, y) {
  return data[y][x];
};

// Choose a start node.
var seed = [1, 1];

// Flood fill over the data structure.
var result = floodFill({
  getter: getter,
  seed: seed
});

// Get the flooded nodes from the result.
result.flooded

Flooded nodes are returned as a nested array of arguments:

[[1, 1], [2, 1], [2, 0], [1, 2], [0, 2]]

onFlood

You can call a function when a node is flooded with the 'onFlood' option.

It is important that you do not modifying the data structure that floodFill is iterating over. Instead, make a copy first:

var copy = data.slice(0);

floodFill({
  getter: getter,
  seed: seed,
  onFlood: function (x, y) {
    copy[y][x] = 5;
  }
});

The copied data structure would now look like this:

[
  [0, 0, 5],
  [0, 5, 5],
  [5, 5, 0]
];

n-dimensions

You can use floodFill in any number of dimensions:

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

var result = floodFill({
  getter: function (x) { return data[x]; },
  seed: [3]
});

result.flooded; // [[3], [2]];

The number of dimensions will be inferred from your getter.

Equivalence

If you're equivalence relation is more complicated, you can set it with the 'equals' option.

var data = [
  ["cat", "bat", "zoo"],
  ["foo", "hat", "bar"],
  ["baz", "rat", "qux"]
];

// Flood cells that contain the string 'at'.
var equals = function (node) {
  return node.match(/at/) !== null;
};

var result = floodFill({
  getter: getter,
  seed: [1, 1],
  equals: equals
});

Boundaries

You can capture or call a function when a boundary between a flooded and non-flooded cell is reached.

This includes cells at the edges of your data structure.

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

var result = floodFill({
  getter: function (x) { return data[x]; },
  seed: [3],
  onBoundary: function (x) {
    console.log(x, " is a boundary.");
  }
});

result.boundaries; // [[2], [6]]

Diagonals

By default, floodFill will not visit diagonal nodes.

If you started in the middle of the following data structure, the top-left node would not be included.

1 0 0
0 1 1
0 1 1

You can change this behaviour with the 'diagonals' option.

floodFill({
  getter: getter,
  seed: seed,
  diagonals: true
});

This will work for any number of dimensions.

Contribution

Please send a pull request or open an issue.

You should follow me on twitter.