In 2D, you make (X,Y) from (x,y) with a rotation by angle t so:
X = x cos t - y sin t
Y = x sin t + y cos t
As a 2x2 matrix this 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 the product 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 2D
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 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; it depends on your application. 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 ©] 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 ©] 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 ©, 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/compg...gdbiblio.tex.gz and ftp://wilma.cs.brown.edu/pub/papers/compg.../gdbiblio.ps.gz Commercial software includes the Graph Layout Toolkit from Tom Sawyer Software http://www.tomsawyer.com and Northwoods Software's GO++ Perhaps the best code is the AT&T Research Labs open C source:How do I find intersections of 2 2D line segments?
How do I generate a circle through three points?
How can the smallest circle enclosing a set of points be found?
Where can I find graph layout algorithms?