[SOLVED] Generating a "random" simple polygon

[Ovidios]

The title basically says it all. I just want to generate a table containing n points that make up a simple (non self-intersecting) polygon
Thanks in advance,
- Ovidios

[ivan]

I recommend starting out with something very simple like, creating a 'regular' polygon:

Code: Select all

--- Constructs a regular polygon
--- Description:
-- Counter-clockwise where the first vertex is: 1*r, 0
--- Parameters:
-- @param n Number of sides
-- @param r Circumradius
-- @return Regular polygon
function poly.regular(n, r, out)
  out = out or {}
  local i = 1
  for j = 0, n do
    local a = j/n*pi2
    out[i] = cos(a)*r 
    out[i + 1] = sin(a)*r
    i = i + 2
  end
  return out
end

--- Constructs a regular polygon
-- @param n Number of sides
-- @param s Side
-- @return Regular polygon
function poly.regular2(n, s, out)
  local r = s/(2*sin(pi/n))
  return poly.regular(n, r, out)
end

Take a look at the first function.
It generates a regular polygon by creating vertices in a circle pattern.
All you have to do is randomize the circumradius for each vertex and there, you have a random, non-intersecting polygon.

Code: Select all

  for j = 0, n do
    local a = j/n*pi2
    local r2 = math.random()*0.5 + 0.5 -- random number in range [0.5-1]
    out[i] = cos(a)*r*r2
    out[i + 1] = sin(a)*r*r2
    i = i + 2
  end

Just make sure the random value 'r2' is greater than 0.
The results look like a deformed 'star' especially if you have a lot of vertices.
Sure, there are better/faster polygon generation algorithms out there
depending on the input you are starting out with,
but it gets quite complicated.

more code: https://bitbucket.org/itraykov/utils/src/ => math/poly.lua or math.poly2.lua

[davisdude]

I don't know if this code is efficiently written or anything like that, but you can check out how I did it. It uses something called "The two peasants" (or something like that) algorithm. I tried to keep the code kind of commented...