0

EDIT:I have a logical error and I don't know how to fix it.This is my code. I think that the problem is in the while function at line 245. It doesn't add the next valid pixel to the queue, so the queue becomes 0 and it exits the WHILE function.

I need help from a veteran here! I have something like a chess table, with equal sized squares, numbered from bottom to top, right to left, but only some of them are valid for me (as shown in the picture I posted a link to). I deleted the non-valid ones from the table.

I want my C program to count the squares in each group. As you can see in the image, a valid group only has directly connected squares, and squares that connect only diagonally are not in the same group. I used colors to evidentiate the valid groups in my picture.

I know the table's width and height and I know how many squares and valid squares it has. I stored their numbers in a vector, but I can't figure out how to count the squares in each group. How can I do this?

Here is my picture:

enter image description here

I want to find out a method which works for larger "chess tables", like pictures with known sizes.

greenro
  • 31
  • 6
  • 1
    Looks like homework? – Mörre Jan 03 '15 at 11:06
  • 4
    Write down a detailed description for a human to group those squares. Convert the description to something machine-executable. Post any problems with this program here. As it stands, this could be just homework, and people here don't do your homework when you don't show an effort yourself. – Ulrich Eckhardt Jan 03 '15 at 11:06
  • Yes, this is part of an assignment and I've been stuck on this step for some time now. I am not asking for an already done algorithm, but if you have some hints I would appreciate it. – greenro Jan 03 '15 at 11:12
  • Hint: depth-first search. – kraskevich Jan 03 '15 at 11:16
  • Thank you for your hint @user2040251, it was really helpful. I also took a look at dreadth first search, which also seems nice. – greenro Jan 03 '15 at 11:53
  • @UlrichEckhardt I added my progress to my initial post. Could you take a look over my code and point me to the right direction in finding my logical error? – greenro Jan 04 '15 at 12:55
  • No. Firstly, you didn't add any progress but a link to some external site. Secondly, that code starts off with loading a bitmap, which is a separate task from locating groups within one. Thirdly, the code is badly formatted and documented, making it tiresome to read. Still, I already see that you don't check function's return codes for errors, which is a road to desaster. Lastly, I really meant what I wrote, i.e. that you should first make a description suitable for consumption by a human and only then try to implement that in code. Use any random human to proofread what you wrote there! – Ulrich Eckhardt Jan 05 '15 at 19:55
  • Yes, there are other tasks in my code, but everything works, except locating the clusters. As you can see, I am a bigginer, that's why my code is badly formatted and documented(if you could be more specific about that, I am willing to learn). About the function's return codes, I googled information about them and I will start checking them for errors. Lastly, I made a human-suitable description and I taught it was fine. I didn't ask "any random human" to proofread what I wrote, but I will do that from now on. Thank you very much for your answer. If you have more tips, I am willing to listen. – greenro Jan 06 '15 at 17:54

3 Answers3

0

What you surely miss is : What group a valid square belongs to ?
You could use graph theory to solve that. But you can also try some other approach.

For instance, you can use one tag list which will keep track of already visited nodes or not. You can use a vector of vector for managing group nodes.

  1. Browse the table with same direction let's say from top left to bottom right. Check only non visited nodes.
  2. When a valid square is found which is non visited add this node to vector[count++] and flag this node to visited.
  3. Look for this node connected squares in bottom right direction. If one is found then flag it to visited and add the node in the same vector[count] list.
  4. You repeat the same process until you cannot find anymore connected components (with recursion for instance).
  5. If no connected squares are found anymore in the same group continue step 1.
  6. At the end just sum of each of your vector[count] and it should give the expected results (for performance you could do that on the fly while looking connected components).
coincoin
  • 4,595
  • 3
  • 23
  • 47
  • Yes, this is a similar depth first search algorithm which I did just now, in pseudocode, while walking in circles in the other room. Thank you for your answer. – greenro Jan 03 '15 at 11:52
0

You should categorize each connected squares into a single component and count the size of each component. For that you can use a nested data structure such as vector to store the connected squares and nest it inside a map to distinguish the other connected squares. like,

map<int squareIndex, vector<squares> >

The basic idea is to have a visited array so that you can ignore the already visited squares. The algorithm follows just like doing Breadth First Search in Graphs. You can use a Queue to store the adjacent connected components of the current square. I would suggest to do the following.

Algo

  1. traverse through the array from 1 to N
  2. If queue is empty then make new index in map and push element into your map
  3. If visited[element] is true then go to step 1, else visited[element]=true and push element into your map.
  4. element = dequeue()
  5. enqueue adjacent squares of the current element and repeat from step 2 for the current element

In this way finally your map will be of size 4 (for the given case) and each map element will contain a vector of the connected squares. Use size property of each vector to count the number of squares in each index.

Tamil Maran
  • 289
  • 1
  • 13
-1

You are searching for something called connected component.

This post sheds some light on the subject but there's a number of different implementations available on the Web.

Community
  • 1
  • 1
karlphillip
  • 92,053
  • 36
  • 243
  • 426
  • Why the -1? This is a **graph theory** problem solvable with **connected component**. There are several implementations of this algorithm out there. – karlphillip Jan 03 '15 at 13:08
  • I added my progress to my initial post. Could you take a look over my code and point me to the right direction in finding my logical error?@karlphillip – greenro Jan 04 '15 at 13:26