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$
  • $\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 '17 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 '17 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 '17 at 20:14
  • $\begingroup$ Is the polygon convex? $\endgroup$ – Rodrigo de Azevedo Jul 23 '17 at 9:56
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, privacy policy and cookie policy

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