+- Qbasicnews.com (http://qbasicnews.com/newforum)
+-- Forum: QbasicNews.Com (http://qbasicnews.com/newforum/forum-3.html)
+--- Forum: Challenges (http://qbasicnews.com/newforum/forum-10.html)
+--- Thread: fill point maximum (/thread-3230.html)
fill point maximum - Agamemnus - 02-17-2004
Many of you know how "filling" an area with a certain color works. As some of you may also know, this is how the simplest pathfinding (search) works, too.
Now, the algorithm in question starts from one single point and moves out until there is nothing left to fill. From that point, 4 (or 8) points around it are checked, and then the points around them are checked, and so on. Call the points-to-be-checked the "fill points": any algorithm stores those fill points for the next iteration.
The challenge is to figure out a precise equation for a fill point maximum, given that the 2D array is of size xmax and ymax.
Assume that the fill progresses in 4 directions: N, S, E, W. (or 8 directions, or both combinations, if you're up to it)
The "block points" would be any points that stop the progression of fill points. On the map, "block points" can be in any combination. The fill point maximum comes from one particular arrangement of block points so that there is a maximum of fill points active at one time.
Here are two possible scenarios: (extremes)
1) No block points. Fill point maximum for that arrangement is:
(x ^ 2 + y ^ 2) * 4
(the fill pattern progresses in a diamond shape)
2) Maze configuration.
Assume that the maze looks like this:
Code:
|=====|
| |
| |=| |
| | |
|===| |
|
======|Thus, this gives a fill point maximum of 2.
fill point maximum - Agamemnus - 02-18-2004
* Has anyone read this?
* Does anyone think this is a worthy challenge?
* Is anyone in pain because of trying to solve this?
fill point maximum - broan496 - 02-18-2004
I've read it but it is way out of my league but good luck.
fill point maximum - PlayGGY - 02-21-2004
I don't quite get what you are asking, especially the stuff abaout "fill point maximum".
When filling a region, the "brute force" method you mentioned is just about the slowest method possible. To fill a convex polygon (all angles are < 180), just find the verticies, and then it is very simple to fill using a simple equation. To fill a concave is harder.
fill point maximum - KiZ - 02-21-2004
Quote:* Is anyone in pain because of trying to solve this?
Er... Kinda? My brain is in pain attempting to understand your challenge. Either I cant understand it, or all that fill point maximum stuff is way beyond me. =D
fill point maximum - Agamemnus - 02-21-2004
Quote:I don't quite get what you are asking, especially the stuff abaout "fill point maximum".
When filling a region, the "brute force" method you mentioned is just about the slowest method possible. To fill a convex polygon (all angles are < 180), just find the verticies, and then it is very simple to fill using a simple equation. To fill a concave is harder.
That's not how you do it at all. I'm not talking about simple mathematical shapes here. I'm talking about a 2D array where the block points (ie: where the fill does not progress) can be anywhere, even randomly dispersed.
Quote:Er... Kinda? My brain is in pain attempting to understand your challenge. Either I cant understand it, or all that fill point maximum stuff is way beyond me. =D
To understand the fill point maximum, first you have to understand how the fill works. Then what a fill point is. Then what a fill point maximum is..
fill point maximum - Antoni Gual - 02-22-2004
If you are challenging us to do a fill function i have one ready.
If you are challenging us to calculate that fill point maximum thing you should elaborate. Most of us have no idea about what it is.
If you are just showing us how clever you are, well ....
fill point maximum - Agamemnus - 02-22-2004
Quote:If you are challenging us to calculate that fill point maximum thing you should elaborate. Most of us have no idea about what it is.
Do you know what I'm talking about?
fill point maximum - PlayGGY - 02-22-2004
So, it is a 2D array? Why not just loop through it and test each element...?
I must not understand what you are asking...
fill point maximum - Agamemnus - 02-22-2004
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.