Qbasicnews.com

Full Version: fill point maximum
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3
Quote:
Quote:So, it is a 2D array? Why not just loop through it and test each element...?

Because the fill starts with one point, and proceeds to surrounding, non-block points until there are no points left to fill.

But if you are looking for the most efficient way, a loop would be it.
Yes, a loop is the most efficient way. But not a loop through the entire array each pass. That's ridiculously slow. The loop is composed of active fill points. The fill point maximum is the maximum number of fill points that you need.
At last we know what you mean with fill point maximum! :wink:

A fill point is one connected to the start point, or to a previously found fill point.
So I think the easiest way to get this maximum is to actually fill the shape and count the number of points filled.
The fast Heckbert fill (from Graphics Gems) used by Jark in his TC-Draw would do the job.
It's not the number of points filled, it's the number of points actively filling.

It's not possible to just calculate that by running through, because any fill shape and fill position is possible. The only variables are X and Y...
Quote:It's not the number of points filled, it's the number of points actively filling.

I must be a little stupid.. I still can't understand what you mean.
Any algorithm will fill point by point.Do you mean the maximum number of points a given fill algorithm has stacked as pending to check?

If yes, It would depend on the filling algorithm, I suppose. And that also would be calculated the best by actually filling the shape...
Yes. I should have said "stack" earlier... my algorithm doesn't use a stack... it uses an array. :|

You always need a stack.

I'm talking about some block-point structure and a start point that allows for the maximum number of fill points given x and y.. which is why it's difficult...
Just fill the shape and get the maximum size of the stack...

EDITED:
You can disguise it by using a separate array, but you will end filling it...
But again, the shape is impossible to predict, which is why one has to figure out the most un-efficient shape, in terms of stack size, possible. In terms of time, the maze that I showed would do the trick..
I repeat, all depends on the filling algorithm. I gathered some algorithms and did some testing one year ago.

For example QB's paint is unable to fill all shapes in screen 12, even if you use CLEAR to set the biggest stack possible. The worst case shape with it seems to be a 45º array of dots.

With Heckbert fill you are reasonably safe with a number of stack entries equal to 4*biggest_dimension_of_the_array (2560 entries for a 640x480 screen). The worst case shape seems to be something similar to a Hilbert curve.

For the same algorithm , changing the stack to a FIFO queue reduces a lot the need for stack space...

You could probably do some reasoning to find an exact figure, but you should base it in the algorithm used.

I can post the fill benchmark i did if you are interested.
Doesn't have to be a perfect fill. There are two types of fill:

E W N S and:
E W N S NE NW SE SW

Code:
With Heckbert fill you are reasonably safe with a number of stack entries equal to 4*biggest_dimension_of_the_array (2560 entries for a 640x480 screen).

I think you have to take into account both arrays. Are you talking abut a diamond fill?: (x ^ 2 + y ^ 2)^.5 * 4

Hilbert curve? Wow, that looks like what I had in mind - something wiggly and squiggly! Neat!

Quote:For the same algorithm , changing the stack to a FIFO queue reduces a lot the need for stack space...

You could probably do some reasoning to find an exact figure, but you should base it in the algorithm used.

I can post the fill benchmark i did if you are interested.

Hmm.. can elaborate some more on a FIFO queue...? Just an optimization, or reduces stack entries?

Fill benchmark isn't necessary as my fill isn't really a fill, it's a pathfinding program (which for these purposes isn't the same thing) that works on arrays not on the screen...

This Hilbert curve is just what I'm looking for!
Pages: 1 2 3