TROUVER TOUT LES QUADRILATÉRES POSSIBLES AVEC N POINTS ALEATOIREMENT GÉNÉRÉS

###############################################  quad.py  ###################################

#!/usr/bin/env python
from random import randint
import operator
import view

def Cnp(n,p, l=None, res=None):
	"""Return combinaisons of k lenght of [1,2,3,...,n] set"""
	if l is None: l=[]
	if res is None: res=[]
	if p==0:
		res.append(l)
		return 
	if n==0: return  
	l1=list(l)
	l1.append(n)
	Cnp(n-1, p-1, l1, res)
	Cnp(n-1, p, l, res)
	return res

def Anp(n, p, l=None, res=None):
	"""Return arrangements of k lenght of [1,2,3,...,n] set"""
	if l is None: l=[]
	if res is None: res=[]	
	if p==0:
		res.append(l)
		return
	for k in range(1,n+1):
		if k not in l:
			l1=list(l)
			l1.append(k)
			Anp(n, p-1, l1,res)
	return res

def get_arrangements(list,p):
	"""Return all p-arrangement in the list
	ex = get_arrangements('ABC',3) == ('ABC','ACB','BAC','BCA','CAB','CBA')
	"""
	if len(list) < p:
		return []
	return [[list[i-1] for i in el] for el in Anp(len(list),p)]
	
def get_combinaisons(list,p):
	"""Return all p-subset in the list"""
	if len(list) < p:
		return []
	return [[list[i-1] for i in el] for el in Cnp(len(list),p)]

def is_colinear(u,v):
	(u1,u2),(v1,v2) = u,v
	return u1*v2 == u2*v1

def is_points_colinear(p1,p2,p3,p4):
	u = map(operator.sub,p2,p1)#just u[0] = p2[0] - p1[0],u[1] = ...
	v = map(operator.sub,p4,p3)
	return is_colinear(u,v)
	
def is_aligned(p1,p2,p3):
	return is_points_colinear(p1,p2,p2,p3)

def is_aligned_with_one_in(p1,points):
	"""Return True if p1 is aligned with one point in points"""
	for p2,p3 in get_arrangements(points,2):
		if is_aligned(p1,p2,p3):
			return True
	return False

def get_lines_pintersection(p1,p2,p3,p4):
	"""Return point of intersection between L1(p1,p2) and L2(p3,p4)"""
	if is_points_colinear(p1,p2,p3,p4) : return None
	(x1,y1),(x2,y2),(x3,y3),(x4,y4) = p1,p2,p3,p4
	i , j = (x1*y2-y1*x2),(x3*y4-y3*x4)
	q = float((x1-x2)*(y3-y4) - (y1-y2)*(x3-x4))
	x = (i*(x3-x4)-(x1-x2)*j) / q
	y = (i*(y3-y4)-(y1-y2)*j) / q
	return (x,y)

def get_lines_vintersection(u,v):
	return get_lines_pintersection(u[0],u[1],v[0],v[1])

def get_random_point(w,h):
	"""Return a random point with 0 <= x <= w and 0 <= x <= h"""
	return (randint(0,w),randint(0,h))

def get_random_points(n,w,h):
	"""Return n random points non-aligned"""
	points = []
	for i in xrange(n):
		p = get_random_point(w,h)
		while p in points or is_aligned_with_one_in(p,points):
			p = get_random_point(w,h)
		points.append(p)
	return points
	
def is_in_seg_but_not_in_line(p,seg):
	"""Return if p is in the segment (seg) but not in the line (formed by the seg two points)"""
	#Just verify if p is in seg bounding box
	xmin = min(seg[0][0],seg[1][0])
	ymin = min(seg[0][1],seg[1][1])
	xmax = max(seg[0][0],seg[1][0])
	ymax = max(seg[0][1],seg[1][1])
	x,y = p
	return x >= xmin and x <= xmax and ymin <= y and ymax >= y

def is_cross_quad(quad):
	"""Return True if quad is crossed
	ex:for a square ABCD,ACBD is crossed
	"""
	segs = []
	for i in range(4):
		segs.append((quad[i % 4],quad[(i+1) % 4]))
	i1 = get_lines_vintersection(segs[0],segs[2])
	i2 = get_lines_vintersection(segs[1],segs[3])
	if (i1 != None and is_in_seg_but_not_in_line(i1,segs[0]) and is_in_seg_but_not_in_line(i1,segs[2]))\
			or (i2 != None and is_in_seg_but_not_in_line(i2,segs[1]) and is_in_seg_but_not_in_line(i2,segs[3])) :
		return True
	return False

def in_triangle(p,tri):
	"""Return True if p is in tri"""
	(x1,y1),(x2,y2),(x3,y3) = tri
	xx,yy = p
	a0 = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))
	a1 = abs((x1-xx)*(y2-yy)-(x2-xx)*(y1-yy))
	a2 = abs((x2-xx)*(y3-yy)-(x3-xx)*(y2-yy))
	a3 = abs((x3-xx)*(y1-yy)-(x1-xx)*(y3-yy))
	return abs(a1+a2+a3-a0) <= 1.0/256

def get_interior_point(q):
	"""Return point inside the 3 others in this quad
	or None of q is convex
	"""
	for i,p in enumerate(q):
		tri = q[:i]+q[i+1:]
		if in_triangle(p,tri):
			return p

def count_quads(points):
	"""Count quads more efficiently"""
	c = 0
	for comb in get_combinaisons(points,4):
		ip = get_interior_point(comb)
		if ip == None: #convex
			c += 1 #1 choice
		else: #concave
			c += 3 #3 choice
	return c

def get_quads(points):
	"""Return all possible quads (non-crossed,BCDA == ABCD) for given points"""
	quads = []
	for comb in get_combinaisons(points,4):
		ip = get_interior_point(comb)
		if ip == None: #convex
			for arr in get_arrangements(comb[1:],3):
					q = (comb[0],) + tuple(arr)
					#print q
					if not is_cross_quad(q):
						quads.append(q)
						break
		else: #concave
			pos = comb.index(ip)
			quads.append([comb[(pos+i)%4] for i in (0,1,2,3)])
			quads.append([comb[(pos+i)%4] for i in (0,1,3,2)])
			quads.append([comb[(pos+i)%4] for i in (0,3,1,2)])
	return quads

def update(n = 15):
	"""Return (points,quads) with points = random points and quads = all possible quads"""
	points = get_random_points(n,view.WIDTH,view.HEIGHT)
	quads = get_quads(points)
	return (points,quads)
	
def quads_numbered(quads,points):
	"""Return ((1,3,4,2),(2,4,5,3),...) quads for given (((0.55,0.21),(541,322),(51,444),(12,32)),...) quads
	useful for debugging (see if quads are valid)
	"""
	l = []
	for q in quads:
		qn = []
		for p in q:
			qn.append(points.index(p))
		l.append(qn)
	return l
	
def print_stat(n,k):
	"""Print max and min in k loops"""
	list = []
	print 'Stat:k=',k
	print 
	ans = ()
	counter = 0
	
	for i in xrange(k):
		c = count_quads(get_random_points(n,1000,1000))
		list.append(c)
		new = [max(list),min(list)]
		if new != ans:
			ans = new
			print counter,new
		list = [max(list),min(list)]
		counter += 1
	
	print
	print "max:",max(list)
	print "min:",min(list)

def show_special_case(n,case):
	points,quads = update(n)
	while len(quads) != case:
		points,lines,quads = update(n)
	view.show(points,quads)

def main():
	points,quads = update()
	view.show(points,quads)
	#print_stat(7,100)
	#show_special_case(7,79)
	
if __name__ == "__main__":
	main()

###############################################  view.py  ###################################
#!/usr/bin/env python
import pygame ,os
import quad
from pygame.locals import *

WIDTH,HEIGHT = 800,600

def draw_text(surf,text,pos=(0,0),size = 40,color=(100,100,100)):
	font = pygame.font.Font(pygame.font.get_default_font(),size)
	text = font.render(text,True,color)
	surf.blit(text,pos)

def draw_points(screen,points):
	radius = 5
	font = pygame.font.Font(pygame.font.get_default_font(),radius*4)
	for i,point in enumerate(points):
		pygame.draw.circle(screen, (0,0,0), point, radius)
		text = font.render(str(i),True,(100,100,100))
		screen.blit(text,point)

def draw_quads(screen,quads):
	for q in quads:
		pygame.draw.polygon(screen, (255,87,0), q, 1)

def show(points,quads):
	os.environ['SDL_VIDEO_CENTERED'] = '1'
	screen = pygame.display.set_mode((WIDTH,HEIGHT))
	pygame.display.set_caption("Points viewer")
	pygame.font.init()
	selected = None
	points = [list(p) for p in points]  #tuple to list
	
	stopLoop = False
	while not stopLoop:
		for event in pygame.event.get():
			update = False
			if event.type == QUIT: stopLoop = True
			elif event.type == KEYDOWN:
				if event.key in (K_ESCAPE,K_RETURN):stopLoop = True
				if event.key == K_RIGHT:
					update = True
					points.append(list(quad.get_random_point(WIDTH,HEIGHT)))
				if event.key == K_LEFT:
					update = True
					points = points[:-1]
				elif event.key in (K_u,K_SPACE):
					update = True
					points = get_random_points(points)
					points = [list(p) for p in points]
			elif event.type == MOUSEBUTTONDOWN:
				if event.button == 1:
					for p in points:
						if abs(p[0] - event.pos[0]) < 10 and abs(p[1] - event.pos[1]) < 10 :
							selected = p
				elif event.button == 3:
							x,y = pygame.mouse.get_pos()
							points.append([x,y])
							update = True
			elif event.type == MOUSEBUTTONUP and event.button == 1:
				if selected is not None:
					update = True
					selected = None
			
			if update:
					draw_text(screen,"please wait...",(0,HEIGHT-40))
					pygame.display.flip()
					n = len(points)
					quads = quad.get_quads(points)
		
		screen.fill((255,255,255))	
		if selected is not None:
			selected[0],selected[1] = pygame.mouse.get_pos()
			pygame.draw.circle(screen, (255,200,200), selected, 10)

		draw_quads(screen,quads)
		draw_points(screen,points)
		draw_text(screen,str(len(points))+" points,"+str(len(quads))+" quads")
		pygame.display.flip()

if __name__ == "__main__":
	quad.main()