Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### rkm0959's blog

By rkm0959, history, 3 years ago, ,

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?

• +8

 » 3 years ago, # |   0 generate random set of points and calculate its convex hull
•  » » 3 years ago, # ^ |   +21 As I remember it's size will be O(log n)
•  » » » 3 years ago, # ^ |   +8 there's paper about it https://arxiv.org/pdf/1111.5340.pdf
 » 3 years ago, # |   0 Randomly choose interior angles and edge lengths while checking if it'll give you a convex polygon in the end?
•  » » 3 years ago, # ^ |   +10 You need too much iterations to obtain a convex polygon by this method, I suppose.
 » 3 years ago, # |   +40 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.
•  » » 3 years ago, # ^ |   0 Does the sum of vector being zero force the polygon to be convex?Thanks for the help!
•  » » » 3 years ago, # ^ |   +21 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.