Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (754) Games in Android Showcase (229) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Finding all the pixels enclosed by a polygon?  (Read 6609 times) 0 Members and 1 Guest are viewing this topic.
kidluff

Senior Newbie

 « Posted 2006-01-13 09:17:19 »

How can I find all the pixels enclosed by a 2D polygon (when given the points of the polygon)?
Mr EEK

Senior Newbie

 « Reply #1 - Posted 2006-01-13 09:36:33 »

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!
noblemaster

« JGO Spiffy Duke »

Medals: 35
Projects: 11

Age of Conquest makes your day!

 « Reply #2 - Posted 2006-01-13 09:40:58 »

how about filling the polygon and then counting all the pixels that changed color?

 Games published by our own members! Check 'em out!
kidluff

Senior Newbie

 « Reply #3 - Posted 2006-01-13 09:49:41 »

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?
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #4 - Posted 2006-01-13 09:51:38 »

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.
CaptainJester

JGO Knight

Medals: 12
Projects: 2
Exp: 14 years

Make it work; make it better.

 « Reply #5 - Posted 2006-01-13 12:31:42 »

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.

nonnus29

Senior Devvie

Giving Java a second chance after ludumdare fiasco

 « Reply #6 - Posted 2006-01-13 13:02:40 »

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:

click
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #7 - Posted 2006-01-13 13:39:02 »

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:

click

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.
Anon666

Junior Devvie

aka Abuse/AbU5e/TehJumpingJawa

 « Reply #8 - Posted 2006-01-13 13:58:47 »

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
DzzD
 « Reply #9 - Posted 2006-01-13 15:02:13 »

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)
 1  2  3  4  5 `for(int y=ymin;y

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 :

 1  2  3  4  5  6 `for(y=y1;ybufferXmax[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:

 1  2  3  4  5  6  7  8  9 `for(y=ymin;y

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
 1  2  3  4  5  6 `for(y=y1;ybufferXmax[y]) bufferXmax[y]=x;}`

by somthing like that:

 1  2  3  4  5  6  7  8 `coeff1=(x2-x1)/(y2-y1);x=x1for(y=y1;ybufferXmax[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

 Games published by our own members! Check 'em out!
kidluff

Senior Newbie

 « Reply #10 - Posted 2006-01-13 15:24:40 »

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.
nonnus29

Senior Devvie

Giving Java a second chance after ludumdare fiasco

 « Reply #11 - Posted 2006-01-13 17:22:49 »

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:

click

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.

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.
DzzD
 « Reply #12 - Posted 2006-01-13 17:58:02 »

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

Pages: [1]
 ignore  |  Print

 DesertCoockie (33 views) 2018-05-13 18:23:11 nelsongames (75 views) 2018-04-24 18:15:36 nelsongames (69 views) 2018-04-24 18:14:32 ivj94 (752 views) 2018-03-24 14:47:39 ivj94 (82 views) 2018-03-24 14:46:31 ivj94 (622 views) 2018-03-24 14:43:53 Solater (98 views) 2018-03-17 05:04:08 nelsongames (179 views) 2018-03-05 17:56:34 Gornova (405 views) 2018-03-02 22:15:33 buddyBro (1065 views) 2018-02-28 16:59:18
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org