EP01_01 — 📏 Three distance metrics in DIP

1.19.4 EP01_01 📏 Three distance metrics in DIP

In this activity, you must write a program that computes the three classical distances in DIP: Euclidean (L2), City‑Block (L1), and Chessboard (L∞).

Read 4 real numbers representing the coordinates: \(A_x, A_y, B_x, B_y\).
Compute the three distances using the formulas:

\[d_{\text{Euclidean}} = \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)\]

Print the three results, each on a separate line, formatted with two decimal places, in the following order: Euclidean, City‑block, Chessboard.

📌 Important:

Use the standard mathematical functions of your language: math.sqrt, abs (or fabs), and max.
The output must contain only the numbers (one per line), without additional text.
See an interactive simulator for this problem at the Figure 1.11 (graph with draggable points and visualization of the three metrics).

1.19.4.1 🖼️ Why does this matter? – Computational cost

In a 1000×1000 pixel image (1 million pixels), computing the distance from each pixel to a reference point requires 1 million operations. The choice of metric affects performance:

Metric	Operations per pixel	Relative cost (1M pixels)	When to use
Euclidean (L2)	2 subtractions, 2 multiplications, 1 addition, 1 `sqrt`	🔴 Most expensive – `sqrt` is costly	“Real” distance in continuous space
City‑block (L1)	2 subtractions, 2 `abs`, 1 addition	🟡 Moderate – no square root	Grids, robotics, binary images
Chessboard (L∞)	2 subtractions, 2 `abs`, 1 `max`	🟢 Most efficient	Piece movements, morphology

The sqrt function is computationally more expensive than operations such as addition, subtraction, multiplication, and absolute value. On modern CPUs, the difference can be small (about 1.5× to 3×), but in embedded systems or in loops with millions of iterations, any gain matters. Therefore, when the goal is only to compare distances (e.g., finding the nearest point), use the squared Euclidean distance.

1.19.4.2 📋 Task (specification for VPL)

Input:
A single line with four real numbers: Ax Ay Bx By

Output:
Three lines, each with a real number with two decimal places (Euclidean, City‑block, Chessboard).

1.19.4.3 📌 Examples

Input	Output	Observation
`0` `0` `3` `4`	`5.00` `7.00` `4.00`	3‑4‑5 triangle
`0` `0` `1` `1`	`1.41` `2.00` `1.00`	Unit diagonal

Example of testing sqrt in Python, with timeit isolating each operation:

%%writefile tmp/mm_out_1.cpp
// Compile: g++ -O2 -std=c++17 benchmark.cpp -o benchmark && ./benchmark
#include <iostream>
#include <iomanip>
#include <cmath>
#include <chrono>

const int N = 50'000'000;

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

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

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

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

    // Prevent optimization removal
    if (sum == 12345.6789) std::cout << sum;

    std::cout << std::fixed << std::setprecision(3);
    std::cout << "Soma simples       : " << t_soma.count() << " s\n";
    std::cout << "Soma + sqrt        : " << t_sqrt.count() << " s\n";
    std::cout << "Razão (sqrt/soma)  : " << std::setprecision(2)
              << (t_sqrt.count()/t_soma.count()) << "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 simples       : 0.141 s
Soma + sqrt        : 0.211 s
Razão (sqrt/soma)  : 1.49x

🎮 EP01_01 Simulator: Distance Metrics in Discrete Space Euclidean vs City-block vs Chessboard

Click and drag the points A or B on the Cartesian plane or adjust their coordinates below to compare the three distance metrics in real time.

📐 EUCLIDEAN (L2)

5.00

√(Δx² + Δy²)

🧱 CITY-BLOCK (L1)

7.00

|Δx| + |Δy|

🏁 CHESSBOARD (L∞)

4.00

max(|Δx|, |Δy|)

👆 Drag points A (Purple) or B (Orange) on the grid.

Point A

Point B

Geometric Legend: Dashed line (Euclidean), orthogonal L-shaped path (City-block) and highlight of the maximum dimension (Chessboard).

Euclidean City-block Chessboard (Max)

Figure 1.11: EP01_01 Simulator: Euclidean, City-block, and Chessboard Distances