sympy et conteur du nombre maximal de triangles

Version imprimable

Bonjour à tous,
Je suis tous neuf dans python, et j'essaye de réaliser un programme qui lorsqu'on lui soumet des coordonnées de points, il compte le maximum de triangle non-sécant (pouvant être inscrit).

Jusqu'ici, je fonctionne au pas à pas...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from sympy import * from sympy.geometry import * from sympy.plotting import * import sys sys.setrecursionlimit(10000) p = [Point(45489772381, -736449623108), Point(45489772381, -736136770248), Point(455065875115, -736292552948), Point(454927507396, -736292552948), Point(454956086125, -736292552948), Point(454956086125, -736344480515), Point(454956086125, -736240625381), Point(454974435912, -736363148689), Point(454974435912, -736221957207), Point(454990378684, -736274957657), Point(454990378684, -736310148239)] l = 0 seg = [] group = [] for i in range(0, len(p)-1): for j in range (i+1, len(p)): l += 1 seg.extend([Segment(p[i] , p[j])])
cette première partie liste tous les segments possible.

puis dans un premier temps je voudrais effacer tous les segments qui se croisent et en faire des groupes
d'où la fonction suivante qui pour le moment devrait juste nettoyer la liste primaire de tous les liens qui croisent les segments précédements "admis"
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 group = [] group.append(seg) def main(): tabl = [] cleancrossed(tabl) def cleancrossed(tabl): print len(tabl) temp = tabl for i in range(0, len(tabl)-1): for j in range (i+1, len(tabl)): for element in intersection(seg[i], seg[j]): if element in p: test = len(tabl) else : print seg[j] tabl = [x for x in temp if x != seg[j]] return cleancrossed(tabl); return; cleancrossed(group[0]) print group[0] print len(group[0])
mais qui a terme devrait générer tous les groupes possibles.

Donc pour le moment je bloque dans cette fonction car elle reprend toujours au même point;

Dans le cas ci dessus la liste primaire fait 55 éléments, la fonction tourne une première fois retire le premier segment secant, puis reprend la fonction avec une liste de 54 éléments, puis ça boucle à 54....
Pourquoi je ne sais pas....

Je pense que ça doit être au niveau de ma compréhension des variables, mais je trouve pas de solution... Si quelqu'un peut trouver une solution et m'expliquer, je serais le plus heureux!

Merci

11/07/2014, 08h39
deusyss
Salut,

Je n'ai pas trop regardé ton code en détail, du moins pas assez pour te donner la solution. N'ayant pas simpy sur ma machine, pourrais tu nous indiquer l'indice qui bloque à 54?

Sinon, mon message va porter plus sur tes boucles for imbriquée qui sont une catastrophe, en terme de performance. Ne t'inquiète pas, on est tous passé par là ;), et justement j'en profite pour t'indiquer l'existance de itertools :lun:

Voici un exemple trouvé sur le net et bien parlant:
Code:

1 2 3 4 5 6 7 8 9 10 a = ['un'] b = a + ['deux'] c = b + ['trois'] d = c + ['quatre'] for i in a: for j in b: for k in c: for l in d: print i,j,k,l
devient
Code:

1 2 3 4 5 6 7 a = ['un'] b = a + ['deux'] c = b + ['trois'] d = c + ['quatre'] for i, j, k, l in itertools.product(a,b,c,d): print i,j,k,l
Bien sur, cela ne fonctionne que pour les imbrications directes dans ce cas. Je t'invite à lire la doc d'itertools très complete.

Outre l'amelioration de la lisibilité, sur des choses un peu consommatrice de ressources, tu verra les performances de l'algo grimper en fleche.

j'attend ton retour pour l'indice (est-ce i, j ou element?) qui pose probleme?
11/07/2014, 13h37
AJMont

Merci pour ta réponse et merci pour itertools, je pense qu je vais pouvoir m'en servir.

Le résultat qui stagne à 54 c'est le print de la longueur de la liste que je veux "réduire".

Code:

print len(group[0])

donc c'est mon appel des variable qui pose un problème car la longueur initiale de la liste est 55; donc c'est comme si ma fonction ne marchait qu'une fois et ne s'appelle pas elle même. (enfin elle s'appelle mais toujours avec la liste initiale)

Je suis sur la bonne voie je crois, mon erreur était dans la fonction en elle même (les intersections testée étaient toujours les mêmes....)

voici mon update

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from sympy import *
from sympy.geometry import *
from sympy.plotting import *
import sys
import itertools
sys.setrecursionlimit(10000)
 
p = [Point(45489772381, -736449623108), Point(45489772381, -736136770248), Point(455065875115, -736292552948), Point(454927507396, -736292552948), Point(454956086125, -736292552948), Point(454956086125, -736344480515), Point(454956086125, -736240625381), Point(454974435912, -736363148689), Point(454974435912, -736221957207), Point(454990378684, -736274957657), Point(454990378684, -736310148239)]
seg = []
group = []
 
results = list(itertools.combinations(range(0, len(p)), 2))
for result in results:
    (i, j) = result
    seg.extend([Segment(p[i] , p[j])])
 
group = []
group.append(seg)
 
def cleancrossed(tabl):
    results = list(itertools.combinations(range(0, len(tabl)), 2))
    for result in results:
       (i, j) = result
       for element in intersection(tabl[i], tabl[j]):
          if element in p:
             test = len(tabl)
          else :
             tabl = [x for x in tabl if x != tabl[j]]
             return cleancrossed(tabl)
    return tabl;
 
group[0] = cleancrossed(group[0])
print len(group[0])

14/07/2014, 20h39
AJMont

Pour tous ceux qui ce sont intéressé au problème, ma technique est une voie sans issue.. (sauf peut être si vous avez un supercalculateur sous la main)
Merci