TNI+VO · Exercice de Programmation

EP01_01 — 📏 Trois métriques de distance en TNI

1.17.1 EP01_01 📏 Trois métriques de distance en TNI

Dans cette activité, vous devez écrire un programme qui calcule les trois distances classiques en TNI : euclidienne (L2), City‑Block (L1) et Chessboard (L∞).

  • Lisez 4 nombres réels qui représentent les coordonnées : \(A_x, A_y, B_x, B_y\).
  • Calculez les trois distances à l’aide des formules :

\[d_{\text{Euclidienne}} = \sqrt{(B_x - A_x)^2 + (B_y - A_y)^2}\]

\[d_{\text{City-block}} = |B_x - A_x| + |B_y - A_y|\]

\[d_{\text{Chessboard}} = \max\big(|B_x - A_x|,\; |B_y - A_y|\big)\]

  • Affichez les trois résultats, chacun sur une ligne, formatés avec deux décimales, dans l’ordre : euclidienne, City‑block, Chessboard.

📌 Important :

  • Utilisez les fonctions mathématiques standard de votre langage : math.sqrt, abs (ou fabs) et max.
  • La sortie doit contenir uniquement les nombres (un par ligne), sans texte supplémentaire.
  • Voir un simulateur interactif pour cette question à la Figure 1.11 (graphique avec glissement des points et visualisation des trois métriques).

1.17.1.1 🖼️ Pourquoi cela importe-t-il ? – Coût computationnel

Dans une image 1000×1000 pixels (1 million de pixels), calculer la distance de chaque pixel à un point de référence exige 1 million d’opérations. Le choix de la métrique affecte la performance :

Métrique Opérations par pixel Coût relatif (1M pixels) Quand l’utiliser
Euclidienne (L2) 2 soustractions, 2 multiplications, 1 addition, 1 sqrt 🔴 Plus coûteuse – sqrt est lente Distance « réelle » dans l’espace continu
City‑block (L1) 2 soustractions, 2 abs, 1 addition 🟡 Modérée – sans racine carrée Grilles, robotique, images binaires
Chessboard (L∞) 2 soustractions, 2 abs, 1 max 🟢 Plus efficace Déplacements de pièces, morphologie

La fonction sqrt est computationnellement plus coûteuse que des opérations comme l’addition, la soustraction, la multiplication et la valeur absolue. Sur les processeurs modernes, la différence peut être faible (environ 1,5× à 3×), mais dans les systèmes embarqués ou dans des boucles de millions d’itérations, tout gain compte. Pour cette raison, lorsque l’objectif est uniquement de comparer des distances (ex. : trouver le point le plus proche), utilisez la distance euclidienne au carré.

1.17.1.2 📋 Tâche (spécification pour VPL)

Entrée :
Une seule ligne avec quatre nombres réels : Ax Ay Bx By

Sortie :
Trois lignes, chacune avec un nombre réel à deux décimales (euclidienne, City‑block, Chessboard).

1.17.1.3 📌 Exemples

Entrée Sortie Observation
0
0
3
4		 5.00
7.00
4.00		 Triangle 3‑4‑5
0
0
1
1		 1.41
2.00
1.00		 Diagonale unitaire

Exemple de test de sqrt en Python, avec timeit isolant chaque opération :

%%writefile tmp/mm_out_1.cpp
#include <iostream>
#include <chrono>
#include <cmath>
#include <iomanip>

int main() {
    const int N = 50'000'000;

    auto apenas_soma = []() {
        double a = 3.0, b = 4.0;
        return a + b;
    };

    auto soma_e_sqrt = []() {
        double a = 3.0, b = 4.0;
        return std::sqrt(a*a + b*b);
    };

    auto start_soma = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        apenas_soma();
    }
    auto end_soma = std::chrono::high_resolution_clock::now();
    double t_soma = std::chrono::duration<double>(end_soma - start_soma).count();

    auto start_sqrt = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        soma_e_sqrt();
    }
    auto end_sqrt = std::chrono::high_resolution_clock::now();
    double t_sqrt = std::chrono::duration<double>(end_sqrt - start_sqrt).count();

    std::cout << std::fixed << std::setprecision(3);
    std::cout << "Soma simple       : " << t_soma << " s\n";
    std::cout << "Soma + sqrt       : " << t_sqrt << " s\n";
    std::cout << "Razão (sqrt/soma) : " << std::setprecision(2) << (t_sqrt/t_soma) << "x\n";

    return 0;
}
Overwriting tmp/mm_out_1.cpp
!g++ -I. -std=c++17 tmp/mm_out_1.cpp -o tmp/mm_out_1 \
  && ./tmp/mm_out_1
Soma simple       : 0.120 s
Soma + sqrt       : 0.233 s
Razão (sqrt/soma) : 1.94x
🎮 Simulateur EP01_01 : Métriques de distance dans l'espace discret Euclidienne vs City-block vs Échiquier

Cliquez et faites glisser les points A ou B sur le plan cartésien ou ajustez leurs coordonnées ci-dessous pour comparer les trois métriques de distance en temps réel.

📐 EUCLIDIENNE (L2)
5.00
√(Δx² + Δy²)
🧱 CITY-BLOCK (L1)
7.00
|Δx| + |Δy|
🏁 ÉCHIQUIER (L∞)
4.00
max(|Δx|, |Δy|)
👆 Faites glisser les points A (Violet) ou B (Orange) sur la grille.
Point A
Point B
Légende géométrique : Ligne pointillée (Euclidienne), Chemin orthogonal en L (City-block) et Mise en évidence de la dimension maximale (Échiquier).
Euclidienne City-block Échiquier (Max)
Figure 1.11: Simulateur EP01_01 : Distances Euclidienne, City-block et Échiquier