How to Make a Quadrangle using 4 Random Points in XY Cordinate

First of all I must say that many of us already know this trick probably. But I encountered this problem once during a big project, I was a bit confused finding the solution. It seemed to be simple problem, but somehow I couldn’t find the answer that how I can make a general quadrangle out of four random points in XY Cartesian coordinate system. I mean to say in which order I should take the points to join them together to make a quadrangle. I searched in the internet hoping that someone else might have solved the problem earlier, but I found nothing about it. Then I thought no one might fall into such problem as everyone might already know the solution. However, I found myself a big nuts, after thinking about the problem a bit rationally. I found a simpler algorithm so I am gladly sharing the algorithm with you.

Second of all, what I am going to discuss in next few minutes, will be all in Imaging coordinate system which is a bit different from general XY Cartesian coordinate system. So there will be no negative coordinates, all points are positive and the origin is (1,1). And the origin is the most Top-Left point of the image.

Suppose, we take four random points in image coordinate system: (11,16), (10,7), (4,11) and (19,9) in Fig.1.

32x32

So the Point matrix is:
11 16
10 7
4 11
19 9

Step 1: First sort the matrix using the first column only i.e with respect to X coordinate in ascending order. So now the Matrix would be like this:
4 11
10 7
11 16
19 9

Step 2: Now sort the first two rows using the Y coordinate in ascending order and sort the next two rows in descending order. So now the Matrix would be like this:
10 7
4 11
11 16
19 9

Step 3: Your quadrangle points are sorted now, Name the points back to back: I, II, III, IV as in Fig.2.
Connect I with II:
Connect II with III:
Connect III with IV:
Connect IV with I:

32x321

Very simple, isn’t it? Simple but useful trick. Take more examples to make the idea clear. Now I am giving the MATLAB code for this algorithm. You can contact me if you need further assistance.

MATLAB CODE

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Program Name : Quadrangle Sort
% Author : Arindam Bose
% Version : 1.0
% Description : This program sorts 4 points in quadrangle order
% Copyright : © Arindam Bose, All rights reserved.
% License : Open Source, Freeware
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [rectMatrix] = rectanglesort(points)
rectMatrix = sortrows(points);
if rectMatrix(1,2) > rectMatrix(2,2)
temp = rectMatrix(1,:);
rectMatrix(1,:) = rectMatrix(2,:);
rectMatrix(2,:) = temp;
end
if rectMatrix(3,2) < rectMatrix(4,2)
temp = rectMatrix(3,:);
rectMatrix(3,:) = rectMatrix(4,:);
rectMatrix(4,:) = temp;
end
end

Hope this helps a lot. Thanks… More Tricks are coming soon…

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.