get the polygon around a point

Java 2D
#1

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

public Polygon getPolygon(Point2D pt){}

Thanks

Jay

#2

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

Kev

#3

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

#4

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

#5

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

#6

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.

#7

[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.
[/quote]
Let’s hope that Java2D’s Polygon class uses a “good fast” routine for it’s implementation of ‘contains’

#8

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.

#9

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

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

#10

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

#11

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

#12

[quote]The winding rule flags in PathIterator suggests that contains() will be O( n ), for a n-sided polygon, which isn’t too bad. :slight_smile:
[/quote]
I think it checks a bounding box first, but other than that - yeah it looks like O(n)

#13

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.

#14

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.

#15

[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.
[/quote]
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.

#16

n triangles * O( 1 ) = O( n ). Or am I missing something :slight_smile: 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.

#17

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

#18

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:


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.

#19

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

#20

[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? ???.
[/quote]
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 :slight_smile: