Alignements de points

Alignements de points

Sont donnés un ensemble de points du plan à coordonnées entières.

Lorsqu'il y a un alignement de points, on est assuré qu'il n'y a pas plus de quatre points dans le même alignement.

En sortie du programme on souhaite tous les alignements de 4 points présents dans l'ensemble de points, un alignement de 4 points est caractérisé par les deux points "extrêmes" de l'alignement

Dans l'exemple suivant votre programme doit retourner: (P6,P10) ou (P10,P6) mais pas (P8,P10), (P10,P3) ou (P3,P10) ,(P3,P6) ou (P6,P3)

Création d'ensemble de points

On ne veut pas créer "à la main" des ensembles de points mais programmer leur création

Comment par des boucles créer un ensemble de points similaire à l'exemple suivant ?(Donner un algorithme)

On veut visualiser avec la tortue (ou matplotlib), les points et les alignements trouvés par conséquent il faudra prévoir des points suffisamment espacés

Faire la même chose sur l'exemple suivant

Mémorisation des ensembles de points

A chaque fois qu'un point, sous la forme de deux entiers i et j est créé, on va le stocker sous la forme d'une chaîne de caractères,dans un ensemble de caractères appelé fichier texte, ainsi:

Dans le même répertoire où se trouve notre fichier .py qui créé l'ensemble de points sous forme de grille, appelé grille4x4.py, se trouvera un fichier texte appelé grille4x4.txt et dans grille4x4.py on va créé grille4x4.txt ainsi:

Compléter le programme suivant


ESPACE = 100
with open("grille4x4.txt", "w") as fichier: 
    #BOUCLES à compléter
            chaine = str(i*ESPACE)+" "+str(j*ESPACE)+"\r"
            fichier.write(chaine)


De même créer le fichier "etoile.txt"

Lecture d'un fichier de points et traitement. Notion de listes

Pour mémoriser un ensemble de points nous avons vu la notion de fichier texte, par contre pour détecter d'éventuels alignements de points on ne peut pas le faire directement dans le fichier, car d'une part, ce fichier est composé uniquement de chaîne de caractères et non d'entiers, donc on ne pourra pas faire de calculs, et d'autre part ce fichier est situé dans le disque dur de l'ordinateur or pour traiter des données rapidement il faut les rapatrier dans la mémoire vive de l'ordinateur

Nous allons découvrir un nouveau type de variables en python, la liste

Exécuter le programme suivant et ...compléter il ne retourne pas exactement ce qu'on veux


listePoints = []
with open("grille4x4.txt","r") as fichier:
    for ligne in fichier:
    	liste = ligne.split()
    	
        point = (liste[0],liste[1])
        listePoints.append(point)
#afficher le contenu de la variable listePoints
print(listePoints)

On peut traiter la liste ListePoints en compréhension et écrire

Exécuter le programme suivant et ...compléter il ne retourne pas exactement ce qu'on veux


listePoints = []
with open("grille4x4.txt","r") as fichier:
    listePoints = [(ligne.split()[0],ligne.split()[1]) for ligne in fichier]
#afficher le contenu de la variable listePoints
print(listePoints)

Traitement. Exercices

  1. Créer une fonction sontAlignes(p,q,r) qui retourne vrai si les points p,q et r sont alignés. On rappelle que les points p,q et r sont des tuples
  2. Créer une fonction compare(i,j) qui compare deux points i et j ainsi ....
  3. Créer une fonction extremites(i,j,k,l) qui retourne un tuple de points, les extremités de l'alignement i,j,k,l
  4. Mettre au point et traduire l'algorithme (Brute Force) suivant:
    
    listeAlignements <- []
    Pour chaque combinaison (i,j,k) de 3 éléments 
    de la liste listePoints (3 boucles imbriquées) avec i < j < k faire
        si sontAlignes(i,j,k)
            Pour chaque l > k dans listePoints
                si sontAlignes(i,j,l)
                    listeAlignements <- extremites(i,j,k,l)
                    arrêter l'itération