Finding islands in a grid? traversing a graph to find smaller disjoint set

  • Thread starter Thread starter farful
  • Start date Start date
  • Tags Tags
    Graph Grid Set
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
1 reply · 4K views
farful
Messages
55
Reaction score
1
I'm working in matlab, and looking for help on how to do the following. (answers in any language or pseudocode will be fine)

I have an nxn matrix, with each cell containing a 1 or a 0. The border cells are all 1's.

Is there an efficient algorithm to determine if there are any "islands" of 1's? That is, any 1's not connected to the border.

For example, if my matrix is:

1 1 1 1 1 1
1 0 0 0 1 1
1 0 1 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1

I'd like to be able to identify the island of the three 1's (and eliminate them).

Thanks!
 
Physics news on Phys.org

Discussion

How about nodal expansion? You can take the expansion part of pathfinder algorithms for 2D grids and modify it a bit. Choose a source node, if this node is connected to the border, then expand to another node, or several nodes. Choose the node which is not connected to the border as the source and expand to other nodes. If those nodes are 1s and not connected to the border, then you have your island (your current source and expanded nodes). Of course you will have to specify how many 1s make an island, and how these 1s relate to your current source node. You should mark explored nodes as already explored, since they cannot be used again. It will help your expansion algorithm.