How to calculate the shortest distance between a point and a line?

Some problems are easy to solve using pen and paper, but suddenly become hard when you have to express things in mathematics. In this blog we will discuss one such case:

What is the shortest distance between a point and a line (or line segment, or ray)? And what are the coordinates of the point on the line that is closest?

We will go from idea to code in four steps:

  1. We sketch the solution for a line, a line segment and a ray.
  2. We use linear algebra to define the vector equations that solve the problem in an N-dimensional space.
  3. We implement the equations in M-code
  4. We turn the code snippets into a robust MATLAB function

The resulting MATLAB function is available for download.

Drawing the solution

We solve the problem graphically, by drawing it in 2D. Two points, A and B, define the line, line segment or ray. P is the independent point. The figure below shows how we construct the distance (red, dashed) and closest point (C). We consider three cases:

  1. A line through A and B (the top row)
  2. A line segment AB (the middle row)
  3. A ray which starts at A and passes through B (the bottom row)

The difference between these cases becomes clear when we consider the intersection point of the line through A and B and the perpendicular through P. The closest point can be the intersection point, or A, or B:

  1. For a line, the intersection point is the closest point.
  2. For a line segment, if the intersection point is on line segment AB, this is the closest point (middle column). If the intersection point is outside segment AB, the closest point is the end of the segment (left and right column).
  3. For a ray, if the intersection point is on the ray, this is the closest point (middle and right column). If the intersection point is not on the ray (behind source A), the closest point is source A (left column).

DistanceToLineSegmentRay

This approach provides insight, but is limited: we need a ruler to measure the distance, an it only works in 2D.

Putting it into math

The next step is to define a set of vector equations that solve the problem in N dimensions.

Let \(\vec{A}\) and \(\vec{B}\) be two points on line \(\vec{L}\). \(\vec{P}\) is the independent point, which is not on the line.

The vector equation of the line is:

\(\vec{L}(t) = \vec{A} + t\vec{M}\) (Eq. 1)

with \(t\) the running parameter and \(\vec{M}\) the direction vector:

\(\vec{M} = \vec{B} – \vec{A}\)

The running parameter can take different values for a line, line segment and ray:

  • A line is infinite,  so \(t \in (-\infty, \infty)\)
  • A line segment is finite, so \(t \in \left[0, 1\right]\)
  • A ray is semi-infinite, so \(t \in [0, \infty)\)

We need to find the orthogonal projection of our independent point \(\vec{P}\) on line \(\vec{L}\). This can be done by using dot products, as follows:

\(\vec{L}(t_0) = \vec{A} + \left[\frac{(\vec{P}-\vec{A}) \cdot \vec{M}}{\vec{M} \cdot \vec{M}}\right] \vec{M}\) (Eq. 2)

From Eq. 1 and Eq. 2 follows that \(t_0\), the value of the running parameter at the intersection of \(\vec{L}\) and its perpendicular through \(\vec{P}\) is:

\(t_0 = \frac{(\vec{P}-\vec{A}) \cdot \vec{M}}{\vec{M} \cdot \vec{M}}\)

Now that we have all the parameters, we can calculate the shortest distance \(d\).

In case of a line:

\(d = \left|\vec{P} – (\vec{A} + t_0\vec{M})\right|\)

In case of a line segment:

\(d = \left\{ \begin{array}{ll} \left| \vec{P} – \vec{A} \right| & t_0 \leq 0 \\ \left| \vec{P} – (\vec{A} + t_0\vec{M})\right| & 0 < t_0 < 1 \\ \left| \vec{P} – \vec{B} \right| & t_0 \geq 1 \end{array}\right.\)

And in case of a ray:

\(d = \left\{ \begin{array}{ll} \left| \vec{P} – \vec{A} \right| & t_0 \leq 0 \\ \left| \vec{P} – (\vec{A} + t_0\vec{M})\right| & t_0 > 0 \end{array}\right.\)

Drafting the implementation

We only need a few lines of code to implement the linear algebra equations MATLAB.

  • Direction vector \(\vec{M}\):
  • Running parameter at the orthogonal intersection \(t_0\):
  • Intersection point:
  • Distance \(d\) between independent point and closest point:

Implementing a function

The last step involves coding a robust, documented, and readable MATLAB function. At least three input arguments are required: the points A and B that define a line and test point P. The optional fourth input argument specifies the line type: 'line' (the default), 'segment' or 'ray'. The function returns up to three outputs: distance d, closest point C, and running parameter at the orthogonal intersection t0. The function definition line reflects this:

Download the distancePoint2Line() function here to inspect the full implementation and to use it for your work.

How to keep your Simulink customizations organized?

Simulink and Stateflow offer ways to customize the modeling environment. You may for example add a menu to the Simulink Model Editor, or add menu items to existing Model Editor menus. Customizations are a practical way to create shortcuts, allowing you to be more productive in Simulink. However, it can be hard to keep a clear oversight of the customization implementations. The two main reasons are:

  1. Each customization needs a function to implement the callback, and a function to register it. In addition, separate functions are required to define and register the menu with the Simulink Customization Manager. Consequently, if you have multiple customizations for diffent projects or contexts, the number of functions will grow rapidly, and significant bookkeeping is required.
  2. If you work on different projects you might want to make a selection of the customizations you find useful. Or, you might want to target customizations to a specific context. In these cases, the default approach, a single sl_customization.m file with numerous sub functions, will be cumbersome. The alternative approach, multiple sl_customization.m files in different folders, may lead to a messy folder structure.

This calls for a structured approach. Below we present one, and share the code.

EDIT 22 March 2017: Code and MATLAB App can be found on GitHub and MATLAB Central File Exchange from now.

Example

In the example below we add the menu “My Menu” to the Simulink Editor’s menu bar. It contains two custom utility commands.

keep_work_organized_menu_small

The first, “Match Size”, matches the size of selected blocks. This can also be arranged via the Simulink context menu, however the customization adds a keyboard shortcut to it.

MatchSizes

The second, “Make Constants Orange”, colors all Constant blocks in a model orange, which reflects a convention.

ColorBlocksOrange

The unstructured approach

All code is in one sl_customization.m file, which has six sub functions. It works, but if you want to add more customizations this file will soon grow to a size that is no longer maintainable.

The structured approach

The two customizations in our example originate from different contexts: one is a general utility, the other part of a style guide. In the structured approach, separate packages (+styleguide, +utils) reflect the different contexts. Both packages contain a Customizer class. A single sl_customization.m file points to the Customizers employed in our model.

keep_work_organized_folder_structure

The idea is that we separate the definition of the custom menu and its contents from the implementation of the customizations. This way, we can add or remove menu items by editing a single line in sl_customization.m. Also, if we add customizations to a package, they will automatically appear in our custom menu.

The implementation reflects this separation. A generic class Customizer is the super class of the Customizer classes in the package folders. The super class contains a helper method getCustomizeMethods that will automatically assign the customizations to the menu. The customizers variable in sub-function customMenu (line 27) defines the items in menu “My Menu”. The Customizer super class will place a separator between customizations from different packages.

The Customizer class in the +utils package implements the details for the “Match Size” menu item: a registration method matchSizeOfBlocks and a callback sub-function matchSizeOfBlocksCb.

Similarly, the Customizer class in the +styleguide package implements the details for the “Make Constants Orange” menu item. 

In short, this structure allows to easily scale up the number of customizations. Also, it facilitates sharing and re-use. The full implementation of the structured approach is available for download. Use it to automate your repeat work and be more productive in Simulink/Stateflow!

EDIT 22 March 2017: Code and MATLAB App can be found on GitHub and MATLAB Central File Exchange from now.