# Thread: And now for some geometry: ordering 4 points around a quadrangle

1. ## And now for some geometry: ordering 4 points around a quadrangle

Simply said: a user gives me 4 pairs of coordinates for 4 points that are the vertices of a quadrangle in any order. How can I identify the 4 corners (top left, top right, bottom left, bottom right)? I'll be dealing with only convex quadrangles and I have seen this.

2. Iced Almond Soy Ubuntu, No Foam
Join Date
Aug 2010
Location
Lancs, United Kingdom
Beans
1,109
Distro
Xubuntu 14.04 Trusty Tahr

## Re: And now for some geometry: ordering 4 points around a quadrangle

Doesn't this simple method work if you know that the quadrilateral is convex?

Sort points ascending by y value. 1st two are "bottom". 2nd two are "top". For the tops then the bottoms, use the x value to decide which is "left" and "right".

3. ## Re: And now for some geometry: ordering 4 points around a quadrangle

does labeling points make any sense? What is top-left in case of a square rotated 45deg?

asking to clarify: is the input an unordered list of points and the goal is to establish the order of vertices that will create a convex quadrilateral?

In a convex shape diagonals have to cross, so you need to find pairs that create crossing segments. Once you have them, alternate, eg A1->B1->A2->B2

4. ## Re: And now for some geometry: ordering 4 points around a quadrangle

Originally Posted by spjackson
Doesn't this simple method work if you know that the quadrilateral is convex?

Sort points ascending by y value. 1st two are "bottom". 2nd two are "top". For the tops then the bottoms, use the x value to decide which is "left" and "right".
No

5. ## Re: And now for some geometry: ordering 4 points around a quadrangle

Originally Posted by Vaphell
does labeling points make any sense? What is top-left in case of a square rotated 45deg?

asking to clarify: is the input an unordered list of points and the goal is to establish the order of vertices that will create a convex quadrilateral?

In a convex shape diagonals have to cross, so you need to find pairs that create crossing segments. Once you have them, alternate, eg A1->B1->A2->B2
That's a start, it will put the points in some perimeter order but that won't tell me which one is at top left, for instance, and if the top right is the one after the top left or the one before (ie I can't tell if this generates a clockwise or counter-clockwise perimeter). However, I think I can walk the list until I find a point where the next has a bigger X and the previous has a bigger Y, and if I don't find it, I can reverse the list I search again. Then I have the top left one.

For a full background: this is for a Gimp script. The user specifies 4 points by drawing a path, and the script covers the quadrangle using an existing rectangular image with a perspective transform. This transforms requires, in a specific order, the 4 corners of the quadrangle that correspond to the 4 corners in the image. The problem is that the user hasn't got much control over the order of the points in the path. If he is reasonably careful things could be OK, but in the general case they won't be, so I prefer having a good way to guess the right order (an output a message otherwise).
Last edited by ofnuts; January 15th, 2014 at 06:09 PM.

6. Iced Almond Soy Ubuntu, No Foam
Join Date
Aug 2010
Location
Lancs, United Kingdom
Beans
1,109
Distro
Xubuntu 14.04 Trusty Tahr

## Re: And now for some geometry: ordering 4 points around a quadrangle

Originally Posted by ofnuts
No

That is a valid counter example if you think that B is "top left". By what definition do you deduce that B is "top left"? Consider a "diamond" shape where A and D have the same x value, and B and C have the same y value. In that case, what labelling would be correct? (By which I mean for example A is at 1,1 B is at 0,0 C is at 2,0 and D is at 1,-1.)
Last edited by spjackson; January 15th, 2014 at 06:39 PM.

7. ## Re: And now for some geometry: ordering 4 points around a quadrangle

Originally Posted by spjackson
That is a valid counter example if you think that B is "top left". By what definition do you deduce that B is "top left"? Consider a "diamond" shape where A and D have the same x value, and B and C have the same y value. In that case, what labelling would be correct? (By which I mean for example A is at 1,1 B is at 0,0 C is at 2,0 and D is at 1,-1.)
I call B "top left" because I don't see any other point that could be labelled as "top left". B and D are more on the left than A and C, so their are the ones on the left, and B is above D so it is the top one. Of course we can decide that the is no top left vertex...

8. Tall Cafè Ubuntu
Join Date
Feb 2009
Beans
1,434

## Re: And now for some geometry: ordering 4 points around a quadrangle

Here's the algorithm I thought of:
0_ Using the knowledge that the polygon is convex, order the points so you can tell which ones are adjacent.
1_ Determine the point with the greatest y-value. Call it P. This is one of your upper corners.
2_ Draw lines from P to both its neigbors. Take the endpoint of the line that has the shallower angle (closer to horizontal), and call it Q.
3_ If P's x-value is less than Q's x-value, then P is your top left vertex and Q is top-right. If P's x is greater than Q's, exactly the opposite.
4_ The other points fall out from the ordering.

9. ## Re: And now for some geometry: ordering 4 points around a quadrangle

no matter how you slice it, it's ambiguous. With that algorithm you can have a top-left that has the lowest y. If you did the same algorithm but from the bottom you'd get something else (this point would be bottom-* by definition). You could also say by looking at the picture that the edge connecting the highest and the lowest point should be top-left to bottom-left
Square rotated 45deg obviously has 2 equally valid solutions (top vertex=top-left or top-right) thanks to symmetry.
Last edited by Vaphell; January 16th, 2014 at 05:23 AM.

10. Tall Cafè Ubuntu
Join Date
Feb 2009
Beans
1,434

## Re: And now for some geometry: ordering 4 points around a quadrangle

Yes, that's true. But if I were trying to stretch a rectangular photo into a canvas that shape, that's what I'd call "top left". I was shooting for a solution that would do the right thing most of the time, not a mathematically rigorous one.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•