Блог пользователя rkm0959

Автор rkm0959, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

generate random set of points and calculate its convex hull

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Thanks for the help!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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.