Find whether a point is closer to any part of a line than other points

Question

Given an finite line segment $\overline{AB}$, and a set of points $P$ lying some distance away on one side of the line, what would be the general way to check, for any given point $P_i$, whether it is closer to any part of the line than any other point in $P$?

For the case where $P_i$ is outside the endpoints of the line, it's as simple as checking whether $\exists Pj\, d(Pj,A)<d(Pi,A) \cap d(Pj,B)<d(Pi,B)$ where $d$ is a distance function. However, when the point is between the endpoints of the line, it seems more complex - the nearest point on the line to $P_i$ could be closer to $P_j$, but some other point on $\overline{AB}$ might still be closer to $P_i$.

Answer 1

The question suggests to me that this query might be made repeatedly, either on the given line or on a succession of lines. If this is also associated with a fixed population of points over a reasonable number of queries, it might be worth creating the Voronoi diagram for those points, which describes the nearest neighbourhood for each point.

Then any point on the line segment - including the end points - would fall within one of the described cells that represent the portion of the plane that is closer to that point than any other. The portion of the line that is closer to a given point than any other would be exactly that part of the line segment that is crosses the corresponding cell in the diagram.

Example Voronoi diagram from Wikipedia:

Answer 2

What I think you are missing is that for any point $p$, there is a unique point, $q(p)$, on the line segment $\overline{AB}$ that is nearest to $p$. In general, there is a well-defined notion of distance between two arbitrary non-empty subsets of the plane $X$ and $Y$, say, defined by: $$ d(X, Y) = \inf \{d(x, y) \mid x \in X, y \in Y\} $$ (where $\inf$ gives the greatest lower bound of a bounded-below non-empty set of real numbers). In your case, take $X = \overline{AB}$ and $Y=P$. Because $P$ is finite there will be at least one $p \in P$ such that $ d(q(p), p) = d(\overline{AB}, \{p\}) = d(\overline{AB}, P)$ and it is the point or points with that property that you are trying to find.

To find $q(p)$ for any given $p$, you first of all find the orthogonal projection, $p_o$ say, of $p$ onto the infinite extension $\overline{AB}$ (which you can do with a bit of vector arithmetic involving the dot product operation). $p_o$ is the closest point to $p$ on the infinitely extended line. If $p_o$ lies on $\overline{AB}$, then $q(p) = p_o$; otherwise $q(p)$ is whichever of $A$ and $B$ is nearer to $p$. (Note that $p$ cannot be equidistant from $A$ and $B$ if $p_o$ does not lie on $\overline{AB}$.)

To find the $p \in P$ and the corresponding point $q(p)$ that you are looking for, you just repeat the above construction for every $p \in P$ and then choose a $p$ that minimise $d(q(p), p)$ (there may be more than one such $p$ in general).

Answer 3

You can always parametrize your line as $y(t)=at+(1-t)b$, where $a,b$ are the vectors corresponding to the line's endpoints. For any other point $z$, then there are two cases to compare. First check if $z$ lies outside the endpoints of the lines, specifically if $(z-b)\cdot (b-a)>|b-a|^2$ or $(z-a)\cdot (a-b)>|b-a|^2$, in which case the closest point will be the corresponding endpoint. Otherwise, the closest point will be the one corresponding to the perpendicular connecting the line to your point, which can be determined by solving $(z-[at+ (1-t)b])\cdot (b-a)=0$ for $t$.