aprendtech.com >> blog >> this post
If you have trouble viewing this, try the pdf of this post. You can download the documents in this post.

A Line object--basic formulas

Computational geometry is an interesting and important topic for imaging in general and x-ray imaging in particular. In this post, I describe the basic formulas for perhaps the most fundamental geometric object—a straight line in three dimensions. The object can also be used in 2D to represent a line in an image.
I used the results described here in the code for my previous posts (here,here, and here) on a CT simulator. In particular, they used a line object. In this post I will derive the basic formulas for an object that encapsulates a three dimensional line. In following posts, I will describe C++ and Matlab implementations and show some applications.
Standard books[1] specify a line by any two points on it. I prefer a more structured definition, which has substantial advantages in implementation of computations as you will see in the examples. I specify a line by two vectors: a vector n from the origin perpendicular to the line and a unit length vector direction vector ŝ along the line (see Fig. 1↓).

Construct line from two points

The most basic operation with a line is to construct it from two points. The details of the construction are shown in Fig. 1↓. The direction vector is
ŝ = (r1 −  r2)/(| r1 −  r2|).
Note that the direction of ŝ is ambiguous depending on the ordering of the two points. But this is also the case with alternate definitions and the user needs to take this into account. The end of the normal vector n is on the line so n = r1 + t0ŝ. Since n is perpendicular to ŝ
nŝ = 0 =  r1ŝ + t0.
Solving, we see that t0 =  −  r1ŝ. With this value we can compute the line n vector as r1 + t0ŝ.

Construct line as intersection of two planes

I specify a plane as two parameters: a unit vector p̂ perpendicular to the plane and the distance of the perpendicular to the plane p. I use two parameters because just using the perpendicular vector cannot represent a plane passing through the origin. I also have a convention that the p parameter is positive. If the computation results in a negative number, we can use its absolute value and negatep̂.
The problem is to compute the parameters of the line n and ŝ from the two planes, p̂1, p1 and p̂2, p2 . First, since the line is in both planes, it is perpendicular to both p̂ vectors so it is parallel to their cross product
ŝ = (p̂1 × p̂2)/(|p̂1 × p̂2|).
Also, n is in the plane spanned by the p̂ vectors
n = k1p̂1 + k2p̂2.
The end of the n vector is in both planes so
np̂1 =  p1 =  k1 + k2p12  np̂2 =  p2 =  k1p12 + k2
where p12 = p̂1p̂2. Solving these two simultaneous equations for k1 and k2
k1 = (p1 − p2p12)/(1 − p212) k2 = ( − p1p12 + p2)/(1 − p212)
Notice that if p̂1 = p̂2, the planes are parallel, p12 = 1, and the equations break down.
figure LineFrom2Vectors.png
Figure 1 Construct Line from two points. This shows examples of the construction diagram for two different cases. In the left panel, the n vector is between the two points, while in the right it is to one side.

Point at intersection of two lines

Unlike the 2D case, lines in three dimensions usually do not intersect. Even if they do, the computation of the intersection point is subject to round off errors. I get around this by defining the intersection as the midpoint of the shortest line segment between the two lines as in Fig. 2↓. This is still undefined if the lines are parallel but that is to be expected. The general formula for points on the lines is Pi = ni + tiŝi i = 1, 2. The line segment between points on the lines is v = P1 − P2 =  δn + t1ŝ1 − t2ŝ2 where δn = n1 −  n2. The minimum length segment is perpendicular to both lines
vŝ1 =  0 =   δnŝ1 + t1 − t2s12  vŝ2 =  0 =   δnŝ2 + t1s12 − t2
where s12 = ŝ1ŝ2. Solving the equations
t1, min = ( − d1 + d2s12)/(1 − s212) t2, min = ( − d1s12 + d2)/(1 − s212)
where di = δnŝi i = 1, 2. Substituting these in the general formula for points on a line gives the points on each line closest to the other, P1, min, P2, min. The “intersection” point is then
Pintersect = 0.5(P1, min + P2, min).
The user can check the length of the line segment [P1, min, P2, min] to decide whether this is an intersection. The formula gives the correct point for the intersection in two dimensions.
figure Intersect2Lines.png
Figure 2 Intersection of two lines. This is defined as the center point of the shortest line segment between the two lines.

Distance of point from line

A common operation is to compute the perpendicular distance of a point from a line. Suppose the point is at P. A point on the line is PL = n + tŝ. The vector joining the original point and a point on the line is v = P − PL. This vector is perpendicular to the line if
vŝ = 0 =  Pŝ − tperp
Solving, tperp = Pŝ and the distance is
d = |P − n − tperpŝ|.

Construct a plane from a point and a line

From elementary geometry a plane can be defined from a line and a point outside the line. The line segment from the point to the line n vector, P − n, is in the plane as is the line ŝ vector. Therefore Pperp = (P − n) × ŝ is perpendicular to the plane and the plane normal vector is
p̂ = (Pperp)/(|Pperp|)
The line n vector is in the plane so the plane distance parameter is p = np̂.

Intersection of a line and a plane

Another common operation is to find the intersection point of a line and a plane. As usual, a point on the line is PL = n + tŝ. At the intersection, PLp̂ = p so
(n + tintersectŝ)p̂ = p
tintersect = (p − np̂)/(ŝp̂).
Last edited Aug. 17, 2011
© 2011 by Aprend Technology and Robert E. Alvarez
Linking is allowed but reposting or mirroring is expressly forbidden.


[1] Philip Schneider, David H. Eberly: Geometric Tools for Computer Graphics. Morgan Kaufmann, 2002.