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/ .

Next Previous Contents