Proche voisin

On souhaite programmer une fonction donnant le point d'une liste de points le plus proche d'un point de départ. Les points sont tous à coordonnées entières. Les points sont donnés sous la forme d'un tuple de deux entiers qui sont leurs coordonnées (dans un repère orthonormé). La liste des points à traiter est donc un tableau de tuples.

On rappelle que la distance entre deux points du plan de coordonnées \((x; y)\) et \((x'; y')\) est donnée par la formule :

\(d=\sqrt{(x-x')^2+(y-y')^2}\)

On importe pour cela la fonction racine carrée (sqrt) du module math de Python.

Exemples

🐍 Console Python
>>> distance((1, 0), (5, 3))
5.0
>>> distance((1, -4), (6, 8))
13.0
>>> proche_voisin([(7, 9), (2, 5), (5, 2)], (0, 0))
(2, 5)
>>> proche_voisin([(7, 9), (2, 5), (5, 2)], (5, 2))
(5, 2)

Compléter le code des fonctions distance et proche_voisin fournies ci-dessous pour qu’elles répondent à leurs spécifications.

Attention

Il est interdit d'utiliser min

Compléter le code ci-dessous

###
# Testsbksl-nlassert distance((1, 0), (5, 3)) == 5bksl-nlassert distance((1, -4), (6, 8)) == 13bksl-nlassert prochepy-undvoisin([(7, 9), (2, 5), (5, 2)], (0, 0)) == (2, 5)bksl-nlassert prochepy-undvoisin([(7, 9), (2, 5), (5, 2)], (5, 2)) == (5, 2)bksl-nlbksl-nl# Autre testsbksl-nlassert prochepy-undvoisin([(7, 9), (2, 5), (5, 2), (3, 4)], (0, 0)) == (3, 4)bksl-nlassert prochepy-undvoisin([(i, 1) for i in range(-50, 50)], (5, 3)) == (5, 1)bksl-nlbksl-nlbksl-nlbksl-nl 5/5
from math import sqrt # import de la fonction racine carréebksl-nlbksl-nldef distance(point1, point2):bksl-nl """ Calcule et renvoie la distance entre deux points. """bksl-nl return sqrt((...)py-strpy-str2 + (...)py-strpy-str2)bksl-nlbksl-nldef prochepy-undvoisin(tab, depart):bksl-nl """ Renvoie le point du tableau tab se trouvant à la plus courte distance du point depart."""bksl-nl point = tab[0]bksl-nl minpy-unddist = ...bksl-nl for i in range (1, ...):bksl-nl if distance(tab[i], depart)...:bksl-nl point = ...bksl-nl minpy-unddist = ...bksl-nl return pointbksl-nlbksl-nl# Testsbksl-nlassert distance((1, 0), (5, 3)) == 5bksl-nlassert distance((1, -4), (6, 8)) == 13bksl-nlassert prochepy-undvoisin([(7, 9), (2, 5), (5, 2)], (0, 0)) == (2, 5)bksl-nlassert prochepy-undvoisin([(7, 9), (2, 5), (5, 2)], (5, 2)) == (5, 2)bksl-nlbksl-nlbksl-nlfrom math import sqrt # import de la fonction racine carréebksl-nlbksl-nldef distance(pointpy-und1, pointpy-und2):bksl-nl """ Calcule et renvoie la distance entre deux points. """bksl-nl return sqrt((pointpy-und1[0] - pointpy-und2[0])py-strpy-str2 + (pointpy-und1[1] - pointpy-und2[1])py-strpy-str2)bksl-nlbksl-nldef prochepy-undvoisin(tab, depart):bksl-nl """ Renvoie le point du tableau tab se trouvant à la plus courte distance du point depart."""bksl-nl point = tab[0]bksl-nl minpy-unddist = distance(point, depart)bksl-nl for i in range (1, len(tab)):bksl-nl if distance(tab[i], depart) < minpy-unddist:bksl-nl point = tab[i]bksl-nl minpy-unddist = distance(tab[i], depart)bksl-nl return pointbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl

Attention

⚠️🌵 Il faut absolument éviter de comparer deux flottants entre eux.

Exemple

🐍 Console Python
>>> 0.1 + 0.2 > 0.3
True
>>> 0.1 + 0.2
0.30000000000000004

Dans cet exercice les coordonnées des points sont supposées entières, mais le calcul de distance avec la racine carrée donne des flottants, qui vont être comparés à d'autres nombres.

Pour travailler avec des entiers, il aurait fallu comparer les carrés des distances, avec évidemment des points de coordonnées entières. Les distances étant des nombres positifs, le problème aurait pû être résolu ainsi.