Fill Shape
need help writeing method fillShape that takes in a 2D array of shapes and points(in other words it will draw the shape and fill it in into my Screen array(ex: Color[][] String = new Color[700][1000]) basicly a 2D array of colors which are painted in my paint method... anyways im sent this 2D array of shapes and their points(ex: int[][] shapes = {{0,0,0,10,10,10,10,0}{0,0,-10,0,-10,-10,0,-10}}) it will go through the array drawing the shapes and filling them in like this:
int x=0 ;
int y=0;
int x2=0;
int y2=0;
for(int i =0;i<shapes.length;i++)
for(int k =0; k><shapes[i].length;k+=2)
{
x2 =x;
y2=y;
x = shapes[i][k];
y = shapes[i][k+1];
if(k>0)
{
//code goes here
}
}
of course i have yet to figure out how im going to do this because im not using a graphics object. i want to be able to draw this filled shape into the screen array... if anyone can help...
if its not clear enough.... basicly i want to do the whole GeneralPath/fill(generalPathObject) thing in an array instead of a graphics object
[1574 byte] By [
sosleepya] at [2007-10-2 22:00:44]
the standard simple polygon filling algorithm works like this.
You grovel over the list of point that make up the polygon to locate verticies that are minimums and maximums (in the y direction)
The sequence of points between a min and a max we will call a wall.
Your polygon is now a list of walls. The important thing to notice about a wall is that being an essentially vertical polyline, it is a single valued function: given a y value ( a horizontal line) it intersects the wall at only one point.
For a moment, don't worry about how you implement that function. it is just x = wall.getX(y); technically, it needs to do just a bit more, in that a wall could be completely above or below a given y value. You will see later on that it is ok to return the x value of the min or the max point if you are asking for a y value that is beyond the y of the min or max point.
Now consider any single y value (a horizontal line) as it zips across the polygon it will intersect each different wall at a different x value (or possibly the same if the walls intersect).
If you sort those x values, you get a list of points. The lowest x value will be the left edge of the polygon so that is where you want to start filling. The next x marked some wall where you want to stop filling. the next x marks the next place to start filling ...
You just treat the x value list as a set of on off on off switches that tell you where to fill across that horizontal line.
This is known as xor fill. It is not the most desireable but it is easy to code. It means the places where a polygon self intersects will not be filled. There is an alternattive know as Winding Number fill that fills in the places where a polygon self intersects.
To calculate winding number, the array of x values that you sort must also keep track of the direction of the wall (walls that went from min to max are +1 walls that went from max to min are -1 - or the other way around. It does not matter)
Now as you draw across the array of xs you keep a counter that is just the sum of the directions numbers that you have seen. This time, instead of treating the x values as on off on off, you treat them as on whenever the xvalue made the count non-zero, and off when they made the count zero.
So now you are thinking, that you will just keep an array of the walls themselves (because they know what direction they are and they can return x values and can be sorted by those x values).
You start at the top of the screen y value, and for each successive y value you generate the xlist, sort it, and fill in the horizontal segments.
Now, how do you find the x value for a given basically vertical line segment? if you don't know how to do that, then you do not know enough algebra and coordinate geomerty to be working on a graphic algorithm.
When you go to compute the x values based on the y it is helpful to notice that since you are always progressing from one y value, Y to the very next one at Y+1, the next X value will be
NewX = PreviousX + 1/(slopeOfWall).
Draw the picture if you must to see this. Beware of division by zero.
For a good time google, bresenham line algorithm. It will tell you how to do all your line calculation in integer arithmetic, if you care.
Enjoy
