How to separate and count clusters ( 4 direction connected components) in a 2D array?

Question

1.00/5 (1 vote)

See more:

, +

for example, I have 2d array like this:

 1 2 2 2 2 1 1 1 1 2 1 1
 2 1 1 1 2 1 2 2 1 1 2 1
 2 2 1 2 1 1 2 2 2 2 1 1
 1 1 1 2 1 2 1 2 2 1 1 2 
 1 1 2 1 2 1 2 1 2 2 2 2
 1 1 2 2 2 2 1 2 1 2 1 1 
 2 1 1 2 1 1 2 2 1 1 1 2

And I want to label the connected components (4 directions)to be like this:

 1  2  2  2  2  3  3  3  3  4  5  5
 6  7  7  7  2  3  8  8  3  3  9  5
 6  6  7  10 3  3  8  8  8  8  5  5
 7  7  7  10 3  11 12 8  8  5  5  8 
 7  7  13 14 13 15 16 17 8  8  8  8
 7  7  13 13 13 13 18 19 20 8  20 20 
 21 7  7  13 22 22 19 19 20 20 20 23

the way to label the clusters is like the flood fill, if it connects to their neighbor by up-down-left-right direction, they will be grouping in the same cluster. we go from top left to bottom right. Please help me solve this problem. Thanks!!!(javascript code example would be great)

What I have tried:

I make 2 for loops for row and col, then for each element, I check for directions to see if their neighbors are the same number, and then grouping them. but I always have a conflict by doing that way as I end up counting a new cluster but that number already belongs to the previous cluster.

Posted 28-Feb-17 12:03pm

Michael Koops

Updated 28-Feb-17 16:01pm

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Rick York · Answer 1 · 2017-02-28T12:19:00

You could have another 2D array that is in "parallel" with the first 2D array. It would hold values that indicate which cluster a value is in. That would default to zero values meaning no cluster. Then keep a counter of clusters, beginning at one, that you assign to the members of a cluster when you find one. So for each value in the original array, you could look in your second array and it will tell which cluster a given value is in. There are lots of refinements you can add to this but that's how I would approach this problem.

Patrice T · Answer 2 · 2017-02-28T16:01:00

Quote:
Please help me solve this problem. Thanks!!!(javascript code example would be great)

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

advice: Take a sheet of paper and solve the problem by hand (mechanically). This method is what you must translate into program.

We give help on specific problems!
So show your code and explain the problem.

How to separate and count clusters ( 4 direction connected components) in a 2D array?

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0