#!/usr/bin/python

try:
  import psyco
  psyco.profile()
except:
  pass

# Parameters

resolution = 1024
node_size = 0.02 #0.04

# Program

import Image, ImageDraw, random

size = (resolution*4*14/10, resolution*4)

def line(points):
  radius = 4
  for x in range(-radius,radius+1):
    for y in range(-radius,radius+1):
      if x*x + y*y <= radius**2:
        new_points = list(points)
	for i in range(0,len(new_points),2):
	  new_points[i] += x
	  new_points[i+1] += y
	draw.line(new_points,0)

def d2(i,j):
  return (points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2

print "Generate random node positions"

node_rad = int(size[1] * node_size)
n_points = size[0]*size[1]/(node_rad**2) / 16
points = [ (random.randrange(size[0]-node_rad*2)+node_rad,
            random.randrange(size[1]-node_rad*2)+node_rad) 
           for i in range(n_points) ]

print "Remove nodes too close to other nodes"

#points = [ point for point in points \
#           if min(point[0],size[0]-point[0])+min(point[1],size[1]-point[1]) > \
#	      size[1] / 4 ]

bad = { }
for i in range(len(points)):
  for j in range(i+1,len(points)):
    if d2(i,j) < node_rad**2:
      bad[i] = 1
      break
points = [ points[i] for i in range(len(points)) if not bad.get(i) ]

print "Find links"

links = [ ]

for i in xrange(len(points)):
  for j in xrange(i+1,len(points)):
    for k in xrange(len(points)):
        if k != i and k != j and \
           d2(k,i) < d2(i,j) and d2(k,j) < d2(i,j):
          break
    else:
        links.append((i,j))

print len(links), "links"

print "Render"

image = Image.new('L',size,255)
draw = ImageDraw.Draw(image)

good_points = { }
for link in links:
  good_points[link[0]] = 1
  good_points[link[1]] = 1
  line(points[link[0]]+points[link[1]])

points = [ points[i] for i in range(len(points)) if good_points.get(i) ]
for point in points:
  draw.ellipse((
    point[0]-node_rad/3,
    point[1]-node_rad/3,
    point[0]+node_rad/3,
    point[1]+node_rad/3
  ), 0)

print "There are", len(points), "nodes"

image = image.resize((size[0]/4,size[1]/4),Image.BILINEAR)
image.save('goboard-navinet.png')