Jump to content

  • Log In with Google      Sign In   
  • Create Account


Finding enclosed tiles


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Tom KQT   Members   -  Reputation: 1506

Like
0Likes
Like

Posted 24 November 2011 - 12:14 PM

Hi,
I'm looking for a way how to detect areas on a grid (hex in my case, but I guess the basic principle would be the same for squares) that are fully enclosed by specific tiles ("walls").
Check the picture for better understanding - that's a random situation, dark blue tiles are the "walls" and bright green are areas (tiles) that I am trying to find. There can be more areas, I need to find all of them.

What came to my mind first was flood fill, but that works from a starting point, which I don't know - I don't know which tile can potentially be in the enclosed area (well, almost all tiles can be).
Then I thought I could simply do the opposite and flood fill the other tiles (white), which would leave the green tiles. But if I started for example in the upper left corner on the picture, the fill would stop very soon.

Do you have any suggestions how this could be done effectively?

Thank you very much for any input.

Tom

Posted Image

Sponsor:

#2 jwezorek   Crossbones+   -  Reputation: 1621

Like
1Likes
Like

Posted 24 November 2011 - 02:15 PM

The search term you need for googling purposes is "connected component labeling" ... The easiest way to do it is to

1. Construct a temporary blank grid.
2. Iterate over the cells of the input grid.
3. For each cell A that is not blue ( in your case ) and that hasn't been marked as discovered do the following
.......... Output A as a seed of a unique connected component.
.......... Perform a floodfill seeded at A that marks the cells of the connected component that A is part of as 'discovered' in the temporary grid.

There are more efficient ways of doing this but probably the above will suffice unless your grids are gigantic.

#3 Tom KQT   Members   -  Reputation: 1506

Like
0Likes
Like

Posted 24 November 2011 - 02:40 PM

Thx, that sounds good, I'll give it a try.
No, the grid isn't going to be huge, I don't know the exact dimensions yet but it will be something like 2x - 4x the size on the image.

#4 taz0010   Members   -  Reputation: 256

Like
0Likes
Like

Posted 25 November 2011 - 02:05 AM

Just add every node to an "unvisited" list. Store in each node a pointer (or iterator) to it's counterpart in this list. Now the process is to:

1) Pop a node off the unvisited list and create a new list with the node as it's first element
2) Visit each neighbour of the node, recursively (i.e. flood fill), add them to the current list, and remove from the unvisited list (as each node has a pointer to it's location in the unvisited list, this is O(1)).
3) One of two things will occur; The flood fill will either terminiate, in which case you output the list as fully enclosed, or you'll hit the outer wall, in which case you discard the list as it's not enclosed. In either case, you return to step 1) and repeat until the unvisited list is empty.


This algorithm is O(n) with respect to the number of nodes.



#5 taz0010   Members   -  Reputation: 256

Like
0Likes
Like

Posted 25 November 2011 - 03:29 AM

If you want to optimise this solution, you can roll your own list structure that's backed by an array. Insert and delete operations can then be performed without allocation/deallocation, which will speed things up by a great amount. In fact you don't even need separate lists for each set of nodes. You can build the other lists inside the memory of the initial allocation, which allows this algorithm to run with a grand total of 1 call to new and delete.

#6 Tom KQT   Members   -  Reputation: 1506

Like
0Likes
Like

Posted 04 December 2011 - 05:17 AM

Thank you very much, both of you. I managed to implement it succesfully.

The search term you need for googling purposes is "connected component labeling" ... The easiest way to do it is to

1. Construct a temporary blank grid.
2. Iterate over the cells of the input grid.
3. For each cell A that is not blue ( in your case ) and that hasn't been marked as discovered do the following
.......... Output A as a seed of a unique connected component.
.......... Perform a floodfill seeded at A that marks the cells of the connected component that A is part of as 'discovered' in the temporary grid.

There are more efficient ways of doing this but probably the above will suffice unless your grids are gigantic.


The key here indeed was the connected-component labeling (http://en.wikipedia....ponent_labeling). I used only it, modified for hexa grid.

It's all done in two passes (by the CCL), I'm not performing any floodfill, so it's pretty straightforward.

#7 davepermen   Members   -  Reputation: 1007

Like
0Likes
Like

Posted 05 December 2011 - 05:19 AM

i have not read up on the other solutions, but just to think about your reverse flood fill: if you would fill the top left, everything else would be "enclosed". why aren't the white ones enclosed, though? because they have one at the edge.

so simple solution would be to surround the whole grid with a white one tile big border, and floodfill that. then reverse.

i guess the other solution is better, but this is just an idea to solve your theoretical issue from the first post.
If that's not the help you're after then you're going to have to explain the problem better than what you have. - joanusdmentia

My Page davepermen.net | My Music on Bandcamp and on Soundcloud





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS