3
$\begingroup$

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 guaranteed to be of the form $a \leq x \leq b$, $c \leq y < d$ i.e. it will not have any rotation.
  • 0
    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.2011-03-24

1 Answers 1

2

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.

  • 0
    @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.2011-03-24