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

return tooclose

def findspot(pointlist, added, d, gridsize, draw):

newlist = []

newadded =[]

for point in pointlist:

newlist.append(point)

for point in added:

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

newadded.append([px,py])

return newlist, newadded

class graph():

def __init__(this, d, gridsize, draw):

this.pointlist = [[400,400]]

this.added = [[400,400]]

this.d = d

this.gridsize = gridsize

this.draw = draw

def tree(this, limit):

newlist, newadded = findspot(this.pointlist,this.added,this.d, this.gridsize, this.draw)

if limit < 25:

this.pointlist = newlist

this.added = newadded

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

## No comments:

## Post a Comment