I'm not sure how to approach this problem. I'm not sure how complex a task it is. My aim is to have an algorithm that generates any polygon. My only requirement is that the polygon is not complex (i.e. sides do not intersect). I'm using Matlab for doing the maths but anything abstract is welcome.
Any aid/direction?
EDIT:
I was thinking more of code that could generate any polygon even things like this:
I took @MitchWheat and @templatetypedef's idea of sampling points on a circle and took it a bit farther.
In my application I need to be able to control how weird the polygons are, ie start with regular polygons and as I crank up the parameters they get increasingly chaotic. The basic idea is as stated by @templatetypedef; walk around the circle taking a random angular step each time, and at each step put a point at a random radius. In equations I'm generating the angular steps as
where theta_i and r_i give the angle and radius of each point relative to the centre, U(min, max) pulls a random number from a uniform distribution, and N(mu, sigma) pulls a random number from a Gaussian distribution, and clip(x, min, max) thresholds a value into a range. This gives us two really nice parameters to control how wild the polygons are - epsilon which I'll call irregularity controls whether or not the points are uniformly space angularly around the circle, and sigma which I'll call spikeyness which controls how much the points can vary from the circle of radius r_ave. If you set both of these to 0 then you get perfectly regular polygons, if you crank them up then the polygons get crazier.
I whipped this up quickly in python and got stuff like this:
Here's the full python code:
import math, random
def generatePolygon( ctrX, ctrY, aveRadius, irregularity, spikeyness, numVerts ) :
'''Start with the centre of the polygon at ctrX, ctrY,
then creates the polygon by sampling points on a circle around the centre.
Randon noise is added by varying the angular spacing between sequential points,
and by varying the radial distance of each point from the centre.
Params:
ctrX, ctrY - coordinates of the "centre" of the polygon
aveRadius - in px, the average radius of this polygon, this roughly controls how large the polygon is, really only useful for order of magnitude.
irregularity - [0,1] indicating how much variance there is in the angular spacing of vertices. [0,1] will map to [0, 2pi/numberOfVerts]
spikeyness - [0,1] indicating how much variance there is in each vertex from the circle of radius aveRadius. [0,1] will map to [0, aveRadius]
numVerts - self-explanatory
Returns a list of vertices, in CCW order.
'''
irregularity = clip( irregularity, 0,1 ) * 2*math.pi / numVerts
spikeyness = clip( spikeyness, 0,1 ) * aveRadius
# generate n angle steps
angleSteps = []
lower = (2*math.pi / numVerts) - irregularity
upper = (2*math.pi / numVerts) + irregularity
sum = 0
for i in range(numVerts) :
tmp = random.uniform(lower, upper)
angleSteps.append( tmp )
sum = sum + tmp
# normalize the steps so that point 0 and point n+1 are the same
k = sum / (2*math.pi)
for i in range(numVerts) :
angleSteps[i] = angleSteps[i] / k
# now generate the points
points = []
angle = random.uniform(0, 2*math.pi)
for i in range(numVerts) :
r_i = clip( random.gauss(aveRadius, spikeyness), 0, 2*aveRadius )
x = ctrX + r_i*math.cos(angle)
y = ctrY + r_i*math.sin(angle)
points.append( (int(x),int(y)) )
angle = angle + angleSteps[i]
return points
def clip(x, min, max) :
if( min > max ) : return x
elif( x < min ) : return min
elif( x > max ) : return max
else : return x
@MateuszKonieczny here is code to create an image of a polygon from a list of vertices.
verts = generatePolygon( ctrX=250, ctrY=250, aveRadius=100, irregularity=0.35, spikeyness=0.2, numVerts=16 )
black = (0,0,0)
white=(255,255,255)
im = Image.new('RGB', (500, 500), white)
imPxAccess = im.load()
draw = ImageDraw.Draw(im)
tupVerts = map(tuple,verts)
# either use .polygon(), if you want to fill the area with a solid colour
draw.polygon( tupVerts, outline=black,fill=white )
# or .line() if you want to control the line thickness, or use both methods together!
draw.line( tupVerts+[tupVerts[0]], width=2, fill=black )
im.show()
# now you can save the image (im), or do whatever else you want with it.