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]

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

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)
    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)

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)):
    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)
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)