| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
I want to generate a random convex polygon, with (hopefully) integer points (lattice points) as vertices.
I am aware of methods using circles/ellipses and using random angles to create a random convex polygon, but I want a method which gives a much more "random" polygon. Is this possible in a not-so-difficult way?
Thanks in advance. :D
generate random set of points and calculate its convex hull
As I remember it's size will be O(log n)
there's paper about it https://arxiv.org/pdf/1111.5340.pdf
Randomly choose interior angles and edge lengths while checking if it'll give you a convex polygon in the end?
You need too much iterations to obtain a convex polygon by this method, I suppose.
You can generate vectors of its edges, then sort them by angle and connect them to build a polygon. You need to make sure that the sum of vectors is zero, it's not too hard to do this. But in this case if you generate n vectors with coordinates up to C by absolute value, you can obtain points with coordinates up to C·n, so you need to choose parameters carefully.
Does the sum of vector being zero force the polygon to be convex?
Thanks for the help!
It forces the polyline to be a polygon.
If you append vectors one by one in the order of their polar angle, connecting the next vector to the end of the current sequence, all angles between consecutive sides will be no more than π. Here we also use that the sum of vectors is zero, you can try to draw pictures for better understanding.