tangent to a point

[mattk210]

I'm not entirely sure this belongs here; it's not directly related to metanet, but it's the kind of game-dev math that I would have put in Dev Tuts in the old forum, and BT assures me this is the new dev tuts.

Anyway, my problem. 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?

[xeronix]

your best bet is trig, thats all a tangent really are. it all depends on the scope and how much you want the range of view to be. do you have an example of the math on hand?

[t̷s͢uk̕a͡t͜ư]

Dunno about silly messing around with trig (sounds like it could get sticky, too), but here's the general solution through calculus.

These steps are easily replicated on a computer, provided you know what vector magnitudes, dot products, and projections are (and I'll define those for you in case you're not familiar, too). If you're not using something high-level like Python or Ruby, then the calculations required here might be faster than a method that involves resolving a whole lot of trig functions.



Vectors have those arrow things above them, and scalars don't.
Vectors are represented with an ordered pair between angle brackets, e.g. "<a, b>", whereas a scalar is just the letter itself, e.g. "a".

Definition of a dot product:
vector (dot) vector: <a, b> (dot) <c, d> = ab + cd <-- a scalar
scalar (dot) vector, or vector (dot) scalar: <a, b> (dot) c = c (dot) <a, b> = <ac, bc> <-- a vector
Also note that dividing a scalar by a vector is like taking the dot product of the scalar unchanged and the vector with each term being its reciprocal, for example:
scalar / vector: c / <a, b> = c (dot) < (1/a), (1/b) > = < c/a, c/b >

Definition of vector magnitude and vector projection, assuming that v_1 = <a, b> and v_2 = <c, d>:


Here's an implementation written in pseudo-code:

Code: Select all

def mag(vector):
    return sqrt( vector[0]^2 + vector[1]^2 )

def dot(a, b):
    if a is scalar and b is scalar:
        return a * b
    if a is scalar and b is vector:
        return Vector(a*b[0], a*b[1])
    if a is vector and b is scalar:
        return Vector(b*a[0], b*a[1])
    if a is vector and b is vector:
        return Vector(a[0]*b[0], a[1]*b[1])

def proj(vector_one, vector_two):
    # vector_one onto vector_two
    return dot( dot( vector_one, vector_two ) / dot( vector_two, vector_two ), vector_two )

# givens:
x_c, y_c = x-coordinate of circle's center, y-coordinate of circle's center
x_0, y_0 = x-coordinate of point, y-coordinate of point
r = radius of circle

# derived quantities:
L = Vector( x_0 - x_c, y_0 - y_c )
r_1 = ( r * mag(L) )  /  ( 2 * L )
r_2 = r^2 / dot(-2, r_1)

point_one = {  x_c + mag( proj( r_1, Vector(1, 0) ) ),   y_c + mag( proj( r_1, Vector(0, 1) ) )  }
point_two = {  x_c + mag( proj( r_2, Vector(1, 0) ) ),   y_c + mag( proj( r_2, Vector(0, 1) ) )  }

# or if you want to save a few CPU cycles...
# (you could also just remove the definition of mag() entirely
point_one = {  x_c + proj( r_1, Vector(1, 0) )[0],   y_c + proj( r_1, Vector(0, 1) )[1]  }
point_two = {  x_c + proj( r_2, Vector(1, 0) )[0],   y_c + proj( r_2, Vector(0, 1) )[1]  }

[mattk210]

thanks a lot, that must have taken some time to type up. I'm by no means an expert but I can understand that enough to implement it. I'll let you know if I have any issues.

EDIT: I can't get it to work. I quickly hacked it into a very old test file (hence the terrible programming conventions and random comments, please let it slide), and I got something that seems like it's on the right track but obviously not right. It's probably me (I tried to work around not having a vector class), but I couldn't seem to find anything obviously wrong and I don't understand the code enough to fix it myself. (I tried both of your methods and a different definition for proj)

http://psychonova.110mb.com/tangent.swf

EDIT AGAIN: where does 60 degrees come from? I think that might be the issue.

Code: Select all

function mag(vector) {
	return Math.sqrt(vector[0]*vector[0]+vector[1]*vector[1]);
}
function dot(a, b) {
	if (a.length != 2 && b.length != 2) {
		return a*b;
	}
	if (a.length != 2 && b.length == 2) {
		return [a*b[0], a*b[1]];
	}
	if (a.length == 2 && b.length != 2) {
		return [b*a[0], b*a[1]];
	}
	if (a.length == 2 && b.length == 2) {
		return [a[0]*b[0], a[1]*b[1]];
	}
}
function proj(vector_one, vector_two) {
	//try a different formula
	//dp = vector_one[0]*vector_two[0] + vector_one[1]*vector_two[1];
	//return [( dp / (vector_two[0]*vector_two[0] + vector_two[1]*vector_two[1]) ) * vector_two[0],( dp / (vector_two[0]*vector_two[0] + vector_two[1]*vector_two[1]) ) * vector_two[1]]
	//vector_one onto vector_two
	var a = dot(vector_one, vector_two);
	var b = dot(vector_two, vector_two);
	return dot([a[0]/b[0], a[1]/b[1]], vector_two);
}
function onEnterFrame() {
	x_0 = _root.line1p1._x;
	y_0 = _root.line1p1._y;
	radx = _root.ring._x-_root.rad._x;
	rady = _root.ring._y-_root.rad._y;
	r = Math.sqrt(radx*radx+rady*rady);
	x_c = _root.circle._x;
	y_c = _root.circle._y;
	i1 = {x:0, y:0};
	i2 = {x:0, y:0};
	/*givens:
	x_c, y_c = x-coordinate of circle's center, y-coordinate of circle's center
	x_0, y_0 = x-coordinate of point, y-coordinate of point
	r = radius of circle*/

	//derived quantities:
	var L = [x_0-x_c, y_0-y_c];
	var r_1 = [(r*mag(L))/(2*L[0]), (r*mag(L))/(2*L[1])];
	var r_2 = [(r*r)/dot(-2, r_1)[0], (r*r)/dot(-2, r_1)[1]];

	i1.x = x_c+mag(proj(r_1, [1, 0]));
	i1.y = y_c+mag(proj(r_1, [0, 1]));
	i2.x = x_c+mag(proj(r_2, [1, 0]));
	i2.y = y_c+mag(proj(r_2, [0, 1]));
	//trace(proj(r_1, [1, 0]))
	//or if you want to save a few CPU cycles...
	//(you could also just remove the definition of mag() entirely
	i1.x = x_c+proj(r_1, [1, 0])[0];
	i1.y = y_c+proj(r_1, [0, 1])[1];
	i2.x = x_c+proj(r_2, [1, 0])[0];
	i2.y = y_c+proj(r_2, [0, 1])[1];
	trace(i1.x);

	//_root.clear();
	//_root.lineStyle(5);
	_root.ring._x = _root.circle._x;
	_root.ring._y = _root.circle._y;
	_root.ring._width = r*2;
	_root.ring._height = r*2;
	_root.ip1._x = i1.x;
	_root.ip1._y = i1.y;
	_root.ip2._x = i2.x;
	_root.ip2._y = i2.y;


}

[jackass]

WTF are you talking about?

If you don't get it, don't post. — maestro

[t̷s͢uk̕a͡t͜ư]

Code: Select all

1: function proj(vector_one, vector_two) {
2:    //try a different formula
3:    //dp = vector_one[0]*vector_two[0] + vector_one[1]*vector_two[1];
4:    //return [( dp / (vector_two[0]*vector_two[0] + vector_two[1]*vector_two[1]) ) * vector_two[0],( dp / (vector_two[0]*vector_two[0] + vector_two[1]*vector_two[1]) ) * vector_two[1]]
5:    //vector_one onto vector_two
6:    var a = dot(vector_one, vector_two);
7:    var b = dot(vector_two, vector_two);
8:    return dot([a[0]/b[0], a[1]/b[1]], vector_two);
9: }

In line 8, you're treating a and b as vectors, whereas they are the result of a dot product operation on two vectors, the result of which is a scalar.
(Also, you're giving the dot() function too many arguments.)
Line 8 should be:

Code: Select all

return dot(a / b, vector_two)

Your commented lines 3-4 accomplish exactly as much.
...and you've probably already got this covered, but these are floats you're using, right? Not ints? (I don't know if that's automatically handled in ActionScript.)

Code: Select all

r = Math.sqrt(radx*radx+rady*rady);

To warn you, I don't know ActionScript...
So the radii of your circle are radx in the x-direction and rady in the y-direction, I'm guessing so you have the option of making an oval.
If it's a circle you're using, then the radius in the x-direction is going to be the same as the radius in the y-direction, so why not just use r = radx or r = rady? Because sqrt(radx^2 + rady^2) will give you the length to the corner of a box that contains the circle. I don't know if that's what you're looking for, but the derivation I gave sort of relies on r being the radius of the circle, not the distance from the center to the corner of a box containing the circle.

EDIT AGAIN: where does 60 degrees come from? I think that might be the issue.

Well, you've reminded me that I forgot to give an additional basic definition of a dot product:
If v_one and v_two are vectors, then v_one (dot) v_two = |v_one|*|v_two|*cos(the angle between v_one and v_two)
I use that with the assumption that the angle between them is 60 degrees, and I solve for the individual vectors on the left side because we already know all the magnitudes.
But also... yeah, I do seem to have just pulled 60 degrees out of my ass. I could swear there's some principle in mathematics that says that those angles are always 60 degrees, but now that doesn't seem to make sense to me (like if you extend L to be, say, 5 million, then the 30-60-90 thing totally doesn't hold).
Well, you could still get that angle by doing an inverse cosine of (r / mag(L)). Call it theta or something. And then you'd have to adjust a few lines, notably:

Code: Select all

# derived quantities:
L = Vector( x_0 - x_c, y_0 - y_c )    # unchanged
theta = inverse_cosine( r / mag(L) )
r_1 = ( r * mag(L) * cosine(theta) )  /  L
r_2 = ( r^2 * cosine(2 * theta) ) / r_1
## or the version you'd probably want to put...
## (this assumes that ActionScript has functions Math.cos and Math.cos_inv;
## they're probably named different things than I'm calling them)
# theta = Math.cos_inv(r / mag(L))
# var r_1 = [(r * mag(L) * Math.cos(theta)) / L[0], (r * mag(L) * Math.cos(theta)) / L[1]]
# var r_2 = [(r*r * Math.cos(2 * theta)) / r_1[0], (r*r * Math.cos(2 * theta)) / r_1[1]]

Barring a faulty implementation of ring, circle, or line objects, I don't see why that wouldn't work. Then again, I haven't actually tested it for myself (felt lazy after spending, like, an hour and a half typing that post :p).
If that doesn't work, I might've done my math wrong. :/

[mattk210]

I was kind of trying to avoid expensive trig... But even with those it's still better than what I had before if I cache some of the trig stuff. I'll fix the mistakes you noticed and try the new stuff (the calculation of the radius and other GUI stuff is fine, it's just me several years ago having no grasp of basic math, but it works). Thanks again!

EDIT:

In line 8, you're treating a and b as vectors, whereas they are the result of a dot product operation on two vectors, the result of which is a scalar.
(Also, you're giving the dot() function too many arguments.)
Line 8 should be:


Code:
return dot(a / b, vector_two)

I didn't know what to do here (i don't know how to divide vectors a and b), so i divided the x and y components and put them in a vector. [a,b] is a vector, that's why it looks like 3 arguments. You say the dot of 2 vectors is a scalar? but in your dp code, unless I'm very mistaken, it returns a vector!

EDIT: I couldn't get it to work, and reconsidering, I thought it would be simple, but this probably isn't worth your time if I already have a working solution. I'll update it and post it for anyone in the future and don't worry about it.

Here. Sorry it isn't commented (again, code from a time before I was sensible enough to use such things), but it works (i basically just considered 3 triangles:the 2 in your diagram using Q0 and Q1 as angles, and the triangle made up of L and the x and y distances between the circle and the point. I also shifted the whole thing so the circle is at (0,0), simplifying calculations.) Using the same givens as you:

Code: Select all

	//shifted values:
	x_t=x_0-x_c
	y_t=y_0-y_c
	var len = Math.sqrt(x_t*x_t+y_t*y_t);
	var tgt = Math.sqrt(len*len-r*r);
	var Q0 = Math.abs(Math.asin(-x_t/len));
	var Q1 = Math.abs(Math.asin(-y_t/len));
	var phi = Math.asin(r/len);
	//i1 and i2 are points of intersection
	i1.y = Math.sin(Math.PI/2-(phi+Q0))*tgt*(y_t<0 ? 1 : -1)+y_t+y_c;
	i2.x = Math.sin(Math.PI/2-(phi+Q1))*tgt*(x_t<0 ? 1 : -1)+x_t+x_c;
	i1.x = Math.cos(Math.PI/2-(phi+Q0))*tgt*(x_t<0 ? 1 : -1)+x_t+x_c;
	i2.y = Math.cos(Math.PI/2-(phi+Q1))*tgt*(y_t<0 ? 1 : -1)+y_t+y_c;

[AlliedEnvy]

Check this post out.

His math seems right to me up until after his "EDIT" (where I stopped checking).


Also, check out this ruler-and-compass-based method for getting the two tangent points, which you could combine with this or this equation to get the intersection of two circles to get something which might work.

[mattk210]

sorry I couldn't respond earlier. Thanks, works great.

[Rikaninja]

What's the purpose of this.
I don't undertsand what you're all talking about!


Yanni edit: Come on, man. Scroll up a bit to the maestro edit on the jackass77 post. If you don't get it, don't post.