Finding intersect in triangle from a vector originating from a particular side

I know the coordinates of A, B and C.. I also know of a vector V originating from C..

I know that the vector intersects A and B, I just don't know h开发者_Go百科ow to find i.

Can anyone explain the steps involved in solving this problem?

Thanks alot.

http://img34.imageshack.us/img34/941/triangleprob.png

---

If you know A and B, you know equation for the line AB, and you said you know V, so you can form the equation for Line V.... Well i is only point that satisfies both those equations.

Equation for Line AB:

  (bx-ax)(Y-ay) = (by-ay)(X-ax)

If you knpow the direction (or slope = m) of the vector, and any point that lies on the vector, then the equation of the line for vector V is

Y = mX = b

where m is the slope or direction of the line, and b is the y coordinate where it crosses thevertical y=axis (where X = 0)

if you know a point on the line (i.e., C = (s, t) then you solve for b by:

t = ms + b ==> b = t - ms,

so equation becomes

Y = mX + t-ms

---

i = C+kV
Lets call N the normal to the line A,B so N = [-(B-A).y, (B-A).x]
Also, for any point on the line:
(P-A)*N = 0       -- substitute from line 1 above:
(C+kV-A)*N = 0
(kV+C-A)*N = 0
kV*N + (C-A)*N = 0
kV*N = (A-C)*N
k = [(A-C)*N]/V*N
Now that we have k, plug it into line 1 above to get i.

Here I'm using * to represent dot product so expanding to regular multiplication:

k = ((A.x-C.x)*-(B.y-A.y) + (A.y-C.y)*(B.x-A.x)) / (V.x*-(B.y-A.y) + V.x*(B.x-A.x))
I.x = C.x + k*V.x
I.y = C.y + k*V.y

Unless I screwed something up....

---

Simple algebra. The hard part is often just writing down the basic equations, but once written down, the rest is easy.

Can you define a line that emanates from the point C = [c_x,c_y], and points along the vector V = [v_x,v_y]? A nice way to represent such a line is to use a parametric representation. Thus,

V(t) = C + t*V

In terms of the vector elements, we have it as

V(t) = [c_x + t*v_x, c_y + t*v_y]

Look at how this works. When t = 0, we get the point C back, but for any other value of t, we get some other point on the line.

How about the line segment that passes through A and B? One way to solve this problem would be to define a second line parametrically in the same fashion. Then solve for a system of two equations in two unknowns to find the intersection.

An easier approach is to look at the normal vector to the line segment AB. That vector is given as

N = [b_y - a_y , a_x - b_x]/sqrt((b_x - a_x)^2 + (b_y - a_y)^2)

Note that N is defined here to have a unit norm.

So now, when do we know if a point happens to lie along the line that connects A and B? This is easy now. That will happen when the dot product defined below is exactly zero.

dot(N,V(t) - A) = 0

Expand this, and solve for the parameter t. We can write it down using dot products.

t = dot(N,A-C)/dot(N,V)

Or, if you prefer,

t = (N_x*(a_x - c_x) + N_y*(a_y - c_y)) / (N_x*v_x + N_y*v_y))

And once we have t, substitute into the expression above for V(t). Lets see all of this work in practice. I'll pick some points A,B,C and a vector V.

A = [7, 3]
B = [2, 5]
C = [1, 0]

V = [1, 1]

Our normal vector N, after normalization, will look something like

N = [0.371390676354104, 0.928476690885259]

The line parameter, t, is then

t = 3.85714285714286

And we find the point of intersection as

C + t*V = [4.85714285714286, 3.85714285714286]

If you plot the points on a piece of paper it should all fit together, and all in only a few simple expressions.