Suppose I have a set of 2D parallel line segments on an XY plane defined by their end points, and the set is out of order, and I need to sort them such that they are ordered correctly in either direction of their shared normal vector.
What might be the best way to do this?
Edit: A picture may be helpful in explaining my intentions. The output of the solution should be either of two mappings shown in the image, which it is, is not important. The line segments are not guaranteed to all share a perpendicular line passing through all of them, hence why I would like to solve using a normal vector.
I can't post the image directly as I do not have enough reputation, so here is the link: https://i.stack.imgur.com/uzUsm.jpg
If the endpoints of a line segment are $\mathbf p$ and $\mathbf q$, then the distance of the line through these points from the origin is the length of their projection onto the normal $\mathbf n$ to the line. For a fixed unit normal this is simply the absolute value of the dot product of $\mathbf p$ or $\mathbf q$ with $\mathbf n$. Retain the sign so that you have a signed distance that also tells you which side of the origin you’re on relative to the direction of the normal and use this scalar projection as the sort key.
You can easily find this common unit normal either by taking the cross product of the homogeneous coordinates of a pair of endpoints and then normalizing the first two components, or by rotating the difference $\mathbf q-\mathbf p$ 90°, which is just a matter of a swap of coordinates and a sign change. As long as you use the same normal for all of the dot products, you don’t even have to normalize it.