Projet : Lycée de secteur

Consignes projet

Les projets sont à rendre en ligne, sur la plateforme Elea. On n'utilisera pas la messagerie pour le rendu !

Fondamental

La qualité du code est toujours évaluée, on prendra soin de rajouter des commentaires utiles pour le relecture ainsi que des docstrings au niveau des fonctions Python.

On respectera donc les bonnes pratiques issues du PEP8 qui sont résumées sur cette page (en construction).

Attention

Tout projet non rendu à minuit le jour J sera pénalisé de -6 points pour 1 jour de retard et de -12 pts pour 2 jours. La note de zéro sera attribuée pour un projet non rendu ou rendu après 2 jours.

Aucun plagiat ou travail de groupe (sauf exception signalée) n'est autorisé, ce sera immédiatement la note minimale aux questions.

Il est strictement interdit d'utiliser une intelligence artificielle quelconque pour la réalisation des projets (sauf mention explicite).

La qualité du code est importante !

Bon travail !

Le problème

On dispose d'une liste qui associe à certaines adresses géographiques un lycée de secteur du département 31 (Haute-Garonne).

Les adresses sont en fait représentées par un couple (lat, lon) où lat est la latitude de l'adresse et lon est la longitude de l'adresse. Par exemple, le 7 rue St-Hilaire à Toulouse est représenté par le couple (43.61319, 1.44209).

On souhaite rédiger un programme qui, à une adresse donnée (donc un couple latitude et longitude), indique quel est son lycée de secteur, en se basant sur le lycée de secteur de ses voisins.

La liste d'association est stockée sous la forme d'un dictionnaire nommé adresses_lycees. Voici ci-dessous un extrait de cette liste d'association. Le fichier complet vous sera donné plus tard.

adresses_lycees = {
    (43.116227, 0.718689): "Lycée Bagatelle",
    (43.592111, 1.459428): "Lycée Marcelin Berthelot",
    (43.587685, 1.48444): "Lycée Saint-Sernin",
    ...
}

Où se trouvent nos données ?

Pour cet exercice, le dictionnaire contenant les données est déjà présent dans le fichier ci-joint :

Télécharger les données

On peut l'importer en le plaçant dans le même dossier que le fichier Python de cet exercice, et en indiquant dans votre fichier de travail le code suivant :

from donnees_lycees import adresses_lycees

La première valeur donnees_lycees correspond au nom du fichier sans l'extension .py et la deuxième adresses_lycees correspond au nom du dictionnaire dans le fichier.

Attention ! Sur Pyzo, on doit cocher la case Changer le répertoire courant lors de l'exécution d'un fichier (Change directory when executing file) dans le menu Exécuter (Run).

On rappelle quelques opérations élémentaires sur les dictionnaires :

for adresse in adresses_lycees:  # Permet de parcourir uniquement les adresses existantes, stockées en temps que couple de données.
for (lat, lon) in assoc:  # Idem en obtenant directement les valeurs lat et lon au lieu d'un couple (lat, lon).

(lat, lon) in assoc  # Renvoie True si l'adresse existe dans le dictionnaire, False sinon

lycee = assoc[(lat, lon)]  # Enregistre dans la variable lycee le nom du lycée associé à une adresse existante
lycee = assoc[adresse]  # Idem avec adresse un couple de coordonnées (lat, lon)

Toutes vos réponses sont à rédiger dans un fichier lycee_de_secteur.py. Vous devrez rajouter des tests dans les docstrings lorsque cela est possible, et d'autres tests plus globaux devront être exécutés dans le main. Le main peut être réalisé grâce au code ci-dessous, placé à la fin de votre fichier :

if __name__ == '__main__':
    # Tests des fonctions pouvant être testées avec doctest.
    # Il ne doit pas y avoir de failure dans l'exécution finale.
    import doctest
    doctest.testmod()

    # Placer ici les tests globaux, permettant de montrer que vous avez compris l'intérêt global du projet.

Question n°1 : Distance euclidienne entre deux adresses.

Rédiger une fonction distance(lat_1, lon_1, lat_2, lon_2) qui renvoie la distance euclidienne entre deux points (lat_1, lon_1) et (lat_2, lon_2).

def distance(lat_1, lon_1, lat_2, lon_2):
    """
    Expliquer ici ce que fait la fonction
    Entrées : -
              -
              -
              -
    Sortie :

    Voici un exemple de tests. Rajoutez-en au moins deux autres
    >>> distance(43.57801, 1.44627, 43.59577, 1.45256)
    0.018840958043584093
    """
    # Le code de la fonction est à rédiger ici
    return 0

Comment calculer une racine carrée ?

Il faut importer la fonction sqrt() depuis le module math :

from math import sqrt  # À placer à la toute première ligne du code

# Utilisation :
sqrt(4)  # Renvoie 2

Question n°2 : Les plus proches

On souhaite ensuite rédiger une fonction plus_proche(lat, lon, k, assoc) qui renvoie la liste des k plus proches adresses de (lat, lon) dans le dictionnaire assoc.

On propose pour cela l'algorithme suivant :

Stocker dans une liste distances l'ensemble des adresses et de leur distance à (lat, lon) sous la forme (distance, adresse).
- Il s'agira donc d'une liste contenant que des tuples ! Et chaque tuple contient alors un entier (la distance), et un couple de flottants (l'adresse).
- Voici un extrait de liste possible : distances = [(0.3, (43.52791, 1.23712)),(0.2, (43.21831, 1.63139)), ...]. On y voit deux adresses (43.52791, 1.23712) et (43.21831,1.63139) (obtenues grâce au dictionnaire assoc), et à distance 0.3 et 0.2 de l'adresse (lat, lon) (obtenue grâce à la fonction distance() précédemment réalisée).
Cette liste va permettre d'indiquer, pour chaque adresse, quelle est sa distance avec l'adresse (lat, lon) passée en paramètre de la fonction.
Trier la liste distances. Elle est alors triée par distance croissante. Rappel sur les tris.
- Cela fonctionne, car lorsqu'on trie une liste de tuples, le tri va se faire en priorité sur le premier élément du tuple (ici sur la distance). Ingénieux !
Parcourir les k premiers éléments de la liste distances et conserver les adresses dans une autre liste plus_proches. C'est cette liste qui vous faudra renvoyer.

Rédiger cet algorithme en Python.

def plus_proche(lat, lon, k, assoc):
    """
    À compléter et à tester
    >>> plus_proche(43.59577, 1.45256, 5, adresses_lycees)
    [(43.597102, 1.45326), (43.596568, 1.454731), (43.598, 1.453246), (43.597306, 1.450786), (43.595723, 1.454907)]
    """
    return []

Pourquoi assoc et pas adresses_lycees ?

Si on s'embête à utiliser le paramètre assoc de notre fonction, c'est pour pouvoir adapter rapidement le code avec une nouvelle liste d'adresses, par exemple pour un autre département.

Question n°3 : Le lycée de secteur

Rédiger une fonction lycee_de_secteur(lat, lon, k=5) qui renvoie le nom du lycée de secteur d'une adresse donnée en paramètre.

Vous êtes libres de choisir la valeur qui vous semble la plus appropriée pour k en paramètre par défaut.

On pourra utiliser max(liste, key=liste.count) pour connaître la valeur de l'élément le plus fréquent dans la liste liste

def lycee_de_secteur(lat, lon, k=5):
    """
    À compléter et à tester
    >>> lycee_de_secteur(43.46647, 1.06295, 10)
    'Lycée Charles de Gaulle'
    """
    return "Lycée Docteur Charles Mérieux"

Question n°4 : La Terre n'est pas plate

Avant de finaliser le projet, vous vous êtes rendus compte que la Terre n'est pas plate (comme un plan orthonormé) et que la courbure de la Terre ne permet pas de calculer la distance entre deux points géographiques grâce à la distance euclidienne.

La distance que nous allons devoir utiliser est appelée formule de haversine et s'applique à toute sphère. La formule est donnée ci-dessous :

\[d = 2 r \arcsin\left(\sqrt{\sin^2\left(\frac{x_2 - x_1}{2}\right) + \cos(x_1) \cos(x_2)\sin^2\left(\frac{y_2 - y_1}{2}\right)}\right)\]

où \(r\) est le rayon de la sphère (en km si on veut le résultat en km) ;
où \((x_1,y_1)\) correspond au premier point ;
et où \((x_2,y_2)\) correspond au second point.

Attention, les coordonnées sont à représenter en radians. Il faudra donc d'abord transformer les différentes coordonnées (exprimées en degrés) en radians.

Vous aurez aussi besoin d'importer quelques fonctions depuis le module math :

from math import sin, cos, atan2, sqrt, pi

Rédiger la fonction distance_km(lat1, lon1, lat2, lon2) qui implémente cette fonction de haversine.

def distance_km(lat1, lon1, lat2, lon2):
    """
    À compléter et à tester
    >>> distance_km(43.57801, 1.44627, 43.59577, 1.45256)
    2.038767515422201
    """
    pass

Question n°5 : Une carte pour visualiser les données

On s'intéresse désormais à pouvoir afficher une carte avec les voisins autour de l'adresse indiquée, et leur lycée de secteur, comme sur la carte ci-contre.

On utilisera pour cela le module TkinterMapView. Pour l'installer, il faut inscrire pip3 install tkintermapview dans un terminal. Sur Windows, on peut utiliser la combinaison + avant d'inscrire la commande précédente.

On dispose également de deux couleurs associées à chaque lycée, toujours dans le fichier donnees_lycees où couleurs_lycees est un dictionnaire qui à chaque lycée associe deux couleurs dans un tuple.

from donnees_lycees import adresses_lycees, couleurs_lycees

La fonction nécessaire pour afficher la carte est pré-écrite ci-dessous :

from tkinter import Tk, CENTER
from tkintermapview import TkinterMapView

def afficher_voisins(lat, lon, k=10):
    """
    À compléter et à tester
    """
    # Création de la fenetre Tkinter qui va permettre d'obtenir une interface graphique
    largeur, hauteur = 800, 600
    fenetre = Tk()
    fenetre.geometry(f"{largeur}x{hauteur}")
    fenetre.title("Lycées de secteur")

    # Ajout du fond de carte dans la fenêtre
    carte = TkinterMapView(fenetre, width=largeur, height=hauteur, corner_radius=0)
    carte.place(relx=0.5, rely=0.5, anchor=CENTER)

    # On récupère les lycées les plus proches
    plus_proches = ....

    # On ajoute les voisins à la carte
    for .... in ....:
        ......

    # On ajoute et on centre sur l'adresse de recherche, en affichant le nom du lycée final,
    ...

    # On crée un bouton pour fermer la carte, après ouverture
    Button(fenetre, text="Fermer", command=fenetre.destroy).pack()

    # On affiche la carte
    carte.mainloop()

Compléter cette fonction, et rédiger des tests dans le main.

Documentation TkinterMapView

Pour créer un marqueur sur une carte nommée carte, on utilise la syntaxe suivante :

carte.set_marker(latitude, longitude, text=un_texte, marker_color_circle=couleur_1, marker_color_outside=couleur_2)

où latitude et longitude sont des nombres flottants, un_texte est une chaîne de caractères qui sera affichée au-dessus du marqueur, et couleur_1 et couleur_2 sont des couleurs au format string, fournies dans le fichier donnees_lycees.

Pour centrer la carte et modifier le zoom, on peut utiliser la syntaxe suivante :

carte.set_position(..., marker=True)
carte.set_zoom(16)

où les ... correspondent à l'indentique à la méthode carte.set_marker(), et marker=True permet d'afficher un marqueur (en plus de centrer la carte).