Comp.Graphics.Algorithms
Frequently Asked Questions

Section 1. 2D Computations: Points, Segments, Circles, Etc.

Subject 1.01: How do I rotate a 2D point?

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.

Subject 1.02: How do I find the distance from a point to a line?

Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By). The length of the line segment AB is L:

        L= sqrt( (Bx-Ax)^2 + (By-Ay)^2 ) .

Let P be the point of perpendicular projection of C onto AB. Let r be a parameter to indicate P's location along the line containing AB, with 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

Compute r with this:

            (Ay-Cy)(Ay-By)-(Ax-Cx)(Bx-Ax)
        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.

Subject 1.03: How do I find intersections of 2 2D line segments?

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 coincident

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,"

Subject 1.04: How do I generate a circle through three points?

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.

Subject 1.05: How can the smallest circle enclosing a set of points be found?

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 a direct algorithm, 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.

Subject 1.06: Where can I find graph layout algorithms?

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
ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.ps.gz

Commercial software includes the Graph Layout Toolkit from Tom Sawyer Software ( www.tomsawyer.com ).

Comp.Graphics.Algorithms Frequently Asked Questions