Reorder four points of a rectangle to the correct order

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

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();
        }
    }
}

Tags:

Java

Sorting

Recent Posts