Given a set of coordinates on a euclidean plane, is it possible to sort the points by sweeping a line through them where the line might not be strictly horizontal or vertical? The inputs to the problem would be the set of unsorted 2d points, and a unit vector.
I know that for a simply vertical or horizontal sweep line, you obviously only need to account for the x value (for a vertical sweep) or the y value (for a horizontal sweep). But if the sweep were to follow some arbitrary vector, I'd imagine the sort has to take in to account some sort of component of the angle of that vector.
Example drawing: a field of points to be sorted
The red line is the sweep line that I'm envisioning, and the grey dashed vector denotes the direction I want the sweep to occur such that the resultant order in this example would be [A, B, C, D, E].
I thought one possible solution might be to first reduce the points to all be on the path of the vector, but I'm not sure how to do that. Then it should become a simple order by x or y component of each point.
Another solution might be to rotate the plane so that the sweep becomes a simple vertical or horizontal sweep, but I'm not sure how to do that either.
If this question is better posed in a different part of stack exchange?
In the answer below, I use "points" and "vectors" interchangeably. So, for example, we might think of $(a,b)$ at the point in the plane or as the vector in the plane that goes from the origin to $(a,b)$.
Also, I'm assuming that either there won't be any ties (points that the line hits at the same time) or that if there are ties, you are indifferent to how the tied points are ordered.
Suppose we are given the direction vector $$u=\begin{pmatrix} x_0 \\ y_0\end{pmatrix}.$$ Suppose also that we have an ant riding a line that's perpendicular to $u$ and traveling along $u$ with speed $1$ (the orange line in the photo is a snapshot of the line at one point in time, and the point of intersection of the line and the vector $u$ is where the ant is sitting). he ant is very tired, so she does not walk up/down the plane. So she also moves in the direction of $u$. We can assume the ant has been traveling for all of history and will travel forever, and is at the origin at time $0$. We could change any of these assumptions (the ant only travels between certain times/is at the origin at a different time/travels at a different speed). This doesn't affect the sorted list of points at the end, though, because (assuming the ant hits all the points in the time window), she will hit them in the same order no matter what.
Recall the dot product $a\cdot b$ of two vectors $a,b$. If $a=(x_1,y_1)$ and $b=(x_2,y_2)$, then $a\cdot b=x_1x_2+y_1y_2$. Recall also that, by the Pythagorean theorem, the length $\|a\|$ of a vector is given by $\|a\|=\sqrt{a\cdot a}$.
Let $$N=\frac{u}{\|u\|}=\frac{u}{u\cdot u}=\frac{1}{\sqrt{x_0^2+y_0^2}}\begin{pmatrix} x_0 \\ y_0\end{pmatrix}.$$ This step isn't strictly necessary, but it helps the discussion. Note that $N$ has the same direction as $u$, and length $1$.
The ant's position at time $t$ is $tN$. That's because $tN$ is the path in the direction of $N$ (and therefore in the direction of $u$) which has speed $1$ and is at the origin at time $t=0$. So at time $t$, the line the ant is riding is the line containing the point $tN$ and which is perpendicular (orthogonal) to $N$ (which is the same as perpendicular to $u$). We check orthogonality by the dot product. That is, a vector $d$ is orthogonal to $N$ if and only if $N\cdot d=0$. So the orange line consists of all the points that we can reach by starting at $tN$ and moving along a vector $d$ which is orthogonal to $N$, to end up at $tN+d$ with $d\cdot N=0$. In other words, at time $t$, the orange line is $$L_t=\{tN+d:d\cdot N=0\},$$ where $d$ ranges over all vectors orthogonal to $N$. Note that if $v=tN+d\in L_t$, then $$N\cdot v=N\cdot (tN+d)=t N\cdot N+N\cdot d=t\|N\|^2+0=t\cdot 1=t.$$ Here we used that the dot product is distributive, commutative, and commutes with scalar multiplication. Therefore if a point $v$ is on the orange line at time $t$, we have $N\cdot v=t$.
On the other hand, if $N\cdot v=t$, define $$d=v-tN.$$ Then, by definition of $d$, $v=tN+d$. Moreover, $$t=N\cdot v = N\cdot (tN+d)=t(N\cdot N)+N\cdot d=t+N\cdot d,$$ from which it follows that $N\cdot d=0$. So $v=tN+d$ and $N\cdot d=0$, which means $v\in L_t$ (in other words, $v$ is on the orange line at time $t$). Therefore we have shown that at time $t$, the orange line is exactly the set of points $v$ with $v\cdot N=t$. Therefore taking the dot product of a vector $v$ with $N$ tells us the "time of impact" of that point with the sweeping orange line. So if we have our unsorted input list of points $v_1,v_2,\ldots, v_p$, the values $v_1\cdot N, v_2\cdot N, \ldots, v_p\cdot N$ tells us the impact times. So if we want to order the points from first hit to last hit, we order them as $v_{i_1}, \ldots, v_{i_p}$ so that $v_{i_1}\cdot N, \ldots, v_{i_p}\cdot N$ is increasing.
Note that $u=\|u\|N$, so $v\cdot u= (v\cdot \|u\|N)=\|u\|(v\cdot N)$, which is just a positive multiple of $v\cdot N$. Therefore ordering the points into $v_{i_1}, \ldots, v_{i_p}$ so that $v_{i_1}\cdot N, \ldots, v_{i_p}\cdot N$ is increasing is equivalent to ordering them so that $v_{i_1}\cdot u, \ldots, v_{i_p}\cdot u$ is increasing (but now the actual dot products aren't impact times, but that's okay, because "time" was artificially introduced by us).
Finally, if since $u=(x_0, y_0)$ and $v_i=(x_i,y_i)$, then $v_i\cdot u=x_0x_i+y_0y_i$, so these are the quantities we want to sort into increasing order.