I have a circle, it's coordinates and its nonzero radius, and an external point. I want to find the two points where the two tangents to the circle from this point will touch the circle. (This is for calculating points in a vision polygon, of what can be seen around objects from the player)

I actually had a solution but it used quite a lot of trig (using the radius and distance from the point as an arm and hyp of a right triangle respectively). This will be recursed several times per frame in my game so I need it to be reasonably efficient. It seemed like it should be quite simple but I can't think of the math.

Any ideas?

PS. I also posted this in the new forum, i wasn't sure which one would elicit more responses (I hope that's ok)

This post has been edited by mattk210 on October 05, 2008 07:03 am

Suppose that your circle has centre (a,b) and radius r, and your external point has coordinates (c,d). Now the distance from the external point to the centre is sqrt((a-c)²+(b-d)²) and you can see this as the hypotenuse of a right-angled triangle whose vertices are the external point, the centre and either place where the tangent touches the circle.
Let the distance from the external point to the place where the tangent touches the circle be s.
By Pythagoras (a-c)²+(b-d)²=r²+s²
so: s²=(a-c)²+(b-d)²-r².
The points where the tangent meets the circle must therefore be a distance s=sqrt((a-c)²+(b-d)²-r²) from (c,d), so they must lie on the circle with centre (c,d) and radius sqrt((a-c)²+(b-d)²-r²), which has equation
(x-c)²+(y-d)²=s²=(a-c)²+(b-d)²-r².
But your original circle has equation (x-a)²+(y-b)²=r².
If you subtract that from the previous equation you get (2a-2c)x+(2b-2d)y+c²+d²-a²-b²=(a-c)²+(b-d)²-2r² which is a linear equation. If you solve it simultaneously with one of the circle equations, the two solutions that you get for (x,y) are the coordinates of the two points.

This post has been edited by 999_Springs on October 07, 2008 07:53 pm

That seems like an efficient way to solve it. Unfortunately I don't know how to solve that kind of problem. I can simplify it to

but I don't know how to solve this. Can you help?

The normal way to solve a pair of simultaneous equations like this is to isolate a variable using the linear equation:
(2a-2c)x+(2b-2d)y+c²+d²-a²-b²=(a-c)²+(b-d)²-2r²
=> (2a-2c)x+(2b-2d)y=a²-2ac+c²+b²-2bd+d²-2r²-c²-d²+a²+b²
=> (2a-2c)x+(2b-2d)y=2a²+2b²-2ac-2bd-2r²
=> (a-c)x+(b-d)y=a²+b²-ac-bd-r²
=> (b-d)y=a²+b²-ac-bd-r²-(a-c)x
=> y=(a²+b²-ac-bd-r²)/(b-d) - (c-a)x/(b-d)
=> y=(a²+b²-ac-bd-r²)/(b-d) + (a-c)x/(b-d)
and substitute into (x-a)²+(y-b)²=r² and you should get a quadratic equation to solve using, say, the quadratic equation formula. If you do that, what you will get will look really ghastly, but it will be much less ghastly once you have put in the values for your known variables.

ah. thank you. I don't have time to check it now but I can understand that. I'll post if I have any issues!

This post has been edited by mattk210 on October 08, 2008 10:44 pm

Note that this is pseudocode. Note also that I haven't tested this beyond deriving the maths for it, and the maths has one major downside: minus signs become ambiguous. In other words, you may have to add test cases to find out whether they work (preferably with a graphical display) and fiddle around with special cases and changing signs accordingly.

Cases you should check to see if you need to change signs for:
px*py > 0
px*py == 0
px*py < 0
mb > 0
mb < 0

wow, I'm being swamped with solutions! Thanks guys, they all work great. Decoy's may be more appropriate because I have a further step to isolate a single tangent and the sign-ambiguity may allow me to circumvent that.

I redid the maths and came up with a vastly more elegant and computationally-simple solution.

As you can see, this version is much faster (only 1 square root), and only has one special case (where px2py2 would be 0). There might still be the ambiguity, but I don't think so. Also note that this is the absolute minimum of computation possible. You simply cannot get a more efficient method than this (unless you are a programming deity of some sort).

It would probably be worth delaying the "if px == 0 and py == 0: return null" until after you get r2 and px2py2, as it's only solvable when px2py2>r2 (well, technically there's the trivial solution when px2py2==r2).
Depending on the language (and compiler, if applicable) used, there are probably some peephole optimizations to be done too (e.g. saving a couple assignments when computing pxr2, pyr2, T1, and T2, or moving some things around to keep stuff in registers), but otherwise it looks pretty close to optimal.

[edit]I've attached a simple demo app. And yes, the signs were correct.[/edit]

This post has been edited by taaveti on October 16, 2008 04:16 am

Attached File ( Number of downloads: 123 )
 circletest.zip

great! Thanks! That's plenty optimized enough even without taaveti's advice (my original solution had at least 5 trig operations)