0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ One of the top hits on Google for "signed distance point line": softsurfer.com/Archive/algorithm_0102/… $\endgroup$ – Rahul Mar 31 '12 at 17:40
  • 1
    $\begingroup$ I think the answer depends on how you define "side", isn't it? Correct me if I'm wrong $\endgroup$ – funktor Mar 31 '12 at 17:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good point about precision - I do mean line, not line segment. Thanks. $\endgroup$ – Simon Mar 31 '12 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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