{
"metadata": {
"name": "",
"signature": "sha256:d4792a400510dfc48c2b7c1eac5f9de6248a3ab08c95f97d6e1244b48f6154bf"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"PolyFill"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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.\n",
"\n",
"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."
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Libraries"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from pandas import *\n",
"import random, math"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 211
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Overall Configuration Parameters"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"config = {\n",
" 'random_seed' : 17,\n",
" 'xExt': [-0.1,1.1] ,\n",
" 'yExt': [-0.1,1.1] ,\n",
" 'densityX' : 40 ,\n",
" 'densityY' : 20 ,\n",
" 'prob_0' : 0.1 ,\n",
" 'prob_3' : 0.075 ,\n",
" 'num_mod_steps' : 10 ,\n",
" 'mod_step_ratio' : 0.1\n",
"}"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 212
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Utility Methods"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Geometry methods"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def dotproduct(v1, v2):\n",
" return sum((a*b) for a, b in zip(v1, v2))\n",
"\n",
"def vectorLength(v):\n",
" return math.sqrt(dotproduct(v, v))\n",
"\n",
"def angleBtwnVectors(v1, v2):\n",
" dot = dotproduct(v1, v2)\n",
" det = v1[0]*v2[1] - v1[1]*v2[0]\n",
" r = math.atan2(det, dot)\n",
" return r * 180.0 / math.pi\n",
"\n",
"def angleViolation(vectorList,maxAllowed):\n",
" violation = False\n",
" angleList = []\n",
" for i in range(0,len(vectorList)):\n",
" angleList.append( angleBtwnVectors([1,0],vectorList[i]) )\n",
" angleList.sort()\n",
" angleList.append(angleList[0] + 360.0)\n",
" for i in range(1,len(angleList)):\n",
" if abs(angleList[i] - angleList[i-1]) > maxAllowed:\n",
" violation = True\n",
" return violation"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 213
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Methods to add vertices and edges to table"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def addVertex(vertices):\n",
" r = len(vertices['x'])\n",
" vertices.ix[r,'x'] = 0\n",
" vertices.ix[r,'y'] = 0\n",
" return r\n",
"\n",
"def locateVertex(p,r,vertices):\n",
" vertices.ix[r,'x'] = p[0]\n",
" vertices.ix[r,'y'] = p[1]\n",
"\n",
"def addEdge(r1,r2,vertices):\n",
" for c in ['a1','a2','a3','a4','a5']:\n",
" if not vertices.ix[r1,c] > -1:\n",
" vertices.ix[r1,c] = r2\n",
" break\n",
" for c in ['a1','a2','a3','a4','a5']:\n",
" if not vertices.ix[r2,c] > -1:\n",
" vertices.ix[r2,c] = r1\n",
" break"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 214
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Graph visualization"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"pylab.rcParams['figure.figsize'] = (12.0, 12.0)\n",
"\n",
"def makeedges(nodes):\n",
" edges = DataFrame({'x1':[],'y1':[],'x2':[],'y2':[]})\n",
" r = 0\n",
" for i in range(len(nodes)):\n",
" for a in ['a1','a2','a3','a4','a5','a6']:\n",
" if nodes.ix[i,a] > -1 :\n",
" edges.ix[r,'x1'] = nodes.ix[i,'x']\n",
" edges.ix[r,'y1'] = nodes.ix[i,'y']\n",
" edges.ix[r,'x2'] = nodes.ix[int(nodes.ix[i,a]),'x']\n",
" edges.ix[r,'y2'] = nodes.ix[int(nodes.ix[i,a]),'y']\n",
" r += 1\n",
" return edges\n",
"\n",
"def plotGraph(vertices,dots=True):\n",
" edges = makeedges(vertices)\n",
" if dots:\n",
" p = vertices.plot(kind='scatter',x='x',y='y',\n",
" xlim=[config['xExt'][0],config['xExt'][1]],\n",
" ylim=[config['yExt'][0],config['yExt'][1]],\n",
" color='grey')\n",
" else:\n",
" p = vertices.plot(kind='scatter',x='x',y='y',\n",
" xlim=[config['xExt'][0],config['xExt'][1]],\n",
" ylim=[config['yExt'][0],config['yExt'][1]],\n",
" color='white')\n",
" for i in range(len(edges)):\n",
" p.plot([edges.ix[i,'x1'],edges.ix[i,'x2']],[edges.ix[i,'y1'],edges.ix[i,'y2']],color='black')\n",
" return p"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 215
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Export to json for d3 visualization"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def graphToJSON(vertices,fileName):\n",
" verticesOut = DataFrame(vertices)\n",
" adjacencies = []\n",
" for i in range(len(verticesOut['x'])):\n",
" ve = []\n",
" for j in range(1,7):\n",
" if verticesOut.ix[i,'a'+str(j)] > -1:\n",
" ve.append( int(verticesOut.ix[i,'a'+str(j)]) )\n",
" adjacencies.append(ve)\n",
" verticesOut['adjacencies'] = adjacencies\n",
" verticesOut.drop('a1', axis=1, inplace=True)\n",
" verticesOut.drop('a2', axis=1, inplace=True)\n",
" verticesOut.drop('a3', axis=1, inplace=True)\n",
" verticesOut.drop('a4', axis=1, inplace=True)\n",
" verticesOut.drop('a5', axis=1, inplace=True)\n",
" verticesOut.drop('a6', axis=1, inplace=True)\n",
" verticesOut['vertex'] = verticesOut.index\n",
" json = verticesOut.to_json(orient='records',path_or_buf=fileName)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 216
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Main Script"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"Make graph"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"random.seed(config['random_seed'])\n",
"vertices = DataFrame({'x':[],'y':[],\n",
" 'a1':[],'a2':[],'a3':[],'a4':[],'a5':[],'a6':[] })\n",
"y = 0\n",
"densityX = config['densityX']\n",
"densityY = config['densityY']\n",
"nextLine = range(densityX)\n",
"for i in range(len(nextLine)):\n",
" r = addVertex(vertices)\n",
"for line in range(densityY):\n",
" currentLine = nextLine\n",
" nextLine = []\n",
" numPointsInLine = len(currentLine)\n",
" previousNone = False\n",
" for i in range(numPointsInLine):\n",
" p = [i/float(numPointsInLine-1),y]\n",
" locateVertex(p,currentLine[i],vertices)\n",
" if i > 0:\n",
" addEdge(currentLine[i-1],currentLine[i],vertices)\n",
" if line < densityY-1:\n",
" # push either 0, 1 or 3 new vertices\n",
" rnd = random.uniform(0,1)\n",
" if rnd < config['prob_0'] and (not previousNone) and line > 0 and i > 0 and i < (numPointsInLine - 1):\n",
" # 0 vertices\n",
" previousNone = True\n",
" elif rnd < (config['prob_3'] + config['prob_0']) and line < densityY-2:\n",
" # 3 vertices\n",
" nv = []\n",
" for j in range(3):\n",
" if j == 0 and previousNone:\n",
" nv.append(len(vertices['x']) - 1)\n",
" else:\n",
" nv.append(addVertex(vertices))\n",
" nextLine.append(nv[j])\n",
" addEdge(currentLine[i],nv[0],vertices)\n",
" addEdge(currentLine[i],nv[2],vertices)\n",
" previousNone = False\n",
" else:\n",
" # 1 vertex\n",
" if previousNone:\n",
" nv = len(vertices['x']) - 1\n",
" else:\n",
" nv = addVertex(vertices)\n",
" nextLine.append(nv)\n",
" addEdge(currentLine[i],nv,vertices)\n",
" previousNone = False \n",
" y += 1.0 / float(densityY-1)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 217
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"vertices.head(10)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"\n",
"
\n",
" \n",
" \n",
" | \n",
" a1 | \n",
" a2 | \n",
" a3 | \n",
" a4 | \n",
" a5 | \n",
" a6 | \n",
" x | \n",
" y | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" 40 | \n",
" 1 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.000000 | \n",
" 0 | \n",
"
\n",
" \n",
" | 1 | \n",
" 0 | \n",
" 41 | \n",
" 2 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.025641 | \n",
" 0 | \n",
"
\n",
" \n",
" | 2 | \n",
" 1 | \n",
" 42 | \n",
" 3 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.051282 | \n",
" 0 | \n",
"
\n",
" \n",
" | 3 | \n",
" 2 | \n",
" 43 | \n",
" 4 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.076923 | \n",
" 0 | \n",
"
\n",
" \n",
" | 4 | \n",
" 3 | \n",
" 44 | \n",
" 5 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.102564 | \n",
" 0 | \n",
"
\n",
" \n",
" | 5 | \n",
" 4 | \n",
" 45 | \n",
" 6 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.128205 | \n",
" 0 | \n",
"
\n",
" \n",
" | 6 | \n",
" 5 | \n",
" 46 | \n",
" 7 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.153846 | \n",
" 0 | \n",
"
\n",
" \n",
" | 7 | \n",
" 6 | \n",
" 47 | \n",
" 49 | \n",
" 8 | \n",
" NaN | \n",
" NaN | \n",
" 0.179487 | \n",
" 0 | \n",
"
\n",
" \n",
" | 8 | \n",
" 7 | \n",
" 50 | \n",
" 52 | \n",
" 9 | \n",
" NaN | \n",
" NaN | \n",
" 0.205128 | \n",
" 0 | \n",
"
\n",
" \n",
" | 9 | \n",
" 8 | \n",
" 53 | \n",
" 10 | \n",
" NaN | \n",
" NaN | \n",
" NaN | \n",
" 0.230769 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"