snorkel's blog

How to order the points of polygon?
By snorkel, history, 2 years ago, In English

I have polygon and its vertices represented with randomly shuffled 2d points, how can I find the correct order?

In correct order I mean order so that segment between P[i] and P[(i + 1) % n] is a side of polygon.

Or if this is hard, how to solve it for 4 sides?

I'm looking for an efficient solutions. Many thanks.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cp-algorithms.com/geometry/convex-hull.html

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You can find the upper hull of the points, add it to the list, then add the points sorted by their x coordinates (lower points first)

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Simple and useful.

    I actually used comparator based on this idea, didn't split the points

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the polygon guaranteed to be convex?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not stated anywhere, so I assume not. It will also be a very obvious / known question in that case.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why are people downvoting this? I answered the question in another comment and the author of the blog seemed fine with it. The convex case would just be finding a convex hull, and there are many known algorithms for that

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you are given a set of points in $$$R^2$$$, then there isn't a unique way of making a non-convex polygon out of them. Take for example the points $$$(1,0),(0,1),(-1,0),(0,-1),(0,0)$$$. There are 4 natural ways you could make a non-convex polygon out of them.

        Only when you assume the points should form a convex polygon will the answer be unique.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          of course it wouldn't be unique, but we can't make assumptions to make our life simpler. and also a convex polygon of n vertices can have 2n orders :/ (rotation, flip)

          That said, I understand why there's the confusion, but my answer seemed to satisfy VaibhavAgarwala, so I guess he meant any order (correct me if I'm wrong)

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wouldn't it be the right thing to do,to simply sort them in clockwise direction, using the formula of cos between 2 vectors,however,you have to fing the center of that polygon to form the vectors

→ Reply