gistfile1.txt

import random

graph = [
	(0,0),
	(20,0),
	(20,20),
	(0,20),
]

#add some random points
random.seed(39176)
for i in range(5):
	new = (random.randint(0,20), random.randint(0,20))
	if new not in graph:
		graph.append(new)

#preprocess
vert_id = 1
for i in range(len(graph)):
	graph[i] = (vert_id, graph[i][0], graph[i][1])
	vert_id += 1


#generate edges
raw_edges = []
for i in range(len(graph)):
	for j in range(i+1, len(graph)):
		#for each vert and each other vert
		v1 = graph[i]
		v2 = graph[j]

		#get the edge props
		at = (v1[1],v1[2])
		r = (v2[1]-v1[1], v2[2]-v1[2])
		l = (r[0]*r[0] + r[1]*r[1])**0.5
		u = (r[0]/l, r[1]/l)

		#write
		raw_edges.append((v1, v2, at, r, l, u))

#now, sort the edges on length
raw_edges.sort(key = lambda x: x[4])

#do write 
out_file = open('test.dot', 'w')

def writegraph():
	#write verts
	out_file.write('graph main {\n')
	out_file.write('\tgraph [size="30,30"];\n')
	out_file.write('\tgraph [bb="0,0,200,200"]')
	for v in graph:
		out_file.write('\t%s [pos="%f, %f!"];\n' % (v[0], v[1], v[2]))
	for e in edges:
		out_file.write('\t%d -- %d [];\n' % (e[0][0], e[1][0]))
	out_file.write('}\n')

def formatedge(e):
	return "<%d->%d, at(%d,%d), dir(%d,%d)>" % \
		(e[0][0], e[1][0], e[2][0], e[2][1], e[3][0], e[3][1])

#now, add edges from the raw edges
edges = []
for e in raw_edges:
	for other in edges:
		#see if |e| intersects with the existing |other|
		#calculate r x s
		rx = e[5][0]
		ry = e[5][1]
		sx = other[5][0]
		sy = other[5][1]
		rxs = rx*sy - ry*sx

		#rxs = 0 => no intersection
		if rxs == 0:
			continue

		#calculate q-p
		qpx = other[2][0] - e[2][0]
		qpy = other[2][1] - e[2][1]

		#calculate t and u
		t = (qpx*sy - qpy*sx) / rxs
		u = (qpx*ry - qpy*rx) / rxs

		#see if both u and t are in [0,1]
		if (0.001 < u < (e[4]-0.001)) and (0.001 < t < (other[4]-0.001)):
			#lines are intersecting, bail out
			#print("%s, %s" % (formatedge(e), formatedge(other)))
			#print(t, u, e[4]+0.001, other[4]+0.001)
			#print(e[3][0], e[3][1])
			#print(rx, ry)
			name = "%d%d%d%d" % (e[0][0], e[1][0], other[0][0], e[1][0])
			#graph.append((name, e[2][0] + t*rx, e[2][1] + t*ry))
			break
	else:
		#no intersection, add the edge
		edges.append(e)

	
	writegraph()

writegraph()