3

I have a list of points in 3 space that are all collinear. I need to sort the list of points so I may process them in order. I don't care or we don't have a choice which end of the line we start from since the line directions vary and there is no sense of beginning or end--they are lines! However, I will have many lists of collinear points that will be parallel to each other and I would like the sort method to yield sorting them in the same direction.

An early attempt, which is flawed, was to pick one of the points in the list and compute distance (magnitude) to all other points and then use this distance to sort. However, that might only work if the chosen point was on one end or the other. Thanks

Bernard
  • 175,478
Timbo
  • 33
  • "There are many lists"... does this mean the lists are already given as separate collections of points, or does the algorithm need to make the separate collections of collinear points from a big list of points not all collinear? – coffeemath Aug 15 '19 at 23:38
  • 1
    The question didn't say anything about making new lists. Whether I have one list or 300, I'm asking for a way to sort...not create, not separate...just sort. thx. – Timbo Aug 16 '19 at 03:09

2 Answers2

3

You could pick one point, then calculate the point that is furthest away from it. That furthest point is an "end point" and you could sort on distance from it.

  • OK, but this wouldn't ensure that all parallel lines are sorted from the same direction. – Jens Aug 15 '19 at 23:53
  • Yeah, I have to confess that I wasn't clear about that part of the story, just improving on the solution that was suggested. I suppose that once you have sorted each line like this, you could calculate the "direction" from your start point of different lines. Then if you find that two are the opposite of each other, you could reverse one of the lists to make them "parallel". –  Aug 15 '19 at 23:58
  • That should do it. – Jens Aug 16 '19 at 00:00
  • I used this approach but as I noted it's flawed. distance or magnitude alone does not allow me to distinguish direction and therefore line them up correctly. If I could figure out how to know the 'sign' or direction then I could know 'forward' or 'backword' thx – Timbo Aug 16 '19 at 03:13
1

I think you could just sort based on the $x$ coordinate of the points. However, if you are worried that the entire line will be parallel to the $y$-$z$ plane and have the same $x$ value then there is a better general solution.

Pick a vector $v$ which trends in a direction which is not perpendicular to the lines. A good choice would be $v=v_1-v_2$ if $v_1$ and $v_2$ are the coordinates of two points on the line. Then sort points $v_i$ according to the value of $v_i\cdot v,$ the dot product of the point with your chosen trend vector. This dot product essentially measures "how much" a given point points in the direction of the trend vector $v$.

subrosar
  • 4,614
  • Something a lot like this was going to be my answer but you posted two minutes quicker than I did. :-) – David K Aug 16 '19 at 00:15
  • Sounds interesting as long as the dot product yields a sign. I'll look it up. thx – Timbo Aug 16 '19 at 03:15
  • I found this answer easy to follow and gave me the help I needed to sort all the lists. Thanks – Timbo Aug 16 '19 at 04:30