Testing for circle overlapping a pie slice.
Daniel Pitts
Given a circle (point + radius), and a pie slice (centered at origin +
start/stop angle), is there an easy test for whether the circle
intersects with the pie slice?
boolean intersects(AngelBracket bracket, Vector center, double radius) {
return /* true if circle is in the angle bracket */;
}
I'll be testing many different circles (same radius, different points)
against the same slice, if that makes any difference.
Thanks,
Daniel.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Dave Eberly
news:HJe0n.5685$Gf3....@newsfe22.iad...
> Given a circle (point + radius), and a pie slice (centered at origin +
> start/stop angle), is there an easy test for whether the circle intersects
> with the pie slice?
This is similar to the 3D problem of testing for intersection of a sphere
and a cone:
http://www.geometrictools.com/Documentation/IntersectionSphereCone.pdf
Test whether the circle is "outside" either line forming the pie slice (a 2D
one-sided cone). If it is, then there is no intersection. If it is not,
then the circle partially overlaps the 2D cone or is fully inside the cone.
When this is the case, test for overlap of your circle with that circle that
"caps" the cone. Just as in the 3D case, you need to deal with the fact
that the cone is one-sided, so you probably want an additional comparison of
the circle against the line perpendicular to the cone axis. If you like, I
can write up a sketch with the math/algorithm details.
--
Dave Eberly
http://www.geometrictools.com
Daniel Pitts
I actually came up with a solution to this. I test if the center of the
circle is within the angles OR if either ray intersects the circle. This
gives me the results I need.
Daniel Pitts
Hmm, looking a little more at the document, it looks like I might be
better off using the method describe there. The only problem is the
algorithm expects the cone to be defined in terms of an axis and theta,
but I've defined it as two separate angles.
Actually, now that I think about it, I probably can refactor my code
only a little and get the representation I need.
Dave Eberly
> I actually came up with a solution to this. I test if the center of the
> circle is within the angles OR if either ray intersects the circle. This
> gives me the results I need.
Your subject line says "pie slice", which I interpreted to mean a
sector of a circle (a finite region). Your description here indicates
that you mean the region bounded between two rays (an infinite
region), which is easier to handle (with the algorithm you mention).
Daniel Pitts
strict. My actual need is to find the closest circle to the vertex
which is within the bounded rays.
I'll want to improve the speed eventually, but I think in order to do
that, I'll need to implement a spacial index of my circles.