Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
fill point maximum
#1
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.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#2
* Has anyone read this?

* Does anyone think this is a worthy challenge?

* Is anyone in pain because of trying to solve this?
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#3
I've read it but it is way out of my league but good luck.
Reply
#4
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.
Reply
#5
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
Reply
#6
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..
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#7
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 ....
Antoni
Reply
#8
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?
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#9
So, it is a 2D array? Why not just loop through it and test each element...?

I must not understand what you are asking...
Reply
#10
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.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)