3

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

Thom
  • 133
  • So to be clear, this a line of finite length? In 2 dimensions? – Alex R. Apr 23 '18 at 18:45
  • @AlexR yup, that's what I'm picturing. – Thom Apr 23 '18 at 18:48
  • You could set up a coordinate system $f:L \to \mathbb R$ on the line, sort the coordinates, and then go from there. – Steven Alexis Gregory Apr 23 '18 at 18:52
  • 1
    For repeated use where the likelihood of a reasonable proportion of the points could reasonably be close to the line, it might be worth creating the Voronoi diagram – Joffan Apr 24 '18 at 08:49
  • In your example, if $P_1,$ $A,$ $B,$ and $P_2$ all lie along one line in that order, then there are many ways to set up $d(P_1,A)<d(P_2,A)$ and $d(P_2,B)<d(P_1,B),$ so $P_1$ is "closer to any part of the line than" $P_2$ but $P_2$ is "closer to any part of the line than" $P_1,$ for example if $d(A,B)=10,$ $d(P_1,A)=1,$ and $d(P_2,B)=9.$ I am not sure if that is what you are trying to accomplish. – David K Apr 24 '18 at 08:49
  • @DavidK none of the points in P necessarily lie on the line AB. I've made another minor edit to hopefully clarify this. – Thom Apr 24 '18 at 08:57
  • @Joffan that would definitely work, if you wanted to write it up as an answer. – Thom Apr 24 '18 at 09:37
  • Right, the "on one side of the line" condition rules out collinear points. OK, let $d(A,B)=1$, let $P_1$ be "some distance" from the line and "outside" $A$ and exactly $100$ units of $A$, let $P_2$ be "some distance" from the line and "outside" $B$ and exactly $100$ units of $B,$ and let every other point be more than $100$ units away from the line. Then it is still the case that both points $P_1$ or $P_2$ are "closer to any part of the line than any other" according to your formula, $\exists P_j, d(P_j,A)<d(P_i,A) \cap d(P_j,B)<d(P_i,B).$ Is that what you want? – David K Apr 24 '18 at 12:44

3 Answers3

1

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).

Rob Arthan
  • 48,577
  • Many apologies if the question was phrased badly - I've attempted to do a better job. I'm not just interested in the nearest point on the line to a given P, I want to know if there is any point on AB to which P is closer than the all other points in P. – Thom Apr 24 '18 at 08:38
0

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

Alex R.
  • 32,771
  • Many apologies if the question was phrased badly - I've attempted to do a better job. I'm not just interested in the nearest point on the line to a given P, I want to know if there is any point on AB to which P is closer than the all other points in P. – Thom Apr 24 '18 at 08:38
  • So the above still works, right? You just need to compute it for every single point and then infer which is closest by computing the resulting distances – Alex R. Apr 24 '18 at 17:11
0

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:
enter image description here

Joffan
  • 39,627
  • Voronoi diagrams are great, but I don't see any efficiency gain in calculating one to solve multiple instances of this problem with different lines and the same set $P$: the "polygon-meets-line-segment" test you have to do for each cell is surely more computation than calculating the distance from the point that lies in the cell to the line segment. Or am I missing an optimisation trick? – Rob Arthan Apr 24 '18 at 18:26
  • @RobArthan I guess I was interpreting the problem more in the spirit of finding that portion of the line segment closest to a given point. – Joffan Apr 24 '18 at 18:39
  • I see your reading of the original question and with that reading I definitely agree with you. But I don't think the OP's edited question is compatible with that reading. – Rob Arthan Apr 24 '18 at 18:55
  • Apologies again if the question is fuzzy. This method probably is overkill, but does definitely solve the problem I have, which is merely a yes/no answer to whether there is any point on the line which is closer to a given P compared to other Ps. This is not guaranteed to be the closest point between the line and P. – Thom Apr 25 '18 at 10:06