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

  • 1
    I think the answer depends on how you define "side", isn't it? Correct me if I'm wrong2012-03-31

1 Answers 1

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

(<,> 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.

  • 0
    Good point about precision - I do mean line, not line segment. Thanks.2012-03-31