Friday, September 6, 2013

Snap Perpendicular Code

"Snap perpendicular" is a way certain drawing programs (like AutoCAD and DraftSight) help the user to draw a line starting from some point C and draw it up to an existing line such that the new line is perpendicular to the existing one.  What would we do without "snap perpendicular"?  The alternative, I suppose, would be to hold a set-square on the computer screen.  Or, calculate the destination point.  Of course, the aforesaid programs do just that.  And so does the Maxima code at the end of this post.


We're given an existing line segment AB in space and a point C.  We want to find a point P on line AB such that line segment CP is perpendicular to AB.  (We won't worry about whether it is on the line segment AB, just on the line AB; we omit a "range check".)  We observe that the perpendicular distance between a point and a line is the shortest possible distance and so we will treat this as a minimization problem, using the methods of calculus.  Let A = (Ax, Ay, Az) and similar for points B and C.  Then line AB is described by the parametric equations:

      x(t) = Ax + (Bx – Ax) t,
      y(t) = Ay + (By – Ay) t,
      z(t) = Az + (Bz – Az) t,

where P(t) = (x(t), y(t), z(t)).  We want to find P(t) such that line segment CP(t) is as small as possible, which is equivalent to finding when the square of the distance is minimized.  So, we define

D(t) = (C– x(t))2 + (C– y(t))2 + (C– z(t))2
       = (Cx – Ax – (Bx – Ax) t)2 + (Cy – Ay – (By – Ay) t)2 + (Cz – Az – (Bz – Az) t)2.

Taking the derivative yields:

D'(t) = 2 (Cx – Ax – (Bx – Ax) t) (– (Bx – Ax)) + 2 (Cy – Ay – (By – Ay) t) (– (By – Ay)) +2 (Cz – Az – (Bz – Az) t) (– (Bz – Az))

We solve for t when D'(t) = 0 as follows:

0 = (Cx – Ax – (Bx – Ax) t) (Bx – Ax) + (Cy – Ay – (By – Ay) t) (By – Ay) + (Cz – Az – (Bz – Az) t) (Bz – Az)

[(Bx – Ax)2 + (By – Ay)2 +  (Bz – Az)2] t = (Cx – Ax)(Bx – Ax) + (Cy – Ay)(By – Ay) +  (Cz – Az)(Bz – Az)

t = [(Cx – Ax)(Bx – Ax) + (Cy – Ay)(By – Ay) +  (Cz – Az)(Bz – Az)]/[(Bx – Ax)2 + (By – Ay)2 +  (Bz – Az)2],
which can be stated more succinctly in vector notation as
\[t = \frac{(B-A)\cdot (C-A)}{(B-A)\cdot (B-A)}\]
from whence derives the below Maxima code:

To prove that the point thus obtained is indeed the desired "Snap Perpendicular" point, it would be sufficient to show that the dot product of the vectors (A – B) and (C – P) is equal to zero, which check I omit.

No comments: