n-dimensional-flood-fill
A non-recursive, n-dimensional implementation of flood fill.
Setup
Install the package.
npm install n-dimensional-flood-fill --save
Require the module.
var floodFill = ;
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 { return datayx;}; // Choose a start node.var seed = 1 1; // Flood fill over the data structure.var result = ; // Get the flooded nodes from the result.resultflooded
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; ;
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 = ; resultflooded; // [[3], [2]];
The number of dimensions will be inferred from your seed.
Equivalence
If you're equivalence relation is more complicated, you can set it with the 'equals' option.
var data = "foo" "bar" "qux" "baz"; // Flood cells start with the same letter.var { return a0 === b0;}; var result = ; resultflooded; // [[1, 1], [1, 0]]
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 = ; resultboundaries; // [[6], [2]]
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.
;
This will work for any number of dimensions.
Contribution
Please send a pull request or open an issue.
You should follow me on twitter.