# How to test if a point is inside the convex hull of two circles?

Following my previous question, I'm wondering how I can determine if a point is within the convex hull of two circles (a boolean value). There's no problem testing if the point is in either of the two circles, but it can also be "between" them and I don't know how to test for that.

Seeing Wolfram MathWorld's article on Circle-Circle Tangeants, it seems that an inequation that tests if the point is on the internal side the two external circle tangeants would do the trick, but I'm afraid my solving skills are too far away to be able to turn the tangeant equations into a fitting inequality.

I'm defining the convex hull of two circles using both centers and radii.

-

You can first calculate the four points of tangency, then use the Point in Polygon algorithm to determine if your point is inside the quadrilateral (this is assuming you have a programming related problem)

Otherwise, once you have found the four tangent points, you can form four lines and get four simultaneous inequalities.

-
I indeed have a programming related problem and this is a great idea that should be easy to implement. Thanks. – Trillian Jul 31 '10 at 14:52

The solution to this problem is indeed to check whether the point is in one of the circles or in the isosceles trapezoid determined by the points were circles touch the tangent lines. However, without some care the equations get messy.

Let's start with a circle at (x1', y1') of radius r1', a circle at (x2', y2') with radius r2', and a point (x', y') to test. We may assume that r1' is at least r2'. By shifting followed by rotation followed by scaling this can be transformed into a simpler instance: a circle at (0,0) of radius r1, a circle at (1,0) of radius r2, and a point (x,y) to test. We have: r1=r1'/D, r2=r2'/D,

$x=((y'-y'_1)\sin\alpha+(x'-x'_1)\cos\alpha)/D$

$y=((y'-y'_1)\sin\alpha-(x'-x'_1)\cos\alpha)/D$

where

$D^2=(x'_1-x'_2)^2+(y'_1-y'_2)^2$

and $\alpha$ is the angle where (x2'-x1',y2'-y1') lies. (In C, there's a function atan2 that takes the two coordinates of a point and gives the angle. In math, atan doesn't really distinguish between points symmetric wrt (0,0).)

1. If the point is in one of the circles say YES, otherwise continue.
2. If r1=r2 then return (0 < x < 1 and |y| < r1), otherwise continue. (At this point the difference between radii Dr=r1-r2 is strictly between 0 and 1.)
3. If x < r1 Dr, say NO.
4. If x > 1 + r2 Dr, say NO.
5. If $x\Delta r + |y|\sqrt{1-{\Delta r}^2}>r_1$, say NO.
6. Say YES.

There's only one thing I used, really, namely that certain triangles are similar. Draw the tangent that touches the two circles 'above'. Let's say that it intersects the big circle at A=(x1,y1), the small circle at B=(x2,y2), and the horizontal axis at C=(d,0). Let's also write D=(0,0) and E=(x1,0) and F=(1,0) and G=(x2,0). The similar triangles are ADC, AED, BFC, and BGD. From ADC similar to BFC you find d = r1/Dr. From ADC similar to AED you find x1 = r1 Dr and from BFD similar to BGD you find x2 - 1 = r2 Dr.

To check that a point is on the right side of a line write its equation as ax+by+c=0 and replace equality by inequality. (It's good to remember that the vector $(a,b)^T$ is perpendicular to the line and that the equation can be interpreted as defining all vectors/points whose scalar/dot product with a fixed vector $(a,b)^T$ gives the constant c.)

Let me know if I messed up again :P

This is the old answer, which is wrong as pointed by the first comment below. It starts with the same transformations (without giving details) but then it uses some line that is clearly not tangent to the circles.

Say the first circle has the center at (0,0) (if not, shift the figure) with radius r_1, and the second at (1,0) (if not, rotate the figure and scale) with radius r_2. If your point is (x,y) and is not in one of the two circles, then x must be between 0 and 1 and |y| must be at most r_1+(r_2-r_1)x.

-
Transforming the shape to reduce the number of variables is a great idea, but your linear interpolation won't yield perfect results. See img96.imageshack.us/img96/7937/lerp.png – Trillian Jul 31 '10 at 13:58
Thanks for taking time to draw that for me. – rgrig Jul 31 '10 at 20:36
This is starting to be quite interesting. I've tried it out and, unless I made a mistake, there still a problem with it. Here's the code: pastebin.com/jxDE9ne8 , and here's the result image where each pixel has been tested: img293.imageshack.us/img293/7913/resultx.png – Trillian Aug 2 '10 at 14:22