Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Working in two dimensions I have a point $P$, a line $AB$ defined by two other points $A$ and $B$, with $P$ not on $AB$. From another set of points, I need to find the nearest point to $P$ which is on the same side of the line $AB$ as $P$.

Working out the distances to $P$ is easy, and there are a number of formulae which give the distances to the line $AB$; but they don't give a sign which lets me know which side of $AB$ a point is on. I'm guessing that I can get this answer out by neglecting to take the square root in one of the formulae, and so I can just order the points by the squared distance and look only at the ones where it comes out with the same sign as the answer for $P$.

If this is the case, what's a suitable formula for the squared distance between a point $(x,y)$ and the line between $A=(x_a, y_a)$ and $B=(x_b, b_y)$ in terms of $x, y, x_a, y_a, x_b$ and $y_b$?

share|improve this question
    
One of the top hits on Google for "signed distance point line": softsurfer.com/Archive/algorithm_0102/… –  Rahul Mar 31 '12 at 17:40
1  
I think the answer depends on how you define "side", isn't it? Correct me if I'm wrong –  Bidit Acharya Mar 31 '12 at 17:42
    
@Rahul - ideal. Could you phrase that as an answer, so I can accept it? –  Simon Mar 31 '12 at 18:34

1 Answer 1

Your question is a little unprecise, are you looking at a line or at a line segment? If $g$ is a line (not a line segment) in $\mathbb{R}^2$ then the line subdivides $\mathbb{R}^2$ into two halfspaces. If $n$ is a unit normal to $g$ then the signed distance of a point $p$ to $g$ (with respect to $n$) is positive iff $p$ is in the halfspace into which $n$ points, otherwise it's negative (or zero if $p$ is lying on $g$). The absolut value of the signed distance is just the usual euclidean distance of the point to the line.

The signed distance is easily calculated, this is standard vector calculus: if $q$ is any point on $g$ and $v_q$ its position vector, and if $v_p $ is the position vector of $p$ then the signed distance from $p$ to $g$ is just the length of the projection of $v_p-v_q$ onto (any) normal line to $g$, which is simply

$$d= <v_p-v_q, n>$$

($<,>$ denoting the scalar product). Similar statements are true for hyperplanes in higher dimensional Euclidean space, the key word to look for is 'Hessian Normal form'.

I never heard about a signed squared distance, but I'd assume it is just the squared distance with a sign attached to it as described in the preceding paragraph. You should look up the definition, though.

Now if you are looking at a line segment $g_{AB}$ from $A$ to $B$ then the above formula ist only true if $p$ is actually lying on a line normal to $g_{AB}$ which really passes through some point on $g_{AB}$, otherwise it's just the euclidean distance to one of the end points $A$ or $B$ (the one which is smaller). If you need to assign a sign to that entity you could extend the line segment to a line and then use the above formula.

share|improve this answer
    
Good point about precision - I do mean line, not line segment. Thanks. –  Simon Mar 31 '12 at 18:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.