DIP+CV · Programming Exercise

EP01_01 — 📏 Three distance metrics in DIP

1.18.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.18.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.18.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.18.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:

import math
import timeit

N = 50_000_000

def apenas_soma():
    a, b = 3.0, 4.0
    return a + b

def soma_e_sqrt():
    a, b = 3.0, 4.0
    return math.sqrt(a*a + b*b)

t_soma = timeit.timeit(apenas_soma, number=N)
t_sqrt = timeit.timeit(soma_e_sqrt, number=N)

print(f"Simple sum         : {t_soma:.3f} s")
print(f"Sum + sqrt         : {t_sqrt:.3f} s")
print(f"Ratio (sqrt/sum)   : {t_sqrt/t_soma:.2f}x")
Simple sum         : 2.613 s
Sum + sqrt         : 5.177 s
Ratio (sqrt/sum)   : 1.98x
🎮 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