Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to link four points to a quadrangle?

Subject: How to link four points to a quadrangle?

From: zhang

Date: 6 Aug, 2010 23:50:09

Message: 1 of 3

Hi guys

How to link four points to a quadrangle? I mean how to identify the order of these four points.

Thanks

Zhong

Subject: How to link four points to a quadrangle?

From: Roger Stafford

Date: 7 Aug, 2010 06:03:06

Message: 2 of 3

"zhang " <xiaoc10@gmail.com> wrote in message <i3i73h$rb3$1@fred.mathworks.com>...
> Hi guys
> How to link four points to a quadrangle? I mean how to identify the order of these four points.
> Thanks
> Zhong
- - - - - - - - - - -
  As it stands your question is not meaningful. One can order the four vertices of a (2D) quadrangle in any order one desires. If you want the resulting quadrangle to be convex, that is a different matter. However, if any of the four points lies within the triangle formed by the other three points, then it will be impossible to make a convex quadrangle from the points, no matter what order is used.

  Let X and Y be 4 by 1 column vectors with the x and y coordinates of the four points. Then do the following to determine, if possible, how to permute their order so as to constitute a convex quadrangle.

 a = det([X(1:3),Y(1:3),ones(3,1)]) > 0;
 b = det([X(2:4),Y(2:4),ones(3,1)]) > 0;
 c = det([X([4,1:2]),Y([4,1:2]),ones(3,1)]) > 0;
 d = det([X([3:4,1]),Y([3:4,1]),ones(3,1)]) > 0;
 s = a+b+c+d;
 if mod(s,2)==1
  fprintf('The quadrangle cannot be made convex.\n')
  p = 1:4; % Leave order as is - convexity is impossible if s is odd
 elseif s==4
  p = 1:4; % The present order is correct
 elseif s==0
  p = 4:-1:1; % Reverse the order
 elseif s==2
  if a & b
   p = [4 2 3 1]; % Interchange 1 & 4
  elseif c & d
   p = [1,3,2,4]; % Interchange 2 & 3
  elseif a & c
   p = [1,2,4,3]; % Interchange 3 & 4
  elseif b & d
   p = [2,1,3,4]; % Interchange 1 & 2
  end
 end
 X = X(p); Y = Y(p);

If convexity is possible, the points in X and Y will now be vertices in counterclockwise ordering around a convex quadrangle.

  This code looks rather awkward but it is the best I could come up with in a short time.

Roger Stafford

Subject: How to link four points to a quadrangle?

From: Roger Stafford

Date: 7 Aug, 2010 06:15:07

Message: 3 of 3

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i3isuq$9u9$1@fred.mathworks.com>...
> "zhang " <xiaoc10@gmail.com> wrote in message <i3i73h$rb3$1@fred.mathworks.com>...
> > Hi guys
> > How to link four points to a quadrangle? I mean how to identify the order of these four points.
> > Thanks
> > Zhong
> - - - - - - - - - - -
> As it stands your question is not meaningful. One can order the four vertices of a (2D) quadrangle in any order one desires. If you want the resulting quadrangle to be convex, that is a different matter. However, if any of the four points lies within the triangle formed by the other three points, then it will be impossible to make a convex quadrangle from the points, no matter what order is used.
>
> Let X and Y be 4 by 1 column vectors with the x and y coordinates of the four points. Then do the following to determine, if possible, how to permute their order so as to constitute a convex quadrangle.
>
> a = det([X(1:3),Y(1:3),ones(3,1)]) > 0;
> b = det([X(2:4),Y(2:4),ones(3,1)]) > 0;
> c = det([X([4,1:2]),Y([4,1:2]),ones(3,1)]) > 0;
> d = det([X([3:4,1]),Y([3:4,1]),ones(3,1)]) > 0;
> s = a+b+c+d;
> if mod(s,2)==1
> fprintf('The quadrangle cannot be made convex.\n')
> p = 1:4; % Leave order as is - convexity is impossible if s is odd
> elseif s==4
> p = 1:4; % The present order is correct
> elseif s==0
> p = 4:-1:1; % Reverse the order
> elseif s==2
> if a & b
> p = [4 2 3 1]; % Interchange 1 & 4
> elseif c & d
> p = [1,3,2,4]; % Interchange 2 & 3
> elseif a & c
> p = [1,2,4,3]; % Interchange 3 & 4
> elseif b & d
> p = [2,1,3,4]; % Interchange 1 & 2
> end
> end
> X = X(p); Y = Y(p);
>
> If convexity is possible, the points in X and Y will now be vertices in counterclockwise ordering around a convex quadrangle.
>
> This code looks rather awkward but it is the best I could come up with in a short time.
>
> Roger Stafford
- - - - - - -
  It occurs to me (rather belatedly) that instead of the above, you could much more easily use the 'convhull' function which would presumably put the vertices in convex order if possible. Otherwise you would get a triangle with one of the four points left out.

Roger Stafford

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us