rkm0959's blog

Generating Random Convex Polygons?
By rkm0959, history, 8 years ago, In English

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

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

generate random set of points and calculate its convex hull

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

Randomly choose interior angles and edge lengths while checking if it'll give you a convex polygon in the end?

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

    You need too much iterations to obtain a convex polygon by this method, I suppose.

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

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.

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

    Does the sum of vector being zero force the polygon to be convex?

    Thanks for the help!

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

      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.

      → Reply