patternMinor
Is a circle inside a polygon?
Viewed 0 times
circlepolygoninside
Problem
How do I test if a circle (x,y,radius) is inside a polygon ([x,y],[x,y],[x,y],[x,y]...) without touching the edges?
Update
I decided to do a point in polygon followed by a circle line collision on each edge, this let me know first if the circle was within the polygon and then told me if it was colliding with any of the edges.
Update
I decided to do a point in polygon followed by a circle line collision on each edge, this let me know first if the circle was within the polygon and then told me if it was colliding with any of the edges.
Solution
Call the center point $(c_x, c_y)$. The function $d(p_x,p_y) = \sqrt{(p_x-c_x)^2+(p_y-c_y)^2}$ computes the distance from the point $(p_x,p_y)$ to the center of the circle.
For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve for, $x$ and $y$ and plug this into the distance equation above, $d(x,y)$. Find the critical points by setting the partial derivatives equal to zero. Check that the critical points are further than the radius of the circle from the center of the circle.
If all critical points for all edges are more than the radius away from the center then the circle fits.
For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve for, $x$ and $y$ and plug this into the distance equation above, $d(x,y)$. Find the critical points by setting the partial derivatives equal to zero. Check that the critical points are further than the radius of the circle from the center of the circle.
If all critical points for all edges are more than the radius away from the center then the circle fits.
Context
StackExchange Computer Science Q#77944, answer score: 3
Revisions (0)
No revisions yet.