Flood fill algorithm selecting pixels with a minimum number of neighbors

Question

I'm working on a plate tectonics simulator that uses a repurposed flood fill algorithm in order to detect continents. The algorithm is much the same. The only difference is that it works with vertices instead of pixels.

I've been trying to improve the quality of this behavior - I'd like to see how it performs when it ignores pixels/vertices with two neighbors or fewer with continental crust. Is there any existing variant of the flood fill algorithm that supports this?

My (somewhat simplified) code is as follows:

var group = [];
var stack = [initialVertex];
while(stack.length > 0){
    var next = stack.pop();
    if (group.indexOf(next) != -1 && isContinental(next)){
        group.push(next);
        stack = stack.concat(getNeighbors(next));
    }
}
return group 

Answer 1

Theoretically speaking, skipping elements in an algorithm conducted over a set should decrease the time spent by that algorithm. Whether or not that increase in speed is significant depends upon your data set and the amount of time spent checking each element. If there are many cases where the skip condition will apply, then it would seem reasonable to say that the algorithm's efficiency will improve.

Let C = the time taken to execute such a skipping algorithm
    S = the total number of skipped elements
    s = the time taken to check if an element should be skipped
    E = the total number of elements
    e = the time taken to process an element

C = (E - S) * e + E * s

If (C < E * e) then the algorithm is more efficient for that particular data set than if it had no skip condition. The following graph demonstrates a scenario where checking an element costs 10% of processing an element. As more elements are skipped, the cost of the function naturally decreases.

---

Considering your case with a floodfill algorithm, it could be difficult to know ahead of time whether or not skipping certain elements will help, due to the graph nature of the problem and the variable initial co-ordinate. On one hand, an entire chain of elements adjacent to one vertex may be eliminated from the process by skipping that vertex, and on the other hand, the cost of checking could outweigh the advantages. Some testing will be in order for your particular data set.

If your simplified code reflects the actual code accurately, then there are a couple issues which I'd like to point out.

1. indexOf

   Checking for the existence of an element in an expanding array using indexOf is much slower than checking for the existence of an element in something like a hash map or associative array. The reason for this is that as the array expands over the course of the operation, it becomes increasingly more costly to check if an element is in that array. Hash maps tend to be much faster for this, at the expense of some memory. You can do something like this by using a simple {} object tied to some unique characteristic of each element, such as an ID. (Also, there was a typo in your original sample code. indexOf returns -1 when an element is not found, and the result was compared with != instead of ==.)

2. concat

   The use of concat to concatenate one array with another actually produces an entirely new array. As you continue to concatenate arrays with arrays, you create a lot of unnecessary garbage. It's much more efficient to keep your original stack array and just push onto that.

---

I have set up a jsperf demo demonstrating some of the changes that could be made to your algorithm, regarding basic efficiency such as using an associative map, not using Array.concat, ignoring neighbors of a vertex that happen to be the vertex itself, and, of course, skipping elements. As always with any optimization issue, you should profile first to find where your program is spending most of its time and benchmark changes in code appropriately. I hope this has been of some help to you, and good luck!

A copy of the most important code used in the demo follows:

function hasSufficientContinentalNeighbors(vert) {
    var i = vert.neighbors.length, n = 0;

    if (i <= 2) { return false; }

    while (i--) {
        if (isContinental(vert.neighbors[i])) {
            // Return true at nearest opportunity.
            if (++n === 3) { return true; }
        }
    }

    return false;
}

// Skip (w/o redundancies)
var group = [], grouped = {};
var stack = [initialVertex];
var next, nearby, i;
while (stack.length > 0) {
    next = stack.pop();
    if (grouped[next.id] === undefined && isContinental(next) && hasSufficientContinentalNeighbors(next)) {
        group.push(next);
        grouped[next.id] = true;
        nearby = getNeighbors(next);
        i = nearby.length;
        while (i--) {
            if (nearby[i] !== next) { stack.push(nearby[i]); }
        }
    }
}

Answer 2

Wasn't too hard, in the end. I all need to do was move the isContinental check to the neighboring vertices. I cannot say whether this is the most efficient method, but it does work:

var group = [];
var stack = [initialVertex];
while(stack.length > 0){
    var next = stack.pop();
    if (group.indexOf(next) != -1){
        var neighbors = getNeighbors(next).filter(isContinental)
        if (neighbors.length > 3){
            group.push(next);
            stack = stack.concat(neighbors);
        }
    }
}
return group;