There is unstructured grid which contains only quadrangles cells. Each cell has 4 neighbors, and known them (has a pointer to them). I can iterate through all cells in the grid. Some cells are marked as a "A - red" some as a "B - blue" - see attached picture - Image

Cells form blue and red regions. I need to separate them - I need information which cells belong to regions A1, A2, B1, B2... etc. The number of regions of each type is unknown.


Let's say you have a cell $K$, then here's an algorithm to find all the cells that are connected with $K$ and have the same color (i.e., to find all cells of a domain):

domain = ()
new_cells_list = (K)
while (new_cells_list not empty)
    // find all neighbors of recently found cells
    // that have the same color and that we haven't
    // visited yet
    next_cells_list = ()
    for (T in new_cells_list)
      for (n=1..4)
        if (T.neighbor(n).color() == K.color()
            T.neighbor(n) not in domain
            T.neighbor(n) not in new_cells_list
            T.neighbor(n) not in next_cells_list)
    domain.append (new_cells_list);
    new_cells_list = next_cells_list;

For a given cell $K$, this then gives you all other cells of same color that are connected to it. You can now repeat this: Start with one cell, find its domain. Then find the next cell that is not part of the first domain and find its domain. Find the next cell that is not part of the previous two domains and find its domain. Etc. By counting how often this process is repeated, you get how many domains there are.

  • 2
    $\begingroup$ A reference for this type of approach that may reinforce Wolfgang's explanation is link $\endgroup$ – John Mousel Apr 24 '13 at 14:20
  • $\begingroup$ The idea for this approach is borrowed from knowing how the Cuthill-McKee algorithm for renumbering works. $\endgroup$ – Wolfgang Bangerth Apr 26 '13 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.