Rectangle polygon intersection test
Author
I am looking for a good algorithm to do polygon/rectangle intersection tests in 2D. So far everything I have found using Google has some feature that doesn't fit my needs.
I don't want to do clipping, and I don't need the intersection points; I only need a boolean to tell me whether the rectange and polygon actually intersect.
My polygon is not necessarily convex, but it will not have any self-intersections. It may have holes though. Most of the stuff I have found involves convex polygons. My rectangle is always axis aligned.
Essentially what I am looking for is the algorithm used in the RectInRegion() Win32 GDI function as this is what I am adapting the code from, but I no longer have any GDI stuff.
Thanks
Hm. I have no idea what sort of approach functions like RectInRegion() use - intersection testing with arbitrary polys (especially ones with holes) is tricky.
This probably isn't what you want to hear, but can you decompose your arbitrary poly into convex polys? Intersection testing between convex objects is a solved problem, and if needed you could also do some optimizations based on a priori knowledge about the collection of convex polygons that make up a single arbitrary polygon (i.e. shared edges and so on).
Other than that, I'm not sure what method you could employ that would catch all cases (which doesn't mean there isn't one - I just can't think of what it would be).
This probably isn't what you want to hear, but can you decompose your arbitrary poly into convex polys? Intersection testing between convex objects is a solved problem, and if needed you could also do some optimizations based on a priori knowledge about the collection of convex polygons that make up a single arbitrary polygon (i.e. shared edges and so on).
Other than that, I'm not sure what method you could employ that would catch all cases (which doesn't mean there isn't one - I just can't think of what it would be).
Quote:I am looking for a good algorithm to do polygon/rectangle intersection tests in 2D.It is quite simple really, given a target object you need only test against the edges of the intersecting geometry.
If the intersecting geometry crosses with your static geometry it's as simple sa it gets.....
What you want is probably to generate a bounding rectangle from a source mesh and heirachichally match this to the geometry stored.
I'm too drunk to describe details. If you need them reply to this post.
hth
Jack
That's the naive approach - it won't catch all cases. Specifically, the hardest case to determine is if the rectangle is completely contained within some portion of the polygon. In this case no edge of the polygon will intersect with the rectangle, and the test will erroneously return false.
However, if you happen to know that the polygons will always be small in relation to the rectangles, you might be able to get away with just testing the edges of the poly against the rectangle (not against the edges of the rect, but against its area - otherwise you will also miss cases where the poly is completely contained within the rect).
However, if you happen to know that the polygons will always be small in relation to the rectangles, you might be able to get away with just testing the edges of the poly against the rectangle (not against the edges of the rect, but against its area - otherwise you will also miss cases where the poly is completely contained within the rect).
Question: How can you have a polygon with holes without self-intersection?
jollyjeffers is right, you'd probably want to make a simple bounding box around the polygon yet, and do a box/box intersection for a quick out (if the box and the polygon's bounding box don't intersect, then you don't have to do the more in-depth test).
Then you'd want an algorithm something like this:
So the first chunk of the test covers cases where there are actually intersections, then the next two cases cover the one object is within the other cases.
Hope that does the trick for you! It's not the greatest algorithm ever, but it does the trick! :)
jollyjeffers is right, you'd probably want to make a simple bounding box around the polygon yet, and do a box/box intersection for a quick out (if the box and the polygon's bounding box don't intersect, then you don't have to do the more in-depth test).
Then you'd want an algorithm something like this:
for each edge in the polygon if (edge intersects rectangle) return INTERSECTSend for// Catch the "polygon completely within the box" caseif (polygon.first_point is in rectangle) return INTERSECTS// Catch the "box completely within the polygon" caseif (box.upper_left_corner is in polygon) return INTERSECTSreturn NO_INTERSECTSo the first chunk of the test covers cases where there are actually intersections, then the next two cases cover the one object is within the other cases.
Hope that does the trick for you! It's not the greatest algorithm ever, but it does the trick! :)
Point-in-rectangle tests are fast and easy, so start with those: test each vertex of the polygon to see if it lies within the rectangle. If one of them does, you're done - there is an overlap.
Then, you can do some easy tests based on the Jordan curve theorem to see if any of the rectangle vertices fall inside the polygon. Basically, send an arbitrary feeler in an arbitrary direction from the rectangle vertex in question. If it crosses an odd number of edges (or vertices) belonging to the polygon, then the rectangle vertex is inside the polygon, and you can stop testing. The great thing is, this feeler can be axis-aligned; so any horizontal or vertical line will work. If you precompute the edges of your polygon in slope/intercept form it is very easy to tell if the edges will hit the feeler or not.
Depending on how complex your polygons are (say, more than 15-20 edges apiece) you can probably do some sneaky optimizations, like creating a polygon composed entirely of right angles that fully overlaps the original poly (not hard). Then decompose that into a series of rectangles (again not hard, and easy to do in a preprocessing step). Use some well-documented geometry to reduce that set of rectangles (again in a preprocessing step) into a near-minimal set required to represent the region. Finally, test your subject rectangle against that set of rectangles first before doing any more detailed tests. However all this work is thoroughly wasted time if your polygons are not terribly complex.
Then, you can do some easy tests based on the Jordan curve theorem to see if any of the rectangle vertices fall inside the polygon. Basically, send an arbitrary feeler in an arbitrary direction from the rectangle vertex in question. If it crosses an odd number of edges (or vertices) belonging to the polygon, then the rectangle vertex is inside the polygon, and you can stop testing. The great thing is, this feeler can be axis-aligned; so any horizontal or vertical line will work. If you precompute the edges of your polygon in slope/intercept form it is very easy to tell if the edges will hit the feeler or not.
Depending on how complex your polygons are (say, more than 15-20 edges apiece) you can probably do some sneaky optimizations, like creating a polygon composed entirely of right angles that fully overlaps the original poly (not hard). Then decompose that into a series of rectangles (again not hard, and easy to do in a preprocessing step). Use some well-documented geometry to reduce that set of rectangles (again in a preprocessing step) into a near-minimal set required to represent the region. Finally, test your subject rectangle against that set of rectangles first before doing any more detailed tests. However all this work is thoroughly wasted time if your polygons are not terribly complex.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
