This script is used to fill a 2-dimensional space with contiguous 4-sided polygons, where the graph (vertices and edges of the polygons) contains vertices with semi-randomly assigned numbers of edges, between 2 and 5. The algorithm running time is linear relative to the number of vertices.
For the author, it is a methodological stepping stone to a window shading device design generator, but may also be of interest for other applications.
from pandas import *
import random, math
config = {
'random_seed' : 17,
'xExt': [-0.1,1.1] ,
'yExt': [-0.1,1.1] ,
'densityX' : 40 ,
'densityY' : 20 ,
'prob_0' : 0.1 ,
'prob_3' : 0.075 ,
'num_mod_steps' : 10 ,
'mod_step_ratio' : 0.1
}
def dotproduct(v1, v2):
return sum((a*b) for a, b in zip(v1, v2))
def vectorLength(v):
return math.sqrt(dotproduct(v, v))
def angleBtwnVectors(v1, v2):
dot = dotproduct(v1, v2)
det = v1[0]*v2[1] - v1[1]*v2[0]
r = math.atan2(det, dot)
return r * 180.0 / math.pi
def angleViolation(vectorList,maxAllowed):
violation = False
angleList = []
for i in range(0,len(vectorList)):
angleList.append( angleBtwnVectors([1,0],vectorList[i]) )
angleList.sort()
angleList.append(angleList[0] + 360.0)
for i in range(1,len(angleList)):
if abs(angleList[i] - angleList[i-1]) > maxAllowed:
violation = True
return violation
def addVertex(vertices):
r = len(vertices['x'])
vertices.ix[r,'x'] = 0
vertices.ix[r,'y'] = 0
return r
def locateVertex(p,r,vertices):
vertices.ix[r,'x'] = p[0]
vertices.ix[r,'y'] = p[1]
def addEdge(r1,r2,vertices):
for c in ['a1','a2','a3','a4','a5']:
if not vertices.ix[r1,c] > -1:
vertices.ix[r1,c] = r2
break
for c in ['a1','a2','a3','a4','a5']:
if not vertices.ix[r2,c] > -1:
vertices.ix[r2,c] = r1
break
pylab.rcParams['figure.figsize'] = (12.0, 12.0)
def makeedges(nodes):
edges = DataFrame({'x1':[],'y1':[],'x2':[],'y2':[]})
r = 0
for i in range(len(nodes)):
for a in ['a1','a2','a3','a4','a5','a6']:
if nodes.ix[i,a] > -1 :
edges.ix[r,'x1'] = nodes.ix[i,'x']
edges.ix[r,'y1'] = nodes.ix[i,'y']
edges.ix[r,'x2'] = nodes.ix[int(nodes.ix[i,a]),'x']
edges.ix[r,'y2'] = nodes.ix[int(nodes.ix[i,a]),'y']
r += 1
return edges
def plotGraph(vertices,dots=True):
edges = makeedges(vertices)
if dots:
p = vertices.plot(kind='scatter',x='x',y='y',
xlim=[config['xExt'][0],config['xExt'][1]],
ylim=[config['yExt'][0],config['yExt'][1]],
color='grey')
else:
p = vertices.plot(kind='scatter',x='x',y='y',
xlim=[config['xExt'][0],config['xExt'][1]],
ylim=[config['yExt'][0],config['yExt'][1]],
color='white')
for i in range(len(edges)):
p.plot([edges.ix[i,'x1'],edges.ix[i,'x2']],[edges.ix[i,'y1'],edges.ix[i,'y2']],color='black')
return p
def graphToJSON(vertices,fileName):
verticesOut = DataFrame(vertices)
adjacencies = []
for i in range(len(verticesOut['x'])):
ve = []
for j in range(1,7):
if verticesOut.ix[i,'a'+str(j)] > -1:
ve.append( int(verticesOut.ix[i,'a'+str(j)]) )
adjacencies.append(ve)
verticesOut['adjacencies'] = adjacencies
verticesOut.drop('a1', axis=1, inplace=True)
verticesOut.drop('a2', axis=1, inplace=True)
verticesOut.drop('a3', axis=1, inplace=True)
verticesOut.drop('a4', axis=1, inplace=True)
verticesOut.drop('a5', axis=1, inplace=True)
verticesOut.drop('a6', axis=1, inplace=True)
verticesOut['vertex'] = verticesOut.index
json = verticesOut.to_json(orient='records',path_or_buf=fileName)
random.seed(config['random_seed'])
vertices = DataFrame({'x':[],'y':[],
'a1':[],'a2':[],'a3':[],'a4':[],'a5':[],'a6':[] })
y = 0
densityX = config['densityX']
densityY = config['densityY']
nextLine = range(densityX)
for i in range(len(nextLine)):
r = addVertex(vertices)
for line in range(densityY):
currentLine = nextLine
nextLine = []
numPointsInLine = len(currentLine)
previousNone = False
for i in range(numPointsInLine):
p = [i/float(numPointsInLine-1),y]
locateVertex(p,currentLine[i],vertices)
if i > 0:
addEdge(currentLine[i-1],currentLine[i],vertices)
if line < densityY-1:
# push either 0, 1 or 3 new vertices
rnd = random.uniform(0,1)
if rnd < config['prob_0'] and (not previousNone) and line > 0 and i > 0 and i < (numPointsInLine - 1):
# 0 vertices
previousNone = True
elif rnd < (config['prob_3'] + config['prob_0']) and line < densityY-2:
# 3 vertices
nv = []
for j in range(3):
if j == 0 and previousNone:
nv.append(len(vertices['x']) - 1)
else:
nv.append(addVertex(vertices))
nextLine.append(nv[j])
addEdge(currentLine[i],nv[0],vertices)
addEdge(currentLine[i],nv[2],vertices)
previousNone = False
else:
# 1 vertex
if previousNone:
nv = len(vertices['x']) - 1
else:
nv = addVertex(vertices)
nextLine.append(nv)
addEdge(currentLine[i],nv,vertices)
previousNone = False
y += 1.0 / float(densityY-1)
vertices.head(10)
a1 | a2 | a3 | a4 | a5 | a6 | x | y | |
---|---|---|---|---|---|---|---|---|
0 | 40 | 1 | NaN | NaN | NaN | NaN | 0.000000 | 0 |
1 | 0 | 41 | 2 | NaN | NaN | NaN | 0.025641 | 0 |
2 | 1 | 42 | 3 | NaN | NaN | NaN | 0.051282 | 0 |
3 | 2 | 43 | 4 | NaN | NaN | NaN | 0.076923 | 0 |
4 | 3 | 44 | 5 | NaN | NaN | NaN | 0.102564 | 0 |
5 | 4 | 45 | 6 | NaN | NaN | NaN | 0.128205 | 0 |
6 | 5 | 46 | 7 | NaN | NaN | NaN | 0.153846 | 0 |
7 | 6 | 47 | 49 | 8 | NaN | NaN | 0.179487 | 0 |
8 | 7 | 50 | 52 | 9 | NaN | NaN | 0.205128 | 0 |
9 | 8 | 53 | 10 | NaN | NaN | NaN | 0.230769 | 0 |
p = plotGraph(vertices)
graphToJSON(vertices,'vertices0.json')
def angleViolationGrid(i,vertices):
violation = False
vt = [i]
for j in range(1,7):
if vertices.ix[i,'a'+str(j)] > -1:
vt.append( int(vertices.ix[i,'a'+str(j)]) )
for v in vt:
vectorList = []
edgeList = []
for j in range(1,7):
if vertices.ix[int(v),'a'+str(j)] > -1:
e = vertices.ix[int(v),'a'+str(j)]
edgeList.append(e)
vectorList.append( [ vertices.ix[int(e),'x'] - vertices.ix[int(v),'x'] ,
vertices.ix[int(e),'y'] - vertices.ix[int(v),'y'] ] )
if angleViolation(vectorList,180.0):
violation = True
return violation
for k in range(config['num_mod_steps']):
for i in range(len(vertices['x'])):
if not (vertices.ix[i,'x'] == 0 or vertices.ix[i,'x'] == 1 or vertices.ix[i,'y'] == 0 or vertices.ix[i,'y'] == 1):
longestEdge = -1
longestEdgeLength = 0
for j in range(1,7):
if vertices.ix[i,'a'+str(j)] > -1:
e = vertices.ix[i,'a'+str(j)]
length = vectorLength( [ vertices.ix[int(e),'x'] - vertices.ix[i,'x'],
vertices.ix[int(e),'y'] - vertices.ix[i,'y'] ] )
if length > longestEdgeLength:
longestEdge = e
longestEdgeLength = length
saveX = vertices.ix[i,'x']
saveY = vertices.ix[i,'y']
deltaX = config['mod_step_ratio'] * ( vertices.ix[int(longestEdge),'x'] - vertices.ix[i,'x'] )
deltaY = config['mod_step_ratio'] * ( vertices.ix[int(longestEdge),'y'] - vertices.ix[i,'y'] )
vertices.ix[i,'x'] = vertices.ix[i,'x'] + deltaX
vertices.ix[i,'y'] = vertices.ix[i,'y'] + deltaY
if angleViolationGrid(i,vertices):
vertices.ix[i,'x'] = saveX
vertices.ix[i,'y'] = saveY
graphToJSON(vertices,'vertices' + str(k+1) + '.json')
p = plotGraph(vertices)