Discussion :

[AJMont]

Bonjour à tous,
J'ai précédemment ouvert un billet sur ce problème en commençant une possibilité de résolution qui c'est avéré bien trop longue à calculer.

Voici le problème:
Je voudrais réalisé un programme qui détermine le nombre maximal de triangle non-secants pouvant être réalisé avec n points.

Exemple simple, avec quatre point:

on peut compter 4 triangles

mais avec quinze points nous pouvons obtenir ceci:



Combien y a t'il de triangle dans ce cas là?

Dans ces deux cas les point sont dans une position optimale, mais le problème devient plus difficile visuellement si les point sont placés aléatoirement.

J'ai tenté avec sympy de générer tous les triangles possible avec les point d'une liste pour ensuite nettoyer celle-ci des triangles sécants. C'est vraiment pas optimal...


Quelqu'un a t'il une idée à me proposer?

[Julien N]

Salut AJMont.

Si ton problème est d'ordre algorithmique tu auras plus de chance en passant par le forum dédié. J'avoue ne pas avoir suivi le post precedent. Quelle méhode utilise-tu pour résoudre le problème? Peut-être peut-on améliorer l'éfficacité du code sans changer l'algorithme.

Ju

[AJMont]

Pour mon premier essai, j'avais décidé de créer la liste de tout les triangles possible avec ces points, utiliser la permutation pour avoir tout les ordres possibles puis effacer au fur et à mesure tout les triangles sécant avec les précédents.
Or avec 6 points par exemple, cela signifie 20 triangle, soit 2.432902e+18 permutations a analyser...

Donc là je pense plutôt tenter l'inverse.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
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 = []
tri = []
group = []
merge = []
perm = []
 
combi_seg = list(itertools.combinations(range(0, len(p)), 2))
for result in combi_seg:
    (i, j) = result
    seg.extend([Segment(p[i] , p[j])])
 
combi_tria = list(itertools.combinations(range(0, len(p)), 3))
for result in combi_tria:
    (i, j, k) = result
    tri.extend([Triangle(p[i] , p[j], p[k])])
 
merge.extend(p)
merge.extend(seg)
merge.extend(tri)
 
group.append([tri[0]])
 
def createnocross(table):
    for element in table:
       for elem in tri:
          for poly in element:
             if intersection(elem, poly) not in merge:
                table.append([elem])
             else:
                element.extend(elem)
    return table
 
group = createnocross(group)
print len(group)

Mais ça fonctionne pas pour le moment, je dois avoir une erreur quelque part...

[Julien N]

ok, c'est pas evident (en tout cas pour moi) de voir ce qu'il se passe du côté math. A ce que j'ai compris, ici un triangle secant c'est un triangle qui n'est pas inscrit dans un autre (sujet precedent), ou un triangle qui "coupe" un autre?

Sur le net, "triangle secant" renvoie à sec=H/A (hypothenus sur adjacent), soit l'inverse de cosinus. Mais ça n'a pas l'air d'être le cas ici.

Sinon, bonne idée de passer par "combinations" de itertools. Tu peux faire des combinations d'objets directement. Au lieu de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

combi_seg = list(itertools.combinations(range(0, len(p)), 2))

Tu peux avoir:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

combi_seg = list(itertools.combinations(p, 2))

Ju

[AJMont]

Le vocabulaire que j'utilise n'est peut être par celui usité...

Pour moi deux triangles sécants se croisent, il y a donc une intersection entre des segments.

[AJMont]

voici un nouvelle technique

Je passe les intersections en matrice et je simplifie jusqu'à obtention de toute les combinaisons de triangle non-secant possible.
puis j'en extrait la plus grande.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
from sympy import *
from sympy.geometry import *
from sympy.plotting import *
from operator import itemgetter
import sys
from itertools import groupby
import itertools
from sympy.interactive.printing import init_printing
init_printing(use_unicode=False, wrap_line=False, no_global=True)
from sympy.matrices import *
sys.setrecursionlimit(10000)
 
p = [Point(0,0), Point(2,0), Point(2,2), Point(0,2), Point(1.25,0.5)]
seg = []
tri = []
group = []
merge = []
perm = []
 
combi_seg = list(itertools.combinations(range(0, len(p)), 2))
for result in combi_seg:
    (i, j) = result
    seg.extend([Segment(p[i] , p[j])])
 
combi_tria = list(itertools.combinations(range(0, len(p)), 3))
for result in combi_tria:
    (i, j, k) = result
    tri.extend([Triangle(p[i] , p[j], p[k])])
 
merge.extend(p)
merge.extend(seg)
merge.extend(tri)
 
def creatematrix(i,j):
     if (i == 0 and j == 0):
        return "ensemb"
     if (i == 0):
        return j
     if (j == 0):
        return i
     for element in intersection(tri[i-1], tri[j-1]):
        if element not in merge:
           return "0"
     return "1"
 
Matrice = Matrix(len(tri)+1, len(tri)+1, creatematrix)
 
def removezeros(matr, j):
    mat = matr[:,:]
    i = 0
    mat[0,0] = str(mat[0,0]) + "_" + str(mat[0,j])
    while (i <= max(mat.shape)):
       try:
          while (mat[j,i] == 0):
             mat.col_del(i)
          mat.col_del(j)
          i += 1
       except LookupError:
          break
    i = 0
    while (i <= max(mat.shape)):
       try:
          if (mat[i,0] != mat[0,i]):
             while (mat[i,0] != mat[0,i]):
                mat.row_del(i)
          else:
             i += 1 
       except LookupError:
          break
    while (max(mat.shape)!=min(mat.shape)):
       mat.row_del(max(mat.shape))
    return mat
 
def multiplzeros(matr):
    mat2 = matr[:,:]
    final = []
    if max(matr.shape) == 1:
       return [matr]
    for k in range(1, max(matr.shape)):
       final.append(removezeros(mat2,k))
    return final
 
Matrice2 = Matrice[:,:]
Matrice2 = multiplzeros(Matrice2)
 
def f2(seq):   # *********
    # order preserving
    checked = []
    for e in seq:
        if e not in checked:
            checked.append(e)
    return checked
 
 
Matrice3 = []
 
for elem in Matrice2:
    Matrice3.extend(multiplzeros(elem))
 
def reocc(Matr):
   test = len(Matr)
   temp = []
   for elem in Matr:
      temp.extend(multiplzeros(elem))
   return temp
 
Matrice3 = reocc(reocc(reocc(reocc(reocc(reocc(Matrice3))))))
 
Matrice4 = str(Matrice3)
Matrice4 = Matrice4.replace("Matrix([[ensemb_","")
Matrice4 = Matrice4.replace("[","")
Matrice4 = Matrice4.replace(" ","")
Matrice4 = Matrice4.replace("]])", "")
Matrice4 = Matrice4.replace("]","")
Matrice4 = [map(int, x.split('_')) for x in Matrice4.split(',')]
Matrice5 = []
i=0
while i < len(Matrice4):
   Matrice5.append(sorted(Matrice4[i]))
   i += 1
Matrice5 = f2(Matrice5)
Matrice5len = []
i=0
while i < len(Matrice5):
   Matrice5len.extend([len(Matrice5[i])])
   i += 1
 
mtemp = max(Matrice5len)
indexM5m = [i for i, j in enumerate(Matrice5len) if j == mtemp]
 
for i in indexM5m:
   print Matrice5[i]
   for j in Matrice5[i]:
      print tri[j-1]
 
print Matrice

Mais j'ai un problème visiblement à un moment ou à un autre ma fonction removezeros ne fonctionne pas. je pense que ca viens du fait qu'en supprimant une colonne l'index change et donc le test aussi....
Une solution?

[AJMont]

J'ai changé ma manière de supprimer les colonnes et ça fonctionne!
Quelqu'un peu regarder au travers pour essayer d'optimiser un peu tout ça?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
from sympy import *
from sympy.geometry import *
from sympy.plotting import *
from operator import itemgetter
import sys
from itertools import groupby
import itertools
from sympy.interactive.printing import init_printing
init_printing(use_unicode=False, wrap_line=False, no_global=True)
from sympy.matrices import *
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)]
 
#p = [Point(0,0), Point(8,0), Point(8,8), Point(0,8), Point(5,2)]
seg = []
tri = []
group = []
merge = []
perm = []
 
combi_seg = list(itertools.combinations(range(0, len(p)), 2))
for result in combi_seg:
    (i, j) = result
    seg.extend([Segment(p[i] , p[j])])
 
combi_tria = list(itertools.combinations(range(0, len(p)), 3))
for result in combi_tria:
    (i, j, k) = result
    tri.extend([Triangle(p[i] , p[j], p[k])])
 
merge.extend(p)
merge.extend(seg)
merge.extend(tri)
 
def creatematrix(i,j):
     if (i == 0 and j == 0):
        return "ensemb"
     if (i == 0):
        return j
     if (j == 0):
        return i
     for element in intersection(tri[i-1], tri[j-1]):
        if element not in merge:
           return "0"
     return "1"
 
Matrice = Matrix(len(tri)+1, len(tri)+1, creatematrix)
 
def removezeros(matr, j):
    mat = matr[:,:]
    i = 1
    mat[0,0] = str(mat[0,0]) + "_" + str(mat[0,j])
    while (i <= max(mat.shape)+1):
       try:
          if (mat[j,i] == 0):
             mat[0,i] = "erase"
             mat[i,0] = "erase"
          i += 1
       except LookupError:
          mat[0,j] = "erase"
          mat[j,0] = "erase"
          break
    i = 1
    while (i <= max(mat.shape)+1):
       try:
          while (str(mat[i,0]) == "erase"):
             mat.row_del(i)
             mat.col_del(i)
          i += 1 
       except LookupError:
          break
    return mat
 
def multiplzeros(matr):
    mat2 = matr[:,:]
    final = []
    if max(matr.shape) == 1:
       return [matr]
    for k in range(1, max(matr.shape)):
       final.append(removezeros(mat2,k))
    return final
 
Matrice2 = Matrice[:,:]
Matrice2 = multiplzeros(Matrice2)
 
def f2(seq):   # *********
    # order preserving
    checked = []
    for e in seq:
        if e not in checked:
            checked.append(e)
    return checked
 
 
Matrice3 = []
 
for elem in Matrice2:
    Matrice3.extend(multiplzeros(elem))
 
def reocc(Matr):
   test = len(Matr)
   temp = []
   for elem in Matr:
      temp.extend(multiplzeros(elem))
   return temp
 
Matrice3 = reocc(reocc(reocc(reocc(reocc(reocc(Matrice3))))))
 
Matrice4 = str(Matrice3)
Matrice4 = Matrice4.replace("Matrix([[ensemb_","")
Matrice4 = Matrice4.replace("[","")
Matrice4 = Matrice4.replace(" ","")
Matrice4 = Matrice4.replace("]])", "")
Matrice4 = Matrice4.replace("]","")
Matrice4 = [map(int, x.split('_')) for x in Matrice4.split(',')]
Matrice5 = []
i=0
while i < len(Matrice4):
   Matrice5.append(sorted(Matrice4[i]))
   i += 1
Matrice5 = f2(Matrice5)
Matrice5len = []
i=0
while i < len(Matrice5):
   Matrice5len.extend([len(Matrice5[i])])
   i += 1
 
mtemp = max(Matrice5len)
indexM5m = [i for i, j in enumerate(Matrice5len) if j == mtemp]
 
for i in indexM5m:
   print Matrice5[i]
   for j in Matrice5[i]:
      print j-1
      print tri[j-1]
 
print Matrice5