## Friday, November 28, 2014

### Branching poisson disk algorithm

My program outputs a distribution like this:
Every dot is at least a distance of 10 pixels from any other.
The way it works is to start at the middle, and branch out in 3 evenly spaced directions at a random angle from the center dot, then from those 3 points branch in a similar way generating more points and continue in that fashion for a certain number of iterations, above is 25 generations. I think this picture helps explain it a lot.
The speed is fairly quick, generating these graphs in python took only about 1.5 seconds for around 1300 points, I think it could be speeded up considerally using parallel processing for example on a gpu with a faster language.
**Python source code**
import math
import random
import Image, ImageDraw
def check(d, pointlist, point, gridsize):
tooclose = False
if point[0] < 10 or point[0] > gridsize[0]-10 or point[1] < 10 or point[1] > gridsize[1]-10:
return True
for p in range(0, len(pointlist)):
if ((point[0]-pointlist[p][0])**2.0 + (point[1]-pointlist[p][1])**2.0)**.5 < d-1:
return True
def findspot(pointlist, added, d, gridsize, draw):
newlist = []
for point in pointlist:
newlist.append(point)
tx = point[0]
ty = point[1]
theta = random.random()*2*3.14159
for i in range(0, 3):
px = tx + d*math.cos(theta+i*(2*3.14159)/3)
py = ty + d*math.sin(theta+i*(2*3.14159)/3)
if check(d, newlist, [px,py], gridsize) == False:
newlist.append([px,py])
class graph():
def __init__(this, d, gridsize, draw):
this.pointlist = [[400,400]]
this.d = d
this.gridsize = gridsize
this.draw = draw
def tree(this, limit):
if limit < 25:
this.pointlist = newlist
this.tree(limit+1)
def main():
gridsize = [790,790]
d = 10.0
point = [400,400]
plot = Image.new("RGB", [800,800])
draw = ImageDraw.Draw(plot)
G = graph(d, gridsize, draw)
G.tree(0)
for point in G.pointlist:
for i in range(-1, 2):
for j in range(-1, 2):
plot.putpixel((int(point[0]+i), int(point[1])+j), (255,255,255))
plot.save("plotdot.png")
main()