How can I find all the pixels enclosed by a 2D polygon (when given the points of the polygon)?
kidluff,
The class java.awt.Polygon has a method contains(int x, int y). You could use this method to test each pixel in the polygon’s bounding rectangle, but it would be very slow.
Maybe someone can think of a cleverer way!
how about filling the polygon and then counting all the pixels that changed color?
Hmm… I need the exact co-ordinates so counting wouldnt work.
The Polygon.contains(x,y) method seems reliable but I would still need to know the pixel cordinates that bound the polygon (the edges).
I was looking up scan-converting… can someone help me out with that? ???
I’d create an appropriately sized BufferedImage, draw the polygon onto it with a known colour, and then use the getRGB( x, y ) method to see which pixels were covered.
The polygon.contains( x, y ) method is likely to be O(n) for an n-sided polygon, so running it in a tight loop is not recommended.
Can you give some more information? Why do you need every pixel? If you tell us what you are trying to do, we might be able to come up with an alternative.
Use the ‘half space’ method; ie find the bound rectangle of the polygon then for each pixel in the rectangle find the the dot product with each side of the polygon. If a pixel is ‘inside’ every edge then it’s inside the polygon:
That is, AFAIK, what the polygon.contains( x, y ) method does. bounds.width * bounds.height * polygon.edges = a lot of dot products to compute.
I agree with CaptainJester, knowing the purpose of this would help. Converting a precise polygon representation into a pixelated approximation seems like an odd thing to do outside of rendering.
Surely all you want is the general polygon filling algorithm.
This will give you a sequence of all the pixels that lie within the Polygons bounds.
Can’t remember the algorithm myself, though I do seem to remember it involves a bucket sort somewhere :
Ok,
Here my scan line converter algorithm in pseudo-code
3 points for you polygon:
x1,y1
x2,y2
x3,y3
first create two int buffer with size=screen height to old xmin and xmax for each line
int bufferXmin[screenHeight];
int bufferXmax[screenHeight];
Get your ymin and your ymax from your three points
ymin=min(y1,y2,y3)
ymax=max(y1,y2,y3)
inititlaise buffer in range from ymin to ymax : with screenWidth for bufferXmin and -1 for bufferXmax (so that xmin>xmax in the range ymin to ymax)
for(int y=ymin;y<ymax:y++)
{
bufferXmin[y]=screenWidth;
bufferXmax[y]=-1;
}
[u][b]
than draw your 3 lines by y and update buffer to find xmin and xmax for each y in the range ymin to ymax, something like that :[/b][/u]
for(y=y1;y<y2;y++)
{
x=x1+(y-y1)*(x2-x1)/(y2-y1);
if(x<bufferXmin[y]) bufferXmin[y]=x;
if(x>bufferXmax[y]) bufferXmax[y]=x;
}
repeat with
for(y=y2;y<y3;y++)
and
for(y=y3;y<y1;y++)
and now you know all pixels covered :
just do:
for(y=ymin;y<ymax;ymax)
{
xmin=bufferXmin[y]
xmax=bufferXmax[y]
for(x=xmin;x<xmax;x++)
{
pixel x,y is covered
}
}
I think that is the fastest method and it is also simple to implement, I will try to send source code later.
dont forget it is a pseudo-code without basic optimisations
ex:
replace
for(y=y1;y<y2;y++)
{
x=x1+(y-y1)*(x2-x1)/(y2-y1);
if(x<bufferXmin[y]) bufferXmin[y]=x;
if(x>bufferXmax[y]) bufferXmax[y]=x;
}
by somthing like that:
coeff1=(x2-x1)/(y2-y1);
x=x1
for(y=y1;y<y2;y++)
{
if(x<bufferXmin[y]) bufferXmin[y]=x;
if(x>bufferXmax[y]) bufferXmax[y]=x;
x+=coeff1;
}
EDIT:
note that before doing final stage you can merge multiple polygone together by repeating all steeps except buffer initialisation
Bruno
I was doing a bit of texture map but I needed to know which pixels in the polygon I was working with.
I think I should try the scan converting like Bruno mentioned.
Check the link I posted, alot of the terms in the dot product are constants per vertial/horizontal row so it’s actually very fast. If the op checks the link he’ll find the texture mapping, lighting, and z buffering are discussed using this method as well.
This is the method I use in my < 4k software renderer.
your algorithm is a smart idea but anyways it could not be faster than scanline converter I posted, wich only need about n loops with few operations inside (n equals poly height).
Bruno