Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
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 2940 times)
0 Members and 1 Guest are viewing this topic.
Offline 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)?
Offline 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!
Offline noblemaster

« JGO Spiffy Duke »


Medals: 20
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?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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? Huh
Offline 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.
Offline 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.

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

Ok,

Here my scan line converter algorithm in pseudo-code Smiley

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<ymax:y++)
{
 bufferXmin[y]=screenWidth;
 bufferXmax[y]=-1;
}



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


1  
2  
3  
4  
5  
6  
7  
8  
9  
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
1  
2  
3  
4  
5  
6  
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:


1  
2  
3  
4  
5  
6  
7  
8  
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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline 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.
Offline 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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (29 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (40 views)
2014-12-09 22:41:13

BurntPizza (75 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (50 views)
2014-12-03 16:27:13

CopyableCougar4 (47 views)
2014-11-29 21:32:03

toopeicgaming1999 (113 views)
2014-11-26 15:22:04

toopeicgaming1999 (100 views)
2014-11-26 15:20:36

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!