Here is a generalized Monte Carlo simulation in python for the average line segment length in any regular polygon with one square unit of area:
Code:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import time
def isInPoly(r,theta,cr,n):
theta = theta%(2*np.pi/n) #Rotates point to first "sector" of the polygon for simplicity
x = r*np.cos(theta)
y = r*np.sin(theta)
x1 = cr #x coordinate of vertex at theta = 0
y1 = 0.0 #y coordinate of vertex at theta = 0
x2 = cr*np.cos(2*np.pi/n) #x coordinate of vertex at theta = 2pi/n
y2 = cr*np.sin(2*np.pi/n) #y coordinate of vertex at theta = 2pi/n
if y < ((y2 - y1)/(x2 - x1))*(x - x1) + y1: #Check using 2-point line formula
return True
else:
return False
def genPolyPt(n, cr):
'''Return tuple of random rectangular coordinate within an n-sided regular polygon centered
at (0,0) with circumradius = cr and a vertex at (cr,0).'''
r = cr*(np.random.random()**0.5) #Square root correction ensures even probability distribution over area
theta = 2*np.pi*np.random.random()
x = r*np.cos(theta)
y = r*np.sin(theta)
if r < cr*np.cos(np.pi/n): #If r < apothem of polygon then point is in the polygon's incircle
return x,y
if isInPoly(r,theta,cr,n): #Checks if point is between polygon and incircle
return x,y
else: #If point not in polygon
return genPolyPt(n, cr)
t = time.time()
n = 4 #Number of sides of polygon
area = 1.0
trials = 10**7 #Number of random samples
cr = (area/(n*np.sin(2*np.pi/n)/2))**0.5 #Solves for circumradius that yields polygon with specified area
total = 0.0
#fig = plt.figure()
#ax1 = fig.gca()
#xlist = []
#ylist = []
for i in range(trials):
x1,y1 = genPolyPt(n,cr)
x2,y2 = genPolyPt(n,cr)
#xlist.append(x1)
#ylist.append(y1)
total += ((x2-x1)**2 + (y2-y1)**2)**0.5
#plt.xlim(-.85, .85)
#plt.ylim(-.85, .85)
#ax1.set_aspect('equal')
#ax1.scatter(xlist,ylist,s=5)
print(total/trials)
print(time.time()-t)
The following are average lengths based on ten million samples:
Triangle: 0.554367342879
Square: 0.521395852676
Pentagon: 0.514797872593
Hexagon: 0.512588030594
Heptagon: 0.51176618103
Octagon: 0.511213933924
Nonagon: 0.511120940654
Decagon: 0.511039068646
25-gon: 0.510860752385
100-gon: 0.510794294963
1000-gon: 0.510750983962
1000000-gon: 0.510902061585
Can anyone think of another general way of generating a random point in an n-gon that is more efficient than mine for small values of n (without sacrificing significantly for larger values of n, of course)? When n=3, my program is discarding almost 60% of the points it generates.