Line Passing Through Given Points

I am trying t开发者_开发知识库o 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?

---

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

---

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.

---

Obviously the line will pass through averaged point (x_average,y_average).

For direction you may use the following algorithm (derived directly from minimizing average square distance between line and points):

dx[i]=x[i]-x_average;
dy[i]=y[i]-y_average;

a=sum(dx[i]^2-dy[i]^2);
b=sum(2*dx[i]*dy[i]);

direction=atan2(b,a);

Usual linear regression will not work here, because it assumes that variables are not symmetric - one depends on other, so if you will swap x and y, you will have another solution.

---

The hough transform might be also a good option:

http://en.wikipedia.org/wiki/Hough_transform

---

You might try searching for "total least squares", or "least orthogonal distance" but when I tried that I saw nothing immediately applicable.

Anyway suppose you have points x[],y[], and the line is represented by a*x+b*y+c = 0, where hypot(a,b) = 1. The least orthogonal distance line is the one that minimises Sum{ (a*x[i]+b*y[i]+c)^2}. Some algebra shows that:

c is -(a*X+b*Y) where X is the mean of the x's and Y the mean of the y's.

(a,b) is the eigenvector of C corresponding to it's smaller eigenvalue, where C is the covariance matrix of the x's and y's