In 2-D, the 2x2 matrix is very simple. If you want to rotate a column vector v by t degrees using matrix M, use
M = {{cos t, -sin t}, {sin t, cos t}} in M*v.
If you have a row vector, use the transpose of M (turn rows into columns and vice versa). If you want to combine rotations, in 2-D you can just add their angles, but in higher dimensions you must multiply their matrices.
Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By). Let P be the point of perpendicular projection of C on AB. The parameter r, which indicates P's position along AB, is computed by the dot product of AC and AB divided by the square of the length of AB:
(1) AC dot AB
r = ---------
||AB||^2
r has the following meaning:
r=0 P = A
r=1 P = B
r<0 P is on the backward extension of AB
r>1 P is on the forward extension of AB
0<r<1 P is interior to AB
The length of a line segment in d dimensions, AB is computed by:
L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 + ... + (Bd-Ad)^2)
so in 2D:
L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )
and the dot product of two vectors in d dimensions, U dot V is computed:
D = (Ux * Vx) + (Uy * Vy) + ... + (Ud * Vd)
so in 2D:
D = (Ux * Vx) + (Uy * Vy)
So (1) expands to:
(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay) r = ------------------------------- L^2
The point P can then be found:
Px = Ax + r(Bx-Ax) Py = Ay + r(By-Ay)
And the distance from A to P = r*L.
Use another parameter s to indicate the location along PC, with the following meaning: s<0 C is left of AB s>0 C is right of AB s=0 C is on AB
Compute s as follows:
(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) s = ----------------------------- L^2
Then the distance from C to P = s*L.
This problem can be extremely easy or extremely difficult depends on your applications. If all you want is the intersection point, the following should work:
Let A,B,C,D be 2-space position vectors. Then the directed line segments AB & CD are given by:
AB=A+r(B-A), r in [0,1] CD=C+s(D-C), s in [0,1]
If AB & CD intersect, then
A+r(B-A)=C+s(D-C), or
Ax+r(Bx-Ax)=Cx+s(Dx-Cx) Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1]
Solving the above for r and s yields
(Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy) r = ----------------------------- (eqn 1) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) s = ----------------------------- (eqn 2) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
Let P be the position vector of the intersection point, then
P=A+r(B-A) or
Px=Ax+r(Bx-Ax) Py=Ay+r(By-Ay)
By examining the values of r & s, you can also determine some other limiting conditions:
If 0<=r<=1 & 0<=s<=1, intersection exists r<0 or r>1 or s<0 or s>1 line segments do not intersect
If the denominator in eqn 1 is zero, AB & CD are parallel If the numerator in eqn 1 is also zero, AB & CD are collinear.
If they are collinear, then the segments may be projected to the x- or y-axis, and overlap of the projected intervals checked.
If the intersection point of the 2 lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then
If r>1, P is located on extension of AB
If r<0, P is located on extension of BA
If s>1, P is located on extension of CD
If s<0, P is located on extension of DC
Also note that the denominators of eqn 1 & 2 are identical.
References:
[O'Rourke (C)] pp. 249-51 [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
Let the three given points be a, b, c. Use _0 and _1 to represent x and y coordinates. The coordinates of the center p=(p_0,p_1) of the circle determined by a, b, and c are:
A = b_0 - a_0; B = b_1 - a_1; C = c_0 - a_0; D = c_1 - a_1;
E = A*(a_0 + b_0) + B*(a_1 + b_1); F = C*(a_0 + c_0) + D*(a_1 + c_1);
G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0));
p_0 = (D*E - B*F) / G; p_1 = (A*F - C*E) / G;
If G is zero then the three points are collinear and no finite-radius circle through them exists. Otherwise, the radius of the circle is:
r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2
Reference:
[O' Rourke (C)] p. 201. Simplified by Jim Ward.
This circle is often called the minimum spanning circle. It can be computed in O(n log n) time for n points. The center lies on the furthest-point Voronoi diagram. Computing the diagram constrains the search for the center. Constructing the diagram can be accomplished by a 3D convex hull algorithm; for that connection, see, e.g., [O'Rourke (C), p.195ff]. For direct algorithms, see: S. Skyum, "A simple algorithm for computing the smallest enclosing circle" Inform. Process. Lett. 37 (1991) 121--125. J. Rokne, "An Easy Bounding Circle" [Gems II] pp.14--16.
See the paper by Eades and Tamassia, "Algorithms for Drawing Graphs: An Annotated Bibliography," Tech Rep CS-89-09, Dept. of CS, Brown Univ, Feb. 1989.
A revised version of the annotated bibliography on graph drawing algorithms by Giuseppe Di Battista, Peter Eades, and Roberto Tamassia is now available from
ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.tex.gz and ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.ps.gz
Commercial software includes the Graph Layout Toolkit from Tom Sawyer | Software http://www.tomsawyer.com and Northwoods Software's GO++ | http://www.nwoods.com/go/ .