# PolyFill¶

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.

### Libraries¶

In [211]:
from pandas import *
import random, math


### Overall Configuration Parameters¶

In [212]:
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
}


### Utility Methods¶

#### Geometry methods¶

In [213]:
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


#### Methods to add vertices and edges to table¶

In [214]:
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]

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


#### Graph visualization¶

In [215]:
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


#### Export to json for d3 visualization¶

In [216]:
def graphToJSON(vertices,fileName):
verticesOut = DataFrame(vertices)
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)]) )
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)


### Main Script¶

#### Make graph¶

In [217]:
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)):
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:
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:
nextLine.append(nv[j])
previousNone = False
else:
# 1 vertex
if previousNone:
nv = len(vertices['x']) - 1
else:
nextLine.append(nv)
previousNone = False
y += 1.0 / float(densityY-1)

In [218]:
vertices.head(10)

Out[218]:
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
In [219]:
p = plotGraph(vertices)

In [220]:
graphToJSON(vertices,'vertices0.json')


#### Modify vertex locations¶

In [221]:
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

In [222]:
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')

In [223]:
p = plotGraph(vertices)