algorithm for determining if plygons overlap?

[notfred]

Assume you have two sets of points (each point is an X,Y pair). When plotted, and connected with line segments, each set of points forms a polygon.

Is there an algorithm that can be used to determine if one of the polygons overlaps the other?

 

[RichieZ]

i suppose you could calculate all the points in one polygon and then do the same thing as the ray intersection test that you do in ray tracing. its kind of a crappy solution though

I think we might have covered this in my computer graphics class but its been a while


edit:
oops never mind i didn't see that its only 2d

 

[Barnaby W. Füi]

http://gamedev.net/community/forums/topic.asp?topic_id=253702

 

[DrPizza]

If you have only 2 polygons, I'd just test it segment by segment for overlap.
I'm kicking myself trying to remember, but it seems there was something relatively simple in linear algebra that you could set up to check. Hmm.... maybe it was with vectors (dot products, cross products etc.) I just can't think of it at the moment.


Regardless, I'll bet it would make an interesting problem to set up a very fast algorithm to do so.

 

[notfred]

I should clarify that I don't simply want to test to see if line segments cross, but to see if the area contained inside one polygon overlaps another. Basically, see if filled ploygons overlap.

 

[DrPizza]

there are only 2 cases to consider for polygon overlap - 2 or more segments have an intersection, OR every point in one polygon is within the other polygon. It would be sufficient to test only 1 point to check the latter case.

 

[Cipherous]

if there are any intersections between any pair of points (1st polygon) with another pair of points (2nd polygon), then the polygons over lap.

 

[notfred]

Originally posted by: Cipherous
if there are any intersections between any pair of points (1st polygon) with another pair of points (2nd polygon), then the polygons over lap.

Not if one polygon lies entirely inside another.

there are only 2 cases to consider for polygon overlap - 2 or more segments have an intersection, OR every point in one polygon is within the other polygon. It would be sufficient to test only 1 point to check the latter case.

HOw do I determine if a point is inside a polygon?

 

[Spencer278]

Originally posted by: notfred

Originally posted by: Cipherous
if there are any intersections between any pair of points (1st polygon) with another pair of points (2nd polygon), then the polygons over lap.

Not if one polygon lies entirely inside another.

there are only 2 cases to consider for polygon overlap - 2 or more segments have an intersection, OR every point in one polygon is within the other polygon. It would be sufficient to test only 1 point to check the latter case.

HOw do I determine if a point is inside a polygon?

The simplest way would just be to check if any point is inside the polygon. Which means the X and Y will be bounded by the X and Y values of the other polygon.

 

[notfred]

Originally posted by: Spencer278

Originally posted by: notfred

Originally posted by: Cipherous
if there are any intersections between any pair of points (1st polygon) with another pair of points (2nd polygon), then the polygons over lap.

Not if one polygon lies entirely inside another.

there are only 2 cases to consider for polygon overlap - 2 or more segments have an intersection, OR every point in one polygon is within the other polygon. It would be sufficient to test only 1 point to check the latter case.

HOw do I determine if a point is inside a polygon?

The simplest way would just be to check if any point is inside the polygon. Which means the X and Y will be bounded by the X and Y values of the other polygon.

And how do I do that? Is there some algorithm I can use to compare points and see that one point lies inside a polygon made by the others?

 

[Matthias99]

Originally posted by: notfred

Originally posted by: Spencer278

Originally posted by: notfred

Originally posted by: Cipherous
if there are any intersections between any pair of points (1st polygon) with another pair of points (2nd polygon), then the polygons over lap.

Not if one polygon lies entirely inside another.

there are only 2 cases to consider for polygon overlap - 2 or more segments have an intersection, OR every point in one polygon is within the other polygon. It would be sufficient to test only 1 point to check the latter case.

HOw do I determine if a point is inside a polygon?

The simplest way would just be to check if any point is inside the polygon. Which means the X and Y will be bounded by the X and Y values of the other polygon.

And how do I do that? Is there some algorithm I can use to compare points and see that one point lies inside a polygon made by the others?

Not trivially, except for special cases (triangles, rectangles, some regular n-sided polygons -- although you can break almost any polygon down into triangles). Try searching under "convex hull" algorithms for a start. If your polygons are convex, that would be all you'd need... but if they're allowed to be concave and/or self-intersecting, you have to do more sophisticated searching. This is a common problem in computer graphics (this is how z-culling works in 3D rendering, for instance), and has been researched to death, so there should be plenty of info on the web.

It's pretty easy to tell if a point is *not* inside a polygon (or at least not even close) by just finding the minimum and maximum x and y values for the polygon (that is, the minimum bounding rectangle) and seeing if the point is inside that rectangle. However, if it's in the bounding rectangle, you still need to check it more thoroughly against the actual boundaries to see if it's really inside. For two full polygons, you can find the bounding rectangles for both and see if they intersect -- if they don't, the polygons definitely don't either, and if one is completely contained inside the other, they must overlap. You can also use bounding ellipses -- these are a bit tougher to compute, but can be checked very quickly, and are much more accurate for polygons that aren't aligned on the x and y axes. Determining actual intersection requires, AFAIK, comparisons between the line segments. The math boils down to expressing the polygon as a set of lines and finding points that are on the 'interior' side of each line.

We did some of this in my graphics class back in school, but it's been a few years. If you have more specific questions, I can try to rack my brain a bit more, or dig through my textbook.

 

[notfred]

OK, I found an algorithm that is ridiculously simple for determining if a point lies inside a polygon. This works for convex, concave and self-intersecting polygons. Take your point and draw a ray from that point to infinity in any direction. To make this easy, say we draw the ray vertically. Count how many times that ray crosses a line segment of your polygon. If the number of times it crosses is even the point is outside the polygon. If the number of times it crosses is odd, the point is inside the polygon.

 

[Matthias99]

Originally posted by: notfred
OK, I found an algorithm that is ridiculously simple for determining if a point lies inside a polygon. This works for convex, concave and self-intersecting polygons. Take your point and draw a ray from that point to infinity in any direction. To make this easy, say we draw the ray vertically. Count how many times that ray crosses a line segment of your polygon. If the number of times it crosses is even the point is outside the polygon. If the number of times it crosses is odd, the point is inside the polygon.

Ah, I'd forgotten about that one. That works, although it can be slow on extremely large polygons.

 

[Armitage]

Originally posted by: notfred
OK, I found an algorithm that is ridiculously simple for determining if a point lies inside a polygon. This works for convex, concave and self-intersecting polygons. Take your point and draw a ray from that point to infinity in any direction. To make this easy, say we draw the ray vertically. Count how many times that ray crosses a line segment of your polygon. If the number of times it crosses is even the point is outside the polygon. If the number of times it crosses is odd, the point is inside the polygon.

That's fine, but what point do you choose to test? The polygons can intersect without any vertices lying within the other polygon. It's a good test to see if it is completely contained within the other though.

 

[Armitage]

I'd probably do a multi-step algorithm. Start with the really simple & fast stuff first...

1. Does the Y range of polygon A overlap the Y range of Polygon B
2. Does the X range of polygon A overlap the X range of Polygon B
3. ??? Heh ??? Thinking on this bit Seems there should be a linear algebra way to do it.

 

[notfred]

Originally posted by: Armitage

Originally posted by: notfred
OK, I found an algorithm that is ridiculously simple for determining if a point lies inside a polygon. This works for convex, concave and self-intersecting polygons. Take your point and draw a ray from that point to infinity in any direction. To make this easy, say we draw the ray vertically. Count how many times that ray crosses a line segment of your polygon. If the number of times it crosses is even the point is outside the polygon. If the number of times it crosses is odd, the point is inside the polygon.

That's fine, but what point do you choose to test? The polygons can intersect without any vertices lying within the other polygon. It's a good test to see if it is completely contained within the other though.

that's all it's for. Like I said, determining if a point lies inside a polygon. You can test line segments for intersection, if there is no intersection, use this method to see if they overlap completely.

 

[DrPizza]

that algorithm works with the exception of if your ray crosses at one of the vertices.

Sounds like a pretty simple algorithm to use though, especially using a vertical ray.