Line Passing Through Given Points

Question

I am trying to find the angle of the outer line of the object in the green region of the image as shown in the image above…

For that, I have scanned the green region and get the points (dark blue points as shown in the image)...

As you can see, the points are not making straight line so I can’t find angle easily.

So I think I have to find a middle way and that is to find the line so that the distance between each point and line remain as minimum as possible.

So how can I find the line so that each point exposes minimum distance to it……?

Is there any algorithm for this or is there any good way other than this?

Answer 1

The obvious route would be to do a least-squares linear regression through the points.

Answer 2

The standard least squares regression formulae for x on y or y on x assume there is no error in one coordinate and minimize the deviations in the coordinate from the line.

However, it is perfectly possible to set up a least squares calculation such that the value minimized is the sum of squares of the perpendicular distances of the points from the lines. I'm not sure whether I can locate the notebooks where I did the mathematics - it was over twenty years ago - but I did find the code I wrote at the time to implement the algorithm.

With:

• n = ∑ 1
• sx = ∑ x
• sx2 = ∑ x²
• sy = ∑ y
• sy2 = ∑ y²
• sxy = ∑ x·y

You can calculate the variances of x and y and the covariance:

• v_x = sx2 - ((sx * sx) / n)
• v_y = sy2 - ((sy * sy) / n)
• v_xy = sxy - ((sx * sy) / n)

Now, if the covariance is 0, then there is no semblance of a line. Otherwise, the slope and intercept can be found from:

• slope = quad((vx - vy) / vxy, vxy)
• intcpt = (sy - slope * sx) / n

Where quad() is a function that calculates the root of quadratic equation x² + b·x - 1 with the same sign as c. In C, that would be:

double quad(double b, double c)
{
    double b1;
    double q;

    b1 = sqrt(b * b + 4.0);
    if (c < 0.0)
        q = -(b1 + b) / 2;
    else
        q = (b1 - b) / 2;
    return (q);
}

From there, you can find the angle of your line easily enough.