Geek asks and answers

How to set 2D scatter data using C ++ string

I worked with MATLAB, and for the question raised, I can use p = polyfit (x, y, 1) to estimate the best suitable line for the scattering data in the plate. I was wondering what resources I can use to implement a string fitting algorithm using C ++. I understand that there are many algorithms for this subject, and for me I expect the algorithm to be fast, and in the meantime it can get comparable polyfit function accuracy in MATLAB.

+5
source share
6 answers

I would suggest coding it from scratch. This is a very simple C ++ implementation. You can encode both interception and gradient to fit the least squares (the same method as polyfit), from your data directly from the formulas here

http://en.wikipedia.org/wiki/Simple_linear_regression#Fitting_the_regression_line

These are closed formula formulas that you can easily evaluate using cycles. If you used higher degrees, I would suggest a matrix library or more complex algorithms, but for a simple linear regression, as you described above, this is all you need. Matrices and routines of linear algebra would be redundant for such a problem (in my opinion).

+6
source

, , ..: http://faculty.cs.niu.edu/~hutchins/csci230/best-fit.htm. , ++ :

#include <vector>
#include <cmath>

struct Point {
  double _x, _y;
};
struct Line {
  double _slope, _yInt;
  double getYforX(double x) {
    return _slope*x + _yInt;
  }
  // Construct line from points
  bool fitPoints(const std::vector<Point> &pts) {
    int nPoints = pts.size();
    if( nPoints < 2 ) {
      // Fail: infinitely many lines passing through this single point
      return false;
    }
    double sumX=0, sumY=0, sumXY=0, sumX2=0;
    for(int i=0; i<nPoints; i++) {
      sumX += pts[i]._x;
      sumY += pts[i]._y;
      sumXY += pts[i]._x * pts[i]._y;
      sumX2 += pts[i]._x * pts[i]._x;
    }
    double xMean = sumX / nPoints;
    double yMean = sumY / nPoints;
    double denominator = sumX2 - sumX * xMean;
    // You can tune the eps (1e-7) below for your specific task
    if( std::fabs(denominator) < 1e-7 ) {
      // Fail: it seems a vertical line
      return false;
    }
    _slope = (sumXY - sumX * yMean) / denominator;
    _yInt = yMean - _slope * xMean;
    return true;
  }
};

, , , (http://en.wikipedia.org/wiki/Simple_linear_regression#Fitting_the_regression_line) , "" . ,

y = k*x + b

. , " " , ,

A*x + B*y + C = 0

. :

y = k*x + b <=>
y - k*x - b = 0 <=>
B=1, A=-k, C=-b

:

B=1, A=-_slope, C=-_yInt

"then" if , 0, // Fail: it seems a vertical line, :

x = xMean <=>
x - xMean = 0 <=>
A=1, B=0, C=-xMean

, , , . - : http://hotmath.com/hotmath_help/topics/line-of-best-fit.html

double denominator = sumX2 - 2 * sumX * xMean + nPoints * xMean * xMean;
...
_slope = (sumXY - sumY*xMean - sumX * yMean + nPoints * xMean * yMean) / denominator;

, nPoints*xMean == sumX nPoints*xMean*yMean == sumX * yMean == sumY * xMean.

+10

Ax + By + C = 0.

, ( B ) y = (-A/B) * x + (-C/B)

typedef double scalar_type;
typedef std::array< scalar_type, 2 > point_type;
typedef std::vector< point_type > cloud_type;

bool fit( scalar_type & A, scalar_type & B, scalar_type & C, cloud_type const& cloud )
{
    if( cloud.size() < 2 ){ return false; }

    scalar_type X=0, Y=0, XY=0, X2=0, Y2=0;

    for( auto const& point: cloud )
    { // Do all calculation symmetric regarding X and Y
        X  += point[0];
        Y  += point[1];
        XY += point[0] * point[1];
        X2 += point[0] * point[0];
        Y2 += point[1] * point[1];
    }

    X  /= cloud.size();
    Y  /= cloud.size();
    XY /= cloud.size();
    X2 /= cloud.size();
    Y2 /= cloud.size();

    A = - ( XY - X * Y ); //!< Common for both solution

    scalar_type Bx = X2 - X * X;
    scalar_type By = Y2 - Y * Y;

    if( fabs( Bx ) < fabs( By ) ) //!< Test verticality/horizontality
    { // Line is more Vertical.
        B = By;
        std::swap(A,B);
    }
    else
    {   // Line is more Horizontal.
        // Classical solution, when we expect more horizontal-like line
        B = Bx;
    }
    C = - ( A * X + B * Y );

    //Optional normalization:
    // scalar_type  D = sqrt( A*A + B*B );
    // A /= D;
    // B /= D;
    // C /= D;
    return true;
}
+3

, .

+1

-. . ( ) . , ​​ ( ). -. "y" . / . x y. , x ( ), , . . , , . . , -.

, , , , , " ", . , , . , . , , , : -).

+1

y=param[0]x+param[1], :

// loop over data:
{               
sum_x += x[i];
sum_y += y[i];
sum_xy += x[i] * y[i];
sum_x2 += x[i] * x[i];
}

// means
double mean_x = sum_x / ninliers;
double mean_y = sum_y / ninliers;

float varx = sum_x2 - sum_x * mean_x;
float cov = sum_xy - sum_x * mean_y;

// varx

param[0] = cov / varx;
param[1] = mean_y - param[0] * mean_x;

http://easycalculation.com/statistics/learn-regression.php ( , N, sz.). 3D-, - http://www.mymathforum.com/viewtopic.php?f=13&t=8793

: , . , . , . RANSAC. :

0

More articles:


All Articles