Hacker News Reader

What's the distance between a point and a line segment?

let A, B be the 2D start and end points of a line segment. Let P be a 2D point.

We think about the problem and graph the problem like this:

            P          
            .          
                       
                       
                       
                       
  A ------------------------ B

Then we realize that we can re-frame the problem in terms of a right triangle:

            P          
            .         
          / |         
        /   |         
      /    _|         
    /     | |         
  A ------------------------- B
            Q

Now for some definitions. Let's define the vector operations that we'll be working with.

  class Vec2( object ):
    def __init__( self, x, y ):
      self.x = x
      self.y = y

This represents a 2D vector with properties 'x' and 'y'.

  def length( V ):
    return sqrt( V.x*V.x + V.y*V.y )

This computes the length of a 2D vector.

  def normalize( V ):
    V_len = length( V )
    return Vec2( V.x / V_len, V.y / V_len )

This computes a new vector that points in the same direction as V, but is of unit length ( length( normalize( V ) ) == 1.0 ).

  def dot( V1, V2 ):
    return V1.x*V2.x + V1.y*V2.y

This computes the "dot product" between two vectors. I'll clarify this operation in a moment.

Finally, for clarity and succinctness:

  V1 + V2 represents Vec2( V1.x+V2.x, V1.y+V2.y )

  V1 - V2 represents Vec2( V1.x-V2.x, V1.y-V2.y )

  S * V represents Vec2( S*V.x, S*V.y ), which 
  scales the vector V by a factor of S.  So (2.0 * V)
  would result in a vector in the same direction as V,
  but twice as long.

Goal: find the length of PQ

First, we examine our graph above and write out the known and unknown quantities.

  AB = B - A
  AP = P - A
  AB_len = length( AB )
  AP_len = length( AP )
  Q = ?
  AQ = Q - A
  PQ = P - A

It looks like our first step is to compute Q.

A dot product trick

The trick we'll use to solve this is via the following rule:

For any line that passes through A and B, dot( normalize( B - A ), P - A ) is the distance between A and the closest point on the line to P.

Huh?

Let me explain this thoroughly, so you can add it to your own toolbox for your entire life.

Building an intuitive understanding of vector math

Imagine a line segment AB and a point P. Now picture point Q, which is the closest point to P on a line that passes through A and B, just like the graph above. You can use the dot product to find the distance between A and Q.

First, compute the vector AB by computing (B - A).

You can visualize this as follows. Picture a line segment from point A to point B. Now move it so that A is coincident with the origin (0,0). Since you moved it, you didn't change its length and you didn't change its direction, just its location. So the result of (B - A) could be intuitively described as "a line segment that begins at the origin (0,0) whose length and direction are equal to AB's".

The next step in the dot product trick is to set the length of (B - A) to 1.0, which is "unit length". A few related trivia notes:

- if a vector's length is exactly 1.0, then it is called a "unit vector".

- when you set a vector's length to 1.0, you have just "normalized" the vector.

- normalized vectors are a succinct way to represent a direction in space, whether it be 1D, 2D, 3D, or any other D.

- remember the 2D line equation "y = mx + b"? 'm' is the line's slope. In 2D space, slope is just an alternate way of representing a vector's direction. You can compute a vector V's slope as "rise over run" (V.y / V.x). The only advantage of using slope to represent a direction in 2D is that it's efficient to compute and to use. There are two big disadvantages. First, it's not immediately clear how we'd compute slope in 3D. But more importantly, you can't represent vertical lines with a slope. A vertical line has no 'run', so (V.x / 0.0) == undefined. In programming terms, this could cause problems. So slope is generally avoided for those reasons. I explained it here because I am hoping that it helps you to understand vectors more intuitively.

So, let's enumerate some features of unit length vectors:

- they can be used to represent any direction in space.

- the range of each component of a unit length vector is never outside of [-1.0 .. 1.0].

- if you compute the dot product between a unit length vector and a point, you have projected the point onto the vector. The result of the dot product is the distance between the origin and the closest point on the vector. -- dot product trick

- the dot product of two unit length vectors is equal to the cosine of the angle between them. In other words, let V1 and V2 be unit length vectors. dot( V1, V2 ) == cos( angle between V1 and V2 ). Related facts:

-- the dot product of two unit length vectors is always in the range [-1.0 .. 1.0].

-- if V1 points in the same direction as V2 (that is, V1 == V2), then the dot product is 1.0.

-- if V1 is perpendicular to V2, then the dot product is 0.0.

-- if V1 points in the opposite direction of V2 (that is, V1 == -V2), then the dot product is -1.0.

-- And now, for something fun (and totally optional -- if you don't really understand, don't sweat it. But hopefully it will be interesting rather than confusing): Imagine a light bulb at point L. Now imagine a sphere at point S, being lit by that light bulb. Imagine a point on that sphere, P. You can compute the lightbulb's effect on the sphere at that point as follows:

  L = lightbulb position
  S = sphere position
  P = point on sphere
  Ldir = normalize( L - P )
  surface_normal = normalize( P - S )
  light_intensity = max( 0.0, dot( surface_normal, Ldir ) )
  # that quanitity is called "NdotL" in computer graphics.
  # you would then multiply that quantity by the light's
  # "attenuation", which dims the light as it gets further
  # away.  But that's outside the scope of this example.
  # If you're interested in computer graphics, 
  # the book "Realtime Rendering" is fantastic.

Solving the problem, finally.

So, let's use our newfound ninja-guru knowledge of vectors and dot products to solve the original problem. After glancing at the above graph again, we remember we need to compute the length of the line segment PQ. One way to solve it is to compute the point Q, then length( Q - P ) is our answer. Getting down to business:

  def dist_point_to_line( A, B, P ):
    # represent the line segment AB as a vector.
    AB = B - A

    # determine the direction of B relative to A.
    AB_dir = normalize( AB ) 

    # compute the distance between A and Q using the dot
    # product trick.  The first argument is a unit length
    # vector.  The second argument is a point *relative to
    # that vector*.
    AQ_len = dot( AB_dir, P - A )

    # Now that we know the length of AQ, we can compute Q.
    # To do this, think of the following equation as "start
    # at A; move along the direction AB_dir by AQ_len units;
    # that position is Q."
    Q = A + AQ_len * AB_dir

    # return the length of PQ.
    return length( Q - P )

I hope the explanation was been illuminating, and not too confusing. If you have any questions, feel free to ask.

- normalized vectors are a succinct way to represent a direction in space, whether it be 1D, 2D, 3D, or any other D.

I'll only add that they are called versors and one can read more about their magic in any material about quaternions.

On a related note, Visualizing Quaternions is a great book.

I got bad news. The question was to find the distance between a point and a line SEGMENT.

Luckily, since you know some math, and you understand what a dot product is, and how it relates to a projection, you can trivially extend your solution by checking to make sure Q is on AB, and then adjusting your answer if its not.

:)

Ahh, yes. Good catch. In the algorithm, simply clamp AQ_len to be >= 0.0 and <= AB_len. (Notice that you compute AB_len as a side effect of normalizing AB.)

There's also the trick way to do it, namely the distance from (x0,y0) to the line ax+by+c=0 is |ax0+by0+c|/sqrt(a^2+b^2)

This has the advantage that it generalizes to arbitrary dimensions. For example, you can do it to find the distance from a point to a plane (|ax0+by0+cz0+d|/sqrt(a^2+b^2+c^2)). The math behind it is pretty much the same, except you're projecting onto a normal instead of onto the line itself.

"if we're going to talk about math, let's get out of the abstract and into the specific. Let's talk details. Examples. What could be more math-y than that?" (from the codinghorror post)

This topic seems to come up relatively frequently, and I appreciate Jeff's attempt to add to the conversation with some interestingly selected quotes. Still, the above quote to me highlights how many people, including Jeff, vastly oversimplify the math side of the equation. To put lbrandy's comment slightly differently, knowing a large number of mathematical facts will not make you a good programmer. But to me a basic explanation of “mathematical inclination” could be: a strong understanding of how a mathematical system is governed by rules, and how a problem can be parsed, compartmentalized, and addressed in pieces. It seems fairly self-evident to me that those skills would be shared by anyone whol could be described as even a competent programmer.

On the topic of the applications of mathematical thinking to programming, I immediately thought of this:

http://www.zedshaw.com/essays/programmer_stats.html

>What's the distance between a point and a line segment?

I think I agree with you. I would argue that the mathematical ability needed to solve the question above is to realize how to phrase a query to google, find the resulting formula, and turn it into code. You don't need to be able to derive it, for the vast majority of jobs out there.

Also: I've noticed that most programming is equivalent to what in grade school and high school they called a "word problem". Most of the class would groan when we had to do these; I loved them. I suspect if you struggled with word problems, you would have a hard time programming.

phrase a query to google, find the resulting formula, and turn it into code

You left out the part where, months later, you pay a mathematically-inclined consultant hundreds of dollars to fix the bugs in the formula that you cut and pasted without understanding it. ;)

Numerical methods was a very interesting class, even on day one. You'd be amazed how easy it is to screw up simple formulas by doing the math in the wrong order -- the finite precision of floating-point arithmetic means that you have to be constantly on your guard.

>> If you see someone sorting papers and try to figure out why they are doing it inefficiently, that is mathematical inclination.

Not really, I would say it was a logical inclination not necessarily a mathematical one. And therein is the rub I see programming as logic and problem solving with little to no inherent math unless I am dealing with a mathematical problem. Kind of like the way writing books is not an inherently mathematical in nature even if quite a bit of math is involved in writing a mathematics text book.

This is bordering on semantics. What's the difference between mathematical inclination and logical inclination? The field of computer programming has made a separation in alot of people's mind that simply didn't exist before. People, especially programmers, view mathematics far too narrowly because they lack historical context.

George Boole was a mathematician. The logic textbooks are full of words that betray their background, e.g. the "lambda calculus". All of these things have their roots in mathematics. And before there was computer science degrees, these things -were- mathematics.

I doubt, very seriously, that Djikstra would draw much of a distinction between "logical inclination" and "mathematical inclination". So while you might, the original context of the quote in question needs to be considered.

Agree fully with lbrandy's point. Just to add a little more, people seem to get confused between the expression of mathematical thoughts and having mathematical thoughts. Mathematical symbols are abbreviations for ideas that, if expressed in natural language, would become tedious. Mathematical thinking is something people do everyday. For example, parents have to use combinatorial optimization everyday to figure out a best strategy for running errands. Few parents are schooled to a formal expression of the mental processes they go through in determining a solution but they weigh different goals and optimize nonetheless.

Oddly, a study that is all about exploration of ideas and abstraction has been narrowly defined in many people's minds. Hopefully mathematics educators can break these limited views in years to come.

Maybe it's my engineering background, but I don't feel like this is semantics - it's unfair to categorize logical thinking as "mathematical" thinking. There are plenty of us from different backgrounds who are big on logic, and IMHO make great programmers. Mathematicians are far from the only ones who can think logically, and the term is at least somewhat misleading.

Uh, logic is a branch of mathematics. From wikipedia:

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical trivium, as well as a branch of mathematics.

potatolicious has a point.

In fact, in universities, logic (formal logic, with symbols) is usually taught by philosophy departments.

That raises an interesting question, doesn't it? I wonder how many mathematicians turn out to be good programmers vs how many philosophers turn out to be good programmers?

From experience, I have concluded that whether mathematicians become good programmers depends on whether they have an engineering aesthetic. Mathematical elegance and engineering elegance are not exactly the same thing. A mathematically trivial solution can be a huge practical mess. Mathematicians with no engineering aesthetic can't see the difference and tend to produce big blobs of unmaintainable code. Mathematicians with an engineering aesthetic are some of the best programmers I've worked with.

I've only worked with one philosopher. He's very creative and produces reams of working code, but new requirements always mean new reams of code. Everyone suspects there must be a lot of redundancy in his code, but then, nobody has needed to look, because it all works....

Only by tradition, and in my experience the philosophy department only teaches the class that serves to introduce formal logic to all undergrads. Philosophers deal with words. They like to discuss the various ways a verbal problem might be reduced to logic, and they might be interested in what can be said (in terms they already use) about a system of logic, but that's the limit of their interest. If you take a graduate-level math class in logic (or metamathematics or foundations or whatever your local math department calls it) or even if you just take an upper-division set theory class, you'll learn more about mathematical logic than anyone in the philosophy department wants to know.

the philosophy department only teaches the class

Most or all undergrad pure logic classes, as far as I've ever seen. There aren't usually a whole lot of pure logic classes, so it's entirely possible that your school(s) might only have had one.

Philosophers deal with words.

Philosophers deal with logic in arguments. I took a couple logic classes during my undergrad and they were entirely symbolic logic. I also took a couple philosophy classes, and they used symbolic logic extensively to describe the flow of logic in arguments. Skimming through MIT OpenCourseWare indicates it's similar there: http://is.gd/qaE0

If you take a graduate-level math class in logic ... even if you just take an upper-division set theory class, you'll learn more about mathematical logic

So you are saying that heavily mathematical logic is more heavily mathematical? Interesting. Do you also learn about tautologies in these classes?

I'm guessing that you are actually implying that mathematical logic is more useful to programmers. As I stated elsewhere, during my undergrad I took classes that touched on both philosophical and mathematical logic concepts and I definitely find myself using both. In my experience: symbolic/philosophical concepts in high level development, symbolic/mathematical concepts in low level development.

The distinction I'm making is between logic that is purely symbolic, where conclusions follow mechanically from assumptions and rules, and logic that is applied to verbal argument. You can describe verbal argument using symbolic logic, but applying symbolic logic to words easily results in ludicrous conclusions unless you apply other filters.

I'm not saying that mathematical logic is more heavily mathematical, I'm saying that philosophers are only interested in mathematical logic concepts they can extract from their mathematical context and apply in words. Aside from that, they are not interested in mathematical logic at all. Whether they are interested in mathematically defined concepts such as "complete," "consistent," and so forth depends entirely on whether the concepts have suggestive names that seem to imbue mathematical results with meanings beyond mathematics.

I'm arguing that the application of logic to arguments and ideas that was part of philosophy has greater impact on high level application design and architecture than math. Taking a real world concept, need or set of actions and translating them into a structure that can be constructed with a programming language uses logic in fundamentally the same way philosophy does, although in an academic setting this area is computer science. Math is most useful at an implementation level, generally coming into play when dealing with components, algorithms and other more narrow implementation details.

The point is that logic used in computer science/information science is a hybrid that is informed by other forms of logic (including linguistics), not just math.

I'm saying that philosophers are only interested in

I don't know what philosophers are only interested in because I don't know what a "philosopher" is.

I think I misunderstood you; I thought you meant mathematical logic (the kind that can be generated mechanically from axioms and rules) and not the kind of logic that requires judgment and applies to words and concepts. If you meant the second kind, then I retract what I said. But you did say, "formal logic, with symbols," and that kind of logic is a pretty weak tool to apply to arguments and ideas.

As for what a philosopher is, we're all philosophers, but not all of us get paid for it.

Why would you consider unfair to call logic thinking as mathematical thinking? Maybe it is the engineering background indeed, at least it is for myself. Maybe it was all those "engineering math" mandatory courses... you know, calculus, differential equations, linear algebra, statistics. If we keep thinking about math in terms of some sort of computation which ought to result in a numeric answer... then, absolutely, I agree that has nothing to do with logic.

However, least see what happens when one does not apply mathematical thinking into his own reasoning. I do it myself from time to time and refer to it as my "rat intelligence". You go over and over the facts, one at a time, trying to figure out the way out... It feels pretty much like a rat walking through a maze inside of my brain.

But it comes to a point, when the problem is very hard, that no matter how many times the rat goes over and over the same data, it does not find the answer. In that case you need a superior type of reasoning. You need to step aside and look at the problem as a whole. To find patterns that you can abstract out and rephrase the problem in a way more tractable. And I think in this broader sense logic and math use the same type of mental tools (principles) to attack the same issues.

Actually, all of those computations "which ought to result in a numeric answer" are done according to the principles of logic. Maybe I see it more clearly having taught myself calculus and more advanced math without having someone to "explain" things to me, but all mathematical problem solving is also logical reasoning.

What's the difference between mathematical inclination and logical inclination?

Logic is a strange area since it bridges fields, primarily math, philosophy, linguistics and computer science.

In my experience, designing software more frequently taps into logic as applied to philosophical arguments and conceptual formal logic more than heavily mathematical areas of logic. The reason is that creating software is basically the process of taking something from the real world and reducing it to a series of logical components and relationships. This is pretty much the exact process for applying formal logic to philosophical questions.

On the other hand, actually coding the software taps far more into the mathematical and linguistic aspects of formal logic, since it's involves piecing together units of mathematical logic to construct a logical machine.

In practice, this whole process is obviously more nuanced, interconnected and filled with gray areas.

It's also certainly possible to argue that all reasoning is math, but this isn't a new concept and dates back to Plato.

>What's the distance between a point and a line segment?

Does anyone have an elegant solution?

Draw a triangle; Do the trig.

Between any arbitrary point on a line segment, the point on the line segment that contains the shortest point, and the point in question, you have a triangle.

You can take the length between any point on the line segment and the point in space, find it's magnitude squared, and subtract the magnitude squared of it's projection along the line segment. This gives you the distance of between the point and line segment squared by pythagoras' theorem.

         x
        /|
       / |
      /  |
    -a****-----

a is the arbitrary point on the line, the *s are the projected segment, and x is the point you want to find the distance from.

I'm not sure, but that sounds like the answer to a different question: what's the distance between a point and a line.