Reorder four points of a rectangle to the correct order

Question

The aspect-ratio=height/width is always >1 (for most cases even >2), so it should be clear/precise how I'd like to rotate.

---

I have a RotatedRect object in OpenCV / Java.
I can get an Array of it with 4 Objects of Type Point and Point defines x/y-values.

Now I'd like to sort those 4 Points so that the top-left Point is the first element of the Array and then clockwise, so that the top-bottom point is the fourth element.

I'm assuming that the Rectangles aren't rotated much (just some small angles), e.g.

I've indicated in the example which point I'd refer to as top left (TL).

How to do it?

You don't need to tell me specifically for OpenCV etc., just assume you'd have two arrays

int[] x = new int[4];
int[] y = new int[4];

Whereas the n-th Point has the coordinates (x[n-1], y[n-1]). I can then do it for OpenCV specifically myself.

Answer 1

Answer

There is an extremely easy solution if you know that:

1. -45 < roundedRect.angle < 45
2. roundedRect.size.height > roundedRect.size.width

If that is true, then the points, in clockwise order, will ALWAYS be in this order:

pts[0], pts[3], pts[2], pts[1]

As an aside, if it doesn't harm your program too much, the points are delivered in counterclockwise order, starting with the top left... then you wouldn't have to do any reordering / sorting.

Other cases:

• height > width && 135 < roundedRect.angle < 225
  
  • The clockwise order starting from the top left is 2,3,0,1
  • The counterclockwise order from top left is 2,1,0,3.
• width > height && -135 < roundedRect.angle < -45
  • The clockwise order starting from the top left is 3,2,1,0
  • The counterclockwise order from top left is 3,0,1,2
• width > height && 45 < roundedRect.angle < 135
  • The clockwise order starting from the top left is 1,0,3,2
  • The counterclockwise order from top left is 1,2,3,0

The remaining cases would all imply that the rectangle is bigger from left to right than it is from top to bottom, which cannot happen in your scenario. Also, if the angle is outside these ranges, you can add or subtract 360 successively to get an angle in one of these ranges.

---

Explanation

(tl;dr)

We know this from how OpenCV calculates the values of those points. You can figure this out with a little experimentation. Here's a little program I wrote that demonstrates it:

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

import org.opencv.core.Point;
import org.opencv.core.RotatedRect;
import org.opencv.core.Size;

public class TestFrame extends JFrame {
    public static void main(String... args) {
        final TestFrame frame = new TestFrame();
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                frame.setVisible(true);
            }
        });
    }

    private RectComponent rect;

    public TestFrame() {
        JPanel containerPane = new JPanel(new BorderLayout());
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        rect = new RectComponent();
        containerPane.add(rect);
        setContentPane(containerPane);
        setSize(400,400);
        new Timer(100, rect).start();
    }

    public class RectComponent extends JComponent implements ActionListener {
        private RotatedRect rect = new RotatedRect(new Point(0,0), new Size(1, 3), 0);

        private final Point[] pts = new Point[4];

        @Override
        protected void paintComponent(Graphics g) {
            rect.points(pts);
            printPoints();
            Dimension size = getSize();
            drawRectLine(g, pts[0], pts[1], size);
            drawRectLine(g, pts[1], pts[2], size);
            drawRectLine(g, pts[2], pts[3], size);
            drawRectLine(g, pts[0], pts[3], size);
        }

        private void printPoints() {
            System.out.format("A: %d, TL: %s, TR: %s, BR: %s, BL%s%n",
                    (int) (rect.angle + (rect.angle < 0 ? -1e-6 : 1e-6)), // Stupid doubles, stupid rounding error
                    pointToString(pts[0]),
                    pointToString(pts[3]),
                    pointToString(pts[2]),
                    pointToString(pts[1]));
        }

        private String pointToString(Point p) {
            return String.format("{%.2f,%.2f}",p.x, p.y);
        }

        private void drawRectLine(Graphics g, Point left, Point right, Dimension size) {
            g.drawLine(scale(left.x, size.width), scale(left.y, size.height),
                    scale(right.x, size.width), scale(right.y, size.height));
        }


        private int scale(double value, int coord) {
            return (int) (value * coord) / 4 + coord / 2;
        }


        @Override
        public void actionPerformed(ActionEvent e) {
            rect.angle += 1;
            if(rect.angle > 44) rect.angle = -44;
            repaint();
        }
    }
}

Answer 2

EDIT: If you are free to assume that the rectangle has not been rotated by much, you can directly go ahead and find the top-left point by calculating the distance from the origin using the formula length = ((y1-y2)^2 + (x1-x2)^2)^(0.5) above with origin being (0,0). The point with the smallest distance will be the top left. And then you can proceed using the steps I have given below.

If you cannot assume that, there is another way of proceeding more elegantly once you have identified the top left point of the rectangle (and hence the first three steps remain the same). Once you have identified the top left:

1. Find out the distance from the top left point to the other three points using the Pythagorean formula, length = ((y1-y2)^2 + (x1-x2)^2)^(0.5)
2. You now have three lengths corresponding to the length of each vertex from the top-left point.

3. The position of the vertices can be easily found as (going in clockwise order):

   shortest distance = top right point 
   longest distance = bottom right point 
   middle distance = bottom left point
   

You do not need to use if conditions.

NOTE: This holds as long as the condition that the height is always greater than the width is maintained.

Answer 3

Search for the 2 points with the highest y-values, one of these is always the TL in your definition (width < height and small angles(not higher then 45°!).

Sort your array in descending order for your y-values and get the element with the 2nd heighest y-value.

If this point has the lowest x-value it defines your right picture (1). Else the point with the highest value is your TL and defines your left picture (2).

Now you get the clockwise order where the TL is your first element.

In case (1): Change the position of the last 2 elemnts of your sorted array In case (2): Change the position of the first 2 elemnts.

This is true because of your definition but I can't explain it in a proper mathematically way.

Answer 4

I just tried out one approach. I'm not sure whether it's "simpler" or in any other way "better" than yours, but I'll post it here as a suggestion:

You can compute the center of the rectangle. Then you can move the rectangle, so that its center is at the origin. Then you can compute the angle that each point has to the x-axis, using the Math.atan2 method. The neat thing here is: It returns the angle in the range -PI ... +PI, which exactly matches your desired ordering: The upper left point will have the "most negative" angle, and the lower left point will have the "most positive".

This description is just for illustration. Some of these steps (particularly "moving" the rectangle) do not have to be done explicitly.

However: In this example, you can set the corner points via mouse clicks. Each point will be labeled with its index and the angle, as described above. When the fourth point is set, then the points will be reordered accordingly, and the resulting indices/angles will be shown.

As far as I can see, the results seem to be what you intended to compute.

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;


public class RectanglePointReorderingTest
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().add(new RectanglePointReorderingPanel());
        f.setSize(800, 800);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    static Point2D computeCenter(List<Point2D> points)
    {
        double x = 0;
        double y = 0;
        for (Point2D p : points)
        {
            x += p.getX();
            y += p.getY();
        }
        x /= points.size();
        y /= points.size();
        return new Point2D.Double(x, y);
    }

    static double computeAngle(Point2D center, Point2D point)
    {
        double dx = point.getX() - center.getX();
        double dy = point.getY() - center.getY();
        double angleRad = Math.atan2(dy, dx);
        return angleRad;
    }

    static Comparator<Point2D> createComparator(Point2D center)
    {
        final Point2D finalCenter = 
            new Point2D.Double(center.getX(), center.getY());
        return new Comparator<Point2D>()
        {
            @Override
            public int compare(Point2D p0, Point2D p1)
            {
                double angle0 = computeAngle(finalCenter, p0);
                double angle1 = computeAngle(finalCenter, p1);
                return Double.compare(angle0, angle1);
            }
        };
    }    

    static void sortPoints(List<Point2D> points)
    {
        Collections.sort(points, createComparator(computeCenter(points)));
    }

}


class RectanglePointReorderingPanel extends JPanel implements MouseListener
{
    private List<Point2D> points = new ArrayList<Point2D>();

    public RectanglePointReorderingPanel()
    {
        addMouseListener(this);
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;

        g.setColor(Color.BLACK);
        if (points.size() < 4)
        {
            g.drawString("Click to create points", 20, 20);
        }
        else
        {
            g.drawString("Sorted points. Click again to clear.", 20, 20);
        }
        for (int i=0; i<points.size(); i++)
        {
            Point2D point = points.get(i);
            double x = point.getX();
            double y = point.getY();
            g.setColor(Color.RED);
            g.fill(new Ellipse2D.Double(x-5,y-5,10,10));

            g.setColor(Color.BLACK);

            double angleRad = 
                RectanglePointReorderingTest.computeAngle(
                    RectanglePointReorderingTest.computeCenter(points), point);
            String angleString = String.valueOf((int)Math.toDegrees(angleRad));
            g.drawString(String.valueOf(i)+" ("+angleString+")", (int)x+5, (int)y+5);


        }
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
        if (points.size() == 4)
        {
            points.clear();
            repaint();
        }
        else
        {
            points.add(e.getPoint());
            if (points.size() == 4)
            {
                RectanglePointReorderingTest.sortPoints(points);
            }
            repaint();
        }
    }


    @Override
    public void mouseEntered(MouseEvent e) {}

    @Override
    public void mouseExited(MouseEvent e) { }

    @Override
    public void mousePressed(MouseEvent e) { }

    @Override
    public void mouseReleased(MouseEvent e) { }


}

Answer 5

Because you are specifically asking for the order of the points from the RotatedRect data structure, that order is predictable and never changes (unless you update the library and the developers somehow needed to change that code -> very unlikely).

The order I got is quite odd and is the following:

point[0] - bottom left
point[1] - top left
point[2] - top right
point[3] - bottom right

You can see in OpenCV source code how that list of points from the RotatedRect is created, based on its center and angle:

public void points(Point pt[])
    {
        double _angle = angle * Math.PI / 180.0;
        double b = (double) Math.cos(_angle) * 0.5f;
        double a = (double) Math.sin(_angle) * 0.5f;

        pt[0] = new Point(
                center.x - a * size.height - b * size.width,
                center.y + b * size.height - a * size.width);

        pt[1] = new Point(
                center.x + a * size.height - b * size.width,
                center.y - b * size.height - a * size.width);

        pt[2] = new Point(
                2 * center.x - pt[0].x,
                2 * center.y - pt[0].y);

        pt[3] = new Point(
                2 * center.x - pt[1].x,
                2 * center.y - pt[1].y);
    }

EDIT (after comments):

If you realize that the corner order depends from the angle. It is easier to get the order based on the Pythagorean formula like it was said before by Sunil.

Depending which sign the variables a and b will have, the order will be different. Those signs depend from the cos() and sin() results which in turn depend from the angle. So you have 4 combinations of signs (+a, +b), (-a ,-b), (+a, -b), (-a, +b). These will give, if my theory stands, the 4 different point orders.

You can get the top-left corner by getting all points distance to (0,0). You will either get one minimum or 2 (equal) minimum distances. If you get 2 minimums, you chose one as the top-left rectangle corner: the one with smaller x coordinate is what makes more sense in my opinion and according to your drawing. The same process can be used for the other rectangle corners.

// Distance (x1, y1) to (x2, y2) = abs( sqrt( (x2-x1)^2 + (y2-y1)^2 ) )
// Note:This is a quite literal translation of the formula, there are more efficient ways.
public static final double pointsDist(Point pt1, Point pt2){        
   return  Math.abs( Math.sqrt( Math.pow((double) (pt2.x - pt1.x), 2) + Math.pow((double) (pt2.y - pt1.y), 2) ) );          
}