Collision Detection – Circle Segment

On a project I am currently working on I needed to handle collision detection. I don’t have enough appendages to help me count the amount of times I have implemented collision detection. But this time it was a little different, I wanted to check whether or not someone was hovering over a segment of a circle. So I started to brainstorm possible algorithms to handle this particular kind of collision detection.

When I first started off I was thinking about it way too hard and way too mathematically instead of logically. I was trying to figure out the equation of a circle segment and blah blah blah. But after a little while of scribbling into my tiny notebook I came across a rather easy way to detect collision detection for circle segments.

Step 1

Are we in the circle? If we aren’t in the circle then we aren’t going to be in the segment.

This is a super qualification to check for, lets just call dX and dY the coordinate relative to the center of the circle:

if (dX*dX + dY*dY) > radius*radius:
    return false;

This snippet of code checks the squared distance of the coordinate with the squared radius (no need to do a square root because a square is present on both sides of the equation and square roots are expensive computing-wise)

Step 2

What angle is our point at? If it lies within the angles of our segment then we are in the segment since we just found out that we are in fact inside of the circle.

Using some vector math, we know that the arctangent2(y,x) is equal to the angle that the vector is at relative to the x-axis. This means we can find out the angle from the x-axis that our coordinate is at. This can be done with this code:

fi= atan2(dY,dX);
return  fi >= alpha && fi <= beta;

Here we call alpha the starting angle and beta the ending angle of the segment.

Here is an image:

Segment Collision Detection

In this image P is the point that was clicked and the resulting line and arrow is it’s vector. 0 is the starting point (unit circle!). If you aren’t familiar with Greek letters: the fish looking guy is Alpha, the “b” looking thing is Beta, and the O with a line through it is Fi.

Complete Algorithm in Semi-Pseudocode/Python:

function inCircleSegment(dX,dY,radius,alpha,beta):
    if(dX*dX + dY*dY > radius) return false;
    fi = atan2(dY,dX);
    return fi >= alpha && fi <= beta;

ONE LINE! (Because why not?):

return (dX*dX + dY*dY > radius) && (atan2(dY,dX) >= alpha && atan2(dY,dX) <= beta);

Seriously, don’t use that version though. At least save atan2(dY,dX) as a variable!

 

This was a fun little algorithm to come up with, one that is a lot easier to derive once you get your mind out of math and back into logic!

-Brandon

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: