Sign in to follow this  
AuthenticOwl

Find flood fill boundries

Recommended Posts

AuthenticOwl    363
I am having some trouble determining an efficent algorithm to find the size and location of a square containing all the cells within a region determined by a flood fill when the grid wraps...
[pre]
I.E:
Fig A. Fig B.
..... ......
.XX.. X...XX
..XX. X....X
...X. ......
[/pre]
Fig.A: Containing box (1,1)->(3,3)

Fig.B: Containing box (4,1)->(6,2)

Share this post


Link to post
Share on other sites
JohnnyCode    1046

loop through each cell, and globaly remember a cell-of cycle lowest X towards global current X minimum and towards global currwent X maximum, as well as for the Y.

 

var minimalX,minimalY=999999999;

var maximalX,maximalY=-1;

 

foreachcell (as cell)

{

if (cell.x<minimalX)

   minimalX=cell.x;

if (cell.y<minimalY)

   minimalY=cell.y;

if (cell.x>maximalX)

   maximalX=cell.x;

if (cell.y>maximalY)

   maximalY=cell.y;

}

 

 

determining an efficent algorithm to find the size and location of a square containing all the cells within a region

It is much the same problem as finding an axis aligned bounding box or axis aligned bounding sphere upon verticies, 2d or 3d

Share this post


Link to post
Share on other sites
Waterlimon    4398

Start with all-encompassing rectangle.

 

You now need to perform 2 actions:

1. Cut a section off vertically

2. Cut a section off horizontally

(Section can wrap so the 2 halves of the section youre cutting off might be on different sides of the non-wrapped view)

Examples for vertical section cut (X=box, _=cut off from box):

XXXX => _XX_

XXXX => X__X

XXXX =>XX__

 

After doing these ops you should be left with a box.

 

You need to find an algorithm to get the size/location of the two sections (one along y other along x)

This should be fairly trivial to do using brute force. You can view the entire map as one dimensional array of booleans, so if youre cutting a vertical section, each 'column' of the map would either be true (column contains X) or false (doesnt contain X). Then youd find the longest string of false to get the coords for the section to cut off. Repeat for horizontal cut.

 

If you use the above algorithm the most costly part would probably be reducing the map to 2 one dimensional boolean arrays (columns and rows) so it would scale O(n) with the amount of cells in the map (since you need to iterate over all of them and set the corresponding booleans in both vertical and horizontal one dimensional array to true if you find an X)

 

The final step is to take the two sections you cut off and calculate the actual box from them, which shouldnt be difficult (just some min/max function calls I believe)

 

So:

 

int mapX,mapY; //map size

bool mapShadowX[mapX],mapShadowY[mapY]; //init to false

//calculate one dimensional 'shadow' for horizontal and vertical dir

for all map cells:

if cell=='X' then set mapShadowX[cell.x]=true; mapShadowY[cell.y]=true;

end for

Section sectionX,sectionY; // contain int a,b; - section goes from some coordinate to some other coordinate in single dimension

//Find longest string of 'false' in both mapShadow arrays, taking wrapping into account, save begin and end of this string to corresponding section

//The wrapping part requires special code to handle the case where lengths of the first and last string of 'false' should be summed to get the actual length for that

//Use sectionX.a etc. which you calculated to get information about the box you wanted to find. Example:

vector2 topLeftCorner = vector2(min(sectionX.a,sectionX.b), min(sectionY.a,sectionY.b)) //Find top left corner of box in nonwrapped coords where X goes right and Y down

 

You can optimize this to some extent too.

 

EDIT:

 

no wait find the longest string of TRUE so sectionX and sectionY will directly describe the box and not the area cut off. I guess one way is optimal (find FALSE string if the box is most of the map?)

Edited by Waterlimon

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this