Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
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  
  get the polygon around a point  (Read 2742 times)
0 Members and 1 Guest are viewing this topic.
Offline jayhg99

Senior Newbie




Java games rock!


« Posted 2003-11-03 14:02:19 »

I wonder if anyone knows how to retrive a 2D polygon around a point ?  Something  like :

public Polygon getPolygon(Point2D pt){}



Thanks

Jay
Offline kevglass

JGO Kernel


Medals: 186
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #1 - Posted 2003-11-03 14:03:44 »

Do you mean you want to get a "regular" polygon of a given number of sides centered on a point?

Kev

Offline jayhg99

Senior Newbie




Java games rock!


« Reply #2 - Posted 2003-11-03 14:44:45 »

I want to be able to detect a ploygon surround a point if there is any.  For example, if I do a mouse click, I would like to get back a  ploygon surround that point if there is one or null if there is none.



Jay
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline kevglass

JGO Kernel


Medals: 186
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #3 - Posted 2003-11-03 14:58:35 »

Ah ha, and how are you going to define where these polygons are originally? Java 2D doesn't store any scene information, it simple draws the graphics context.

You'll have to code this sort of detection in. I.e. store a list of the polygons you've drawn. When the user clicks cycle through the polygons using contains() to check if the MouseEvent.getPoint() is inside the polygon.

Kev

Offline jayhg99

Senior Newbie




Java games rock!


« Reply #4 - Posted 2003-11-03 15:20:10 »

That's what I thought. I was just trying to avoid to keep track all the polygons drawn on the screen and the intersections among all the polygons.




Jay
Offline Jeff

JGO Coder




Got any cats?


« Reply #5 - Posted 2003-11-03 23:14:23 »

You will have to walk a list of your polys until you find one where the point in question is interior to the polygon.  

How you determine whether a point is inside or outside the poly depends on thinsg like whether all your polys are convex or not.

There are good fast routines for doing a point inclusion  test on a plygon in the Graphics Gems series of books-- a must have for any game developer.


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #6 - Posted 2003-11-03 23:56:36 »

Quote
There are good fast routines for doing a point inclusion  test on a plygon in the Graphics Gems series of books-- a must have for any game developer.


Let's hope that Java2D's Polygon class uses a "good fast" routine for it's implementation of 'contains'

Offline Jeff

JGO Coder




Got any cats?


« Reply #7 - Posted 2003-11-04 06:44:18 »

Quote


Let's hope that Java2D's Polygon class uses a "good fast" routine for it's implementation of 'contains'


Hmm. Would be nice to hope.  Its always a good place to start (and thanks I had forgotten it was there)  but if when you profile you find its a bottleneck you may want to look  for other solutions where you control the algorithym in use.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #8 - Posted 2003-11-05 07:55:40 »

The winding rule flags in PathIterator suggests that contains() will be O( n ), for a n-sided polygon, which isn't too bad. Smiley

Off the top of my head, you might be able to get better asymptotic performance by splitting the polygon into triangles and testing against the triangles, but the extra overhead would probably negate any speedups in most cases.  Plus it would only work for convex polygons. :-/
Offline jayhg99

Senior Newbie




Java games rock!


« Reply #9 - Posted 2003-11-05 18:14:21 »

What if I just need to fill colors for a map, pretty much like coloring book.  Is there any better way to do it other than try to detect polygons within the map ?


Jay

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #10 - Posted 2003-11-05 18:50:45 »

What is this map? Is it an image, or a list of polygons that you draw? How do you create the map? Can you explain exactly what you are trying to do?

If you have an image, and you want to fill the inside of a border with a color, you can use a flood-fill. There is another topic on that in the forum: http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=Offtopic;action=display;num=1066999281


Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #11 - Posted 2003-11-05 23:55:24 »

Quote
The winding rule flags in PathIterator suggests that contains() will be O( n ), for a n-sided polygon, which isn't too bad. Smiley

I think it checks a bounding box first, but other than that - yeah it looks like O(n)

Offline Jeff

JGO Coder




Got any cats?


« Reply #12 - Posted 2003-11-06 02:02:54 »

Hmm.  Last time I implemented point inclusion I used a different approach I think.  Basically I draw a horizontal line through the point and did a fast (optimized) line v. line intersection and counted the number of intersections from one edge of the screen til the point.

It was a GraphicsGems solution and was pretty damn fast given the optimized line intersection that I ALSO got out of GG.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline ryanm

Senior Duke


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #13 - Posted 2003-11-06 06:48:54 »

Isn't that still going to be O( n )? You would have had to test with intersection for each line segment in the polygon.

Or am i missing something? Huh

The faster method is to split the polygon into n  triangles and test each triangle to see if it contains the point ( O( 1 ) operation ).

Best case scenario ( point is in first triangle tested ) is O( 1 ),
Worst case scenario ( point is not in polygon ) is O( n ).

However, it only works for convex polygons.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #14 - Posted 2003-11-06 07:20:26 »

Quote
The faster method is to split the polygon into n  triangles and test each triangle to see if it contains the point ( O( 1 ) operation ).

Best case scenario ( point is in first triangle tested ) is O( 1 ),
Worst case scenario ( point is not in polygon ) is O( n ).

However, it only works for convex polygons.

Uh, if it only works for convex polys then why even bother chopping it up into triangles? Just do an inside/outside test against each edge, and if its inside all of them the point is inside. That gets you O(n) and approx.  ?(n/2) since if it fails any edge test you can exit early.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline tom
« Reply #15 - Posted 2003-11-06 07:28:04 »

Quote

The faster method is to split the polygon into n  triangles and test each triangle to see if it contains the point ( O( 1 ) operation ).  


n triangles * O( 1 ) = O( n ). Or am I missing something  Smiley  In addition there will be a lot more edges to test. Since when you split a polygon into triangles you get more edges.

The fastest way is of course to use a higher level data structure. Like a BSP tree, oct tree or something similar. So that you don't check every polygon.

Offline jayhg99

Senior Newbie




Java games rock!


« Reply #16 - Posted 2003-11-06 11:47:11 »

Tom,  basically, I need to implement the same function as "fill with color tool" of MS paint. Draw any polygons on a canvas and then selectively fill them with colors after all the polygons are drawn on the canvas.

Try to find a better way to do it without keeping track of all the polygons drawn and their intersections.


Jay
Offline tom
« Reply #17 - Posted 2003-11-06 14:00:44 »

MS paint uses a flood fill. But this algorithm has nothing to do with polygons. It uses the image itself to find out where to fill. The flood fill is recursive and might look something like this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
void floodFill(int x, int y, int fillColor, int borderColor) {

 // return at border
 if (image(x, y) == borderColor)
  return;
 }
 
 // draw color at current pixel
 image(x, y) = fillColor;

 // go right
 floodFill(x+1, y, fillColor, borderColor);

 // go left
 floodFill(x-1, y, fillColor, borderColor);

 // go down
 floodFill(x, y+1, fillColor, borderColor);

 // go up
 floodFill(x, y-1, fillColor, borderColor);
}


This means you have to get hold of the Image pixels of the polygons you drew. You can do this by drawing the polygons on a offscreen image. Then use java.awt.image.PixelGrabber to get the pixels.

I can go into more detail if it sounds like what you are looking for.

Offline jayhg99

Senior Newbie




Java games rock!


« Reply #18 - Posted 2003-11-06 15:28:09 »

Thanks tom. That's what I need. I'll go around the thread  http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=Offtopic;ac tion=display;num=1066999281


Jay
Offline Jeff

JGO Coder




Got any cats?


« Reply #19 - Posted 2003-11-06 18:56:50 »

Quote
Isn't that still going to be O( n )? You would have had to test with intersection for each line segment in the polygon.

Or am i missing something? Huh.


Well, what you MAY be missing is that Order is really a scalabaility measure, its less relevent for small Ns then for big Ns.

And that tehre is an INCREDIBLY efficvient way to do line v. line intersection tests.  Again, see GraphcisGems, its really the best source for these kinds of geometric things as its hints culled from some of the best computaional geometricists in the country Smiley


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline jayhg99

Senior Newbie




Java games rock!


« Reply #20 - Posted 2003-11-07 14:51:53 »

Thanks Tom for leading me to flood fill. I think that I understand basically how flood fill works.

But how can I detect a border color?   For instance, if a polygon has 12 line segments and each line segment has a different color. In order to  fill this polygon with a color using flood fill ,  I have to detect all 12 colors and keep track each pixel as the color filling moves toward the polygon border.


Jay
Offline Jeff

JGO Coder




Got any cats?


« Reply #21 - Posted 2003-11-07 19:03:42 »

If you are trying to fill a vector polygon I would FIRST look to see if your polygona renderer has it  built in. (I know Java2D for instance has drawFilledFoo  functions.  Thats going to be the fastest solution because the filling as part of the rasterization is pretty trivial.  If yo uwant to provide a "refill op I'd just draw the enw fileld oply over the old one.

If for some rason though you HAVE to do it as a flood fill then yo uare going to have to do "contains" ops for every point which will be expensive.  Yo uca pergapse optimzie a it by doing a "contains" on your first point and then just doing edge/point intersection tests on the subsequent points (see Graphcis Gems).

You might even be able to optimize this with a clever solution, like doing line/edge tests  against a screen wide line for each new Y value and then alternately filling he lines between inetrsections.

In the end though NONE of this will be as good or fast as the rasterizer, particualrly  since the rasterizer these days is generally hardware accelerated.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline tom
« Reply #22 - Posted 2003-11-09 19:24:55 »

Quote
But how can I detect a border color?   For instance, if a polygon has 12 line segments and each line segment has a different color. In order to  fill this polygon with a color using flood fill ,  I have to detect all 12 colors and keep track each pixel as the color filling moves toward the polygon border.

Usually the fill tools in painting programs are used to replace a color in an Image. Then the border is any color that is not the one that is replaced.

If that don't apply to you, you can draw the polygons line segments to another off-screen buffer. Where the background is white and the line segments are black. Then you can use this buffer when you fill.

But, Yes, You have to know where the border is and you have to know where you have filled. Exactly how this is done depends on your application, as there are a lot of ways of doing this.

Jeff: I agree that flood fill is not the way to go if you only want to fill a single polygon. However, I enterprated the problem as first drawing one or more, possibly self intersecting, overlapping polygons, and then fill inside like a flood fill. Doing this with using polygons you would have to "AND" all the polygons that contains the start point (meaning finding the area that all the polygons overlap), and then "subtract" the rest. Either useing contains on all polygons for each pixel, or using clipping. I thought it would be easier to use a flood fill Smiley

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.

Longarmx (38 views)
2014-10-17 03:59:02

Norakomi (28 views)
2014-10-16 15:22:06

Norakomi (24 views)
2014-10-16 15:20:20

lcass (28 views)
2014-10-15 16:18:58

TehJavaDev (55 views)
2014-10-14 00:39:48

TehJavaDev (55 views)
2014-10-14 00:35:47

TehJavaDev (44 views)
2014-10-14 00:32:37

BurntPizza (64 views)
2014-10-11 23:24:42

BurntPizza (36 views)
2014-10-11 23:10:45

BurntPizza (78 views)
2014-10-11 22:30:10
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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!