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 la liste des 4 points

Dans l'exemple ci-dessus votre programme doit retourner 3 listes de 4 points

Création d'un ensemble de points

On veut créer l'ensemble suivant de points par un programme python

En supposant que le point dans le coin inférieur droit a pour coordonnées (0,0), et que l'unité est donné par le côté d'un petit carré, définir une fonction creeGrille() qui retourne une liste de tuples, les coordonnées des points du dessin.

La liste retournée est [(0,0),(0,2),(0,4),(0,6),(2,0),(2,2),(2,4),(2,6),(4,0),(4,2),(4,4),(4,6),(6,0),(6,2),(6,4),(6,6)]

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 de nombres
  2. Finir de mettre au point la fonction alignements(liste) qui retourne la liste des alignements de 4 points dans la liste
    
    def alignements(liste):
        listeAlignements = []
        for i in range(len(liste)):
            for j in range(i+1,len(liste)):
                alignement = [i,j]
                for k in range(j+1,len(liste)):
                    ...........
        return listeAlignements
     
     
  3. Tester la fonction alignements(liste) sur la liste associée au dessin suivant