get the polygon around a point

[jayhg99]

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

public Polygon getPolygon(Point2D pt){}



Thanks

Jay

[kevglass]

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

Kev

[jayhg99]

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!

[kevglass]

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

[jayhg99]

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

[Jeff]

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.

[swpalmer]

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'

[Jeff]

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.

[ryanm]

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

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. :-/

[jayhg99]

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!

[tom]

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

[swpalmer]

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

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

[Jeff]

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.

[ryanm]

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?

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.

[Orangy Tang]

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.

[tom]

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

[jayhg99]

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

[tom]

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.

[jayhg99]

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

[Jeff]

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

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

[jayhg99]

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

[Jeff]

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.

[tom]

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