Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (563) Games in Android Showcase (151) games submitted by our members Games in WIP (604) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Finding all the pixels enclosed by a polygon?  (Read 3085 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: 21
Projects: 10

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?

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];

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

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

You cannot reply to this message, because it is very, very old.

 wxwsk8er (48 views) 2015-03-20 15:39:46 Fairy Tailz (42 views) 2015-03-15 21:52:20 Olo (26 views) 2015-03-13 17:51:59 Olo (27 views) 2015-03-13 17:50:51 Olo (33 views) 2015-03-13 17:50:16 Olo (40 views) 2015-03-13 17:47:07 ClaasJG (29 views) 2015-03-10 11:36:42 ClaasJG (36 views) 2015-03-10 11:33:01 Pippogeek (45 views) 2015-03-05 14:36:23 Pippogeek (37 views) 2015-03-05 13:56:12
 LiquidNitrogen 23x KevinWorkman 23x BurntPizza 22x basil_ 21x Riven 20x theagentd 19x EgonOlsen 17x Roquen 14x princec 12x Slyth2727 9x NegativeZero 9x Ecumene 9x SHC 9x Varkas 9x ClaasJG 7x teletubo 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 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