| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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.
https://cp-algorithms.com/geometry/convex-hull.html
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)
Simple and useful.
I actually used comparator based on this idea, didn't split the points
Is the polygon guaranteed to be convex?
It's not stated anywhere, so I assume not. It will also be a very obvious / known question in that case.
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
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.
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)
Yeah, I meant any order.
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