import sys, pygame

pygame.init()
screen = pygame.display.set_mode((640, 480))

def same_sign(a, b):
	return ((a * b) >= 0)

def intersect(l1, l2):
	x1 = l1[0][0]
	y1 = l1[0][1]
	x2 = l1[1][0]
	y2 = l1[1][1]
	x3 = l2[0][0]
	y3 = l2[0][1]
	x4 = l2[1][0]
	y4 = l2[1][1]
	# Compute a1, b1, c1, where line joining points 1 and 2
	# is "a1 x + b1 y + c1 = 0".
	a1 = y2 - y1
	b1 = x1 - x2
	c1 = (x2 * y1) - (x1 * y2)
	
	# Compute r3 and r4.
	r3 = ((a1 * x3) + (b1 * y3) + c1)
	r4 = ((a1 * x4) + (b1 * y4) + c1)
	
	# Check signs of r3 and r4. If both point 3 and point 4 lie on
	# same side of line 1, the line segments do not intersect.
	if (r3 != 0) and (r4 != 0) and same_sign(r3, r4):
		return "DONT_INTERSECT"
	
	# Compute a2, b2, c2
	a2 = y4 - y3
	b2 = x3 - x4
	c2 = (x4 * y3) - (x3 * y4)
	
	# Compute r1 and r2
	r1 = (a2 * x1) + (b2 * y1) + c2
	r2 = (a2 * x2) + (b2 * y2) + c2
	
	# Check signs of r1 and r2. If both point 1 and point 2 lie
	# on same side of second line segment, the line segments do
	# not intersect.
	if (r1 != 0) and (r2 != 0) and same_sign(r1, r2):
		return "DONT_INTERSECT"
	
	# Line segments intersect: compute intersection point.
	denom = (a1 * b2) - (a2 * b1)
	
	if (denom == 0):
		return "COLLINEAR"
	
	if (denom < 0):
		offset = -denom / 2
	else:
		offset = denom / 2
	
	# The denom/2 is to get rounding instead of truncating. It
	# is added or subtracted to the numerator, depending upon the
	# sign of the numerator.
	num = (b1 * c2) - (b2 * c1)
	if (num < 0):
		x = (num - offset) / denom
	else:
		x = (num + offset) / denom
	
	num = (a2 * c1) - (a1 * c2)
	if (num < 0):
		y = ( num - offset) / denom
	else:
		y = (num + offset) / denom
	
	# lines_intersect
	return "DO_INTERSECT", x, y

lines = []
circles = []
while True:
	for event in pygame.event.get():
		if event.type == pygame.QUIT:
			sys.exit()
		
		if event.type == pygame.MOUSEBUTTONDOWN:
			if event.button == 1:
				if len(lines) and len(lines[-1]) == 1:
					lines[-1].append(event.pos)
					circles += [intersect(lines[-1], l)[1:] for l in lines[:-1] if intersect(lines[-1], l)[0] == "DO_INTERSECT"]
				else:
					lines.append([event.pos])
	
	screen.fill([255, 255, 255])
	[pygame.draw.aalines(screen, (150, 150, 150), False, l, 1) for l in lines if len(l) > 1]
	[pygame.draw.circle(screen, [255, 0, 0], c, 5, 1) for c in circles]
	pygame.display.flip()