Search code examples
geometryregression

Order of points along a best fit line

I have a list of points (x,y) I need to be able to determine the order of points along a best fit (green) line. Points on line

AS shown in the picture I want them to be in the order 1,2,3 even though the x-coordinate is in the order x3,x1,x2 (I know the y-coordinate looks like the order I want but that is just this example)

If I have a line aX + bY + c=0, is there a way of finding a point normal to the line that passes through point(X1,Y1) ?

Looked at regression algorithms but they just seem to give me the line.

Looking at the picture I think I should be able to calculate each of the blue lines, that are normal to the green line and pass through the appropriate point.

Then solve for the points where the blue lines intersect the green line.

Then calculate the distance along the green line from a specific point of each of those green/blue intersections.

Is there a shortcut? If I am only dealing with <100 points, should I just rotate them about the point on the green line where y=0 and use the new x-value as the sequence?

Solution

  • Define some base point S at the line, and get it's direction vector D.

    Then for every point P[i] calculate parameter of orthogonal projection onto the line using dot (scalar) product

    t(i) = (P[i] - S).dot.D

    and sort points by this parameter

    Full expression for projection point coordinates is more complex, but I removed parts that don't influence on point order.

    P.S. You can get base point S=(0, -C/B) and direction vector D=(-C/A, C/B) when A,B coefficients are non-zero