Trouver tout les quadrilatéres possibles avec n points aleatoirement générés

Commenter

Contenu du snippet

Alors je viens de finir un programme sans prétention qui ,je l'espère,vous impressionnera:

Il sait:
<ul>
<li>Trouver le nombre de quadrilatère / les donner</li>
<li>Trouver un cas spécial (6 points,39 quadrilatères)</li>
<li>Faire de rapides stats (maximum/minimum de quadrilatères pour n points en ayant faire k essais</li>
<li>Afficher les quadrilatères trouvés
<ul>
<li> Déplacer les points (clic gauche->drag)</li>
<li> Ajouter de nouveaux points (clic droit)</li>
<li> Refaire une nouvelle liste de points (espace)</li>
<li> Changer le nombre de points (flèche droite et gauche)</li>
</ul></li>
</ul>

Pour le lancer il vous faudra python (2.x) et pygame (paquet python-pygame)

Source / Exemple : 


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

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.