Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a rectangle and a circular sector in a Cartesian plane. What is the easiest way (algorithmically) to tell if they intersect?

Edit:

  • I'm looking to see if the areas intersect, not just the perimeters.
  • Also, The rectangle is guarenteed to be of the form a <= x <= b, c <= y < d. ie, it wil not have any rotation.
share|improve this question
    
What do you know from the rectangle and the sector? –  Fabian Mar 23 '11 at 22:34
    
anything you want. I have a the center (for the circle) of the sector, the radius, the slope of the line that bisects sector...I have all the vertices of the rectangle. –  Conley Owens Mar 24 '11 at 0:45

1 Answer 1

up vote 2 down vote accepted

Check whether the centre of the circle is within the rectangle expanded by the radius in all directions. If not, the answer is "no". Else, check whether the centre of the circle is within the rectangle. If so, the answer is "yes". Else for each line, check whether the centre of the circle is less than the radius away from it, and if so, calculate the angles at which the line intersects the circle. If any of these angles is in the angle range of the sector, the answer is "yes". Else the answer is "no".

This avoids unnecessary line/circle intersections when the answer can easily be determined without them. Note that it relies on the fact that the border of the rectangle can't intersect the border of the sector without also intersecting its circular part.

share|improve this answer
1  
It seems the center of the circle could be within the rectangle, but the entire circular arc could be outside. –  Ross Millikan Mar 24 '11 at 0:36
    
@ross: Sorry, I'm looking for the intersection of their areas, not their perimeters. –  Conley Owens Mar 24 '11 at 0:49
    
@Conley: I was questioning the comment "Note that it relies on the fact that the border of the rectangle can't intersect the border of the sector without also intersecting its circular part." but maybe I didn't understand it properly. If you are interested in area intersection, you also have to deal with one shape being entirely inside the other. –  Ross Millikan Mar 24 '11 at 1:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.