Sign in to follow this  
Wavesonics

Circle - Polygon intersection test

Recommended Posts

I've been looking around a bit for methods to determine if a circle intersects with a general polygon (i.e. concave or convex). And it's beginning to look like that is generally something difficult (as with most collision algorithms, concave leading to many of the problems). So I guess I'm asking two things: 1) Does anyone know of a good algorithm that DOES do circle -> polygon intersection testing? 2) If i am right and that's generally a more complex topic, my next feeling is to tessellate the polygon into a triangle strip, and then do the much simpler, circle -> triangle intersection test. Does this sound reasonable? The performance isn't much of a concern, it is only going to be run on a few triangles (n < ~10) every minute or so.

Share this post


Link to post
Share on other sites
There isn't a direct easy method for concave polygons that I know of.

here's two that you mentioned.

1)
. split concave polygon into convex pieces (gluTesselate(), or some simple algo if your concave polygons are sensible).
. for each convex piece, find point on perimeter the closest to the sphere centre.
. check if closest point is inside circle.
. also check if sphere centre inside each convex perimeter (usually given when you do the closest point calculation).

2)
. for each edge, find closest point on edge to sphere centre.
. check if closest point inside the circle.
. do a point-in-concave-polygon test for the circle centre.

Share this post


Link to post
Share on other sites
One method rather similar to described above is to first break up the concave polygon into convex parts and then perform a Separating Axis Test against each of them. Both the circle and convex polygon are convex, so SAT applies. Since the separating axis must be parallel to one of the edges of the convex polygon, there's only a small number of axes to test.

Share this post


Link to post
Share on other sites
Seems pretty simple, actually, even without a decomposition. Just do a segment-circle test with each edge of the polygon, and a point-in-polygon test with the center of the circle. That should catch both fully-enclosed cases as well as the general case.

EDIT: nevermind, olii already mentioned it. Do it that way, tho. :-)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this