Page 1 of 2 12 LastLast
Results 1 to 10 of 14

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

  1. #1
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,877
    Distro
    Kubuntu 12.10 Quantal Quetzal

    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.
    Warning: unless noted otherwise, code in my posts should be understood as "coding suggestions", and its use may require more neurones than the two necessary for Ctrl-C/Ctrl-V.

  2. #2
    Join Date
    Aug 2010
    Location
    Lancs, United Kingdom
    Beans
    1,093
    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. #3
    Join Date
    Jul 2007
    Location
    Poland
    Beans
    4,346
    Distro
    Ubuntu 10.04 Lucid Lynx

    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
    if your question is answered, mark the thread as [SOLVED]. Thx.
    To post code or command output, use [code] tags.
    Check your bash script here // BashFAQ // BashPitfalls

  4. #4
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,877
    Distro
    Kubuntu 12.10 Quantal Quetzal

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

    Quote Originally Posted by spjackson View Post
    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

    Warning: unless noted otherwise, code in my posts should be understood as "coding suggestions", and its use may require more neurones than the two necessary for Ctrl-C/Ctrl-V.

  5. #5
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,877
    Distro
    Kubuntu 12.10 Quantal Quetzal

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

    Quote Originally Posted by Vaphell View Post
    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.
    Warning: unless noted otherwise, code in my posts should be understood as "coding suggestions", and its use may require more neurones than the two necessary for Ctrl-C/Ctrl-V.

  6. #6
    Join Date
    Aug 2010
    Location
    Lancs, United Kingdom
    Beans
    1,093
    Distro
    Xubuntu 14.04 Trusty Tahr

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

    Quote Originally Posted by ofnuts View Post
    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. #7
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,877
    Distro
    Kubuntu 12.10 Quantal Quetzal

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

    Quote Originally Posted by spjackson View Post
    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...
    Warning: unless noted otherwise, code in my posts should be understood as "coding suggestions", and its use may require more neurones than the two necessary for Ctrl-C/Ctrl-V.

  8. #8

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

    What about this?

    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. #9
    Join Date
    Jul 2007
    Location
    Poland
    Beans
    4,346
    Distro
    Ubuntu 10.04 Lucid Lynx

    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.
    if your question is answered, mark the thread as [SOLVED]. Thx.
    To post code or command output, use [code] tags.
    Check your bash script here // BashFAQ // BashPitfalls

  10. #10

    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.

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

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