3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It does not look like prepared question with any prior research. Quite obvious way is to do PIP test for the center and distance from the edges. If this doesn't work for you then some constraints are missing. $\endgroup$
    – Evil
    Jul 14, 2017 at 18:57
  • $\begingroup$ What are your thoughts? What research have you done? What approaches have you considered, and why did you reject them? See cs.stackexchange.com/help/how-to-ask. Sharing your research helps make your question more interesting for others, and help us assess your current level of understanding and give you a better answer. $\endgroup$
    – D.W.
    Jul 14, 2017 at 19:24
  • $\begingroup$ Well I think scaling the polygon on a point, and doing an edge test (like point in polygon). I just wondered if there was a simpler method I was missing. I have done a lot of research without finding much. Did not want to confuse anyone with any tangents so I posted as simply as I could. $\endgroup$
    – Chris
    Jul 14, 2017 at 20:14
  • $\begingroup$ Is the polygon convex? $\endgroup$ Jul 23, 2017 at 9:56

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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