CODEWITHSUNDEEP
algorithmoctavebounding-box
maximus
maximus

Reputation: 4302

How to calculate angle of rotation of a rectangle, given its 4 points

I have a set of 2D points. I did eigenvectors estimation of its covariance. Made transformation to new basis and found the bounding box there. For simplicity giving code in octave below. Points are given as: points variable with shape of Nx2

mycov = cov(points);
[V, E] = eig(mycov);
new_basis_points = V*points';

Then in the code I estimate max and min values for each axis and make four points set:

points = [[minX, minY], 
          [minX, maxY],
          [maxX, minY],
          [maxX, maxY]];

Now I transform back to old basis:

old_basis_bounding_box = V'*points';

These calculations are correct, I get four corner points in old basis. But now I want to estimate the angle of rotation of the rectangle between its side and X axis.

The problem is, that the order of points in old_basis_bounding_box is not defined. So I'm not sure which two points to select to make angle estimation.

How should I proceed?

Upvotes: 2

Views: 2576

Answers (1)

snowynguyen
snowynguyen

Reputation: 316

Illustration

I believe the angle alpha (marked green in the image) is what you are looking for. Assuming the lowest point of the rectangle is O(0, 0), this angle can be easily calculated as cos-1(a/sqrt(a^2+b^2)), where B(a,b) is the point with lowest positive slope. As of D ≠ O (where D is the point with the lowest y-axis coordinate), just move the whole thing by the vector OD so that D = O.

Don't forget to separately handle the case when the rectangle already aligned to the axis, when you may get division by zero.

My pseudo-code:

    struct Point
    {
        double x, y, angle;
        Point (double x, double y): x(x), y(y) {}
    };

    bool SortByY (Point a, Point b)
    {
        return a.y < b.y;
    }

    bool SortByAngle (Point a, Point b)
    {
        return a.angle < b.angle;
    }

    double GetRotationAngle(vector<Point> points)
    {
        sort (points.begin(), points.end(), SortByY);

        // If there are 2 points lie on the same y-axis coordinates, simply return 0
        if  (points[0].y == points[1].y) return 0;

        Point D = points[0];

        for (int i=1; i<4; i++)
        {
            // Move the whole thing by vector OD
            double a = points[i].x -= D.x;
            double b = points[i].y -= D.y;

            // Keep in mind that in C++, the acos function returns value in radians, you may need to convert to degrees for your purposes.
            points[i].angle = acos(a / sqrt(a*a+b*b));
        }

        sort (points.begin()+1, points.end(), SortByAngle);
        return points[1].angle;
    }

Upvotes: 3

Related Questions