CODEWITHSUNDEEP
javamatrixgraphicsfieldflood-fill
user7558351
user7558351

Reputation:

Calculating un-floodfill-able area

I have a 2D array (n * m) as a canvas and coordinates of Used points (startingPoints) in it. I have to calculate, how many points in it is not fieldable with floodfill from outside of the canvas. Field can go only in 4 directions and there are three types of points: Free, Fielded, Used. Used point is not fieldable and field not go over it. So count of unfieldable points is n*m-fieldable-startingPoints.

Now I do it like this: I run floodfill with stack from every point of border and I calculate, how many points are fielded.

But this is not usable for canvas, with dimensions 10^18*10^18. This wants a lot of memory and I must find better solution than using this classic floodfill.

Can someone help with better solution?

Upvotes: 0

Views: 453

Answers (2)

diginoise
diginoise

Reputation: 7620

You could flip the problem on its head and search for points which appear inside of a field by using Point In Polygon technique.

Once you identified such point, you run a flood-fill starting from it. If flood fill ever touches the boundary, then your point and all points filled by this run of flood fill are discarded from the candidates since these are fieldable.

You repeat this procedure by finding points inside fields, which have not yet been filled.

Durring each flood fill you keep the count of filled points, and if given flood fill finishes and none of its leaves are on the boundary you include the count of that fill in the overall count of un-fieldable points.

Upvotes: 1

xtratic
xtratic

Reputation: 4699

I'm not 100% sure I understand what you want.

I'm imagining something like a labyrinth with multiple possible starting points on the outside edge, and you want to know all the possible areas that can be visited/filled from the outside?

The solution to make it more efficient is to cache values so that you don't go recalculating fills that were already calculated.

Make an other 2d array of equal size to keep track of already filled points.

Something like byte[][] filledPoints = new byte[n][m]; initialized with 0 meaning unfilled.

Just for example:

final byte UNFILLED = 0;
final byte RED = 1;
final byte BLUE = 2;

When you do a fill, for each point you visit mark that point with a "fill-color" to say that it was already calculated.

Eg. filledPoints[0][1] = RED

BUT, when doing a fill, if the point you are starting on is already filled, then that whole fill that you are about to do has already been calculated by a previous fill.

if(filledPoints[x][y] != UNFILLED){
    // Then this fill was already filled with the color of filledPoint[x][y]
}

So if it was already calculated then you don't need to calculate it again, so move on to the next starting point that you want to try to fill and check if that is already filled.

When you find a fill area that is not already filled, then start filling it with a new "color", and keep track of the area that gets filled.

Eg. filledPoints[0][386] = BLUE

The un-flood-fillable area is of course the total area minus the sum of all flood filled areas.

Upvotes: 0

Related Questions