Distanza euclidea

Da Wikipedia, l'enciclopedia libera.

In matematica, la distanza euclidea è la tipica distanza fra due punti che si potrebbe misurare con un righello, che può essere ottenuta dall'applicazione ripetuta del teorema di Pitagora. Usando questa formula come distanza, lo spazio euclideo diventa uno spazio metrico (più in particolare risulta uno spazio di Hilbert). La letteratura tradizionale si riferisce a questa metrica come metrica pitagorica.

Indice

1 Distanza mono-dimensionale
2 Distanza bi-dimensionale
- 2.1 Approssimazione 2D per applicazioni informatiche
3 Distanza tri-dimensionale
- 3.1 Approssimazioni 3D per applicazioni informatiche
4 Distanza n-dimensionale
5 Voci correlate

[modifica] Distanza mono-dimensionale

Per due punti monodimensionali, $P = (p x)$ e $Q = (q x)$ , la distanza è calcolata come:

$\sqrt{(p_x-q_x)^2} = | p_x-q_x |$

Si utilizza il valore assoluto dato che la distanza è di norma un numero intero positivo.

[modifica] Distanza bi-dimensionale

Per due punti in due dimensioni, $P = (p x, p y)$ e $Q = (q x, q y)$ , la distanza è calcolata come:

$\sqrt{(p_x-q_x)^2 + (p_y-q_y)^2}$

[modifica] Approssimazione 2D per applicazioni informatiche

Un'approssimazione rapida della distanza in 2D basata su un intorno ottagonale può essere calcolata come segue. Sia $d x = | p x - q x |$ (valore assoluto) e $d y = | p y - q y |$ . Se $d y > d x$ , la distanza approssimata è $0.41 d x + 0.941246 d y$ ; se $d y < d x$ , si invertono i due valori.

La differenza fra dalla distanza esatta è fra il -6% e il +3% più dell'85% di tutte le possibili differenze sono fra il -3% e il +3%..

Il seguente codice Maple implementa questa approssimazione e produce un grafico con la circonferenza reale in nero e l'intorno ottagonale approssimato in rosso:

fasthypot :=
  unapply(piecewise(abs(dx)>abs(dy), 
                    abs(dx)*0.941246+abs(dy)*0.41,
                    abs(dy)*0.941246+abs(dx)*0.41),
          dx, dy):
hypot := unapply(sqrt(x^2+y^2), x, y):
plots[display](
  plots[implicitplot](fasthypot(x,y) > 1, 
                      x=-1.1..1.1, 
                      y=-1.1..1.1,
                      numpoints=4000),
  plottools[circle]([0,0], 1),
  scaling=constrained,thickness=2
);

Esistono altri tipi di approssimazione. Tutte cercano generalmente di evitare le radici quadrate, dato che sono costose in termini computazionali, e sono fonte di diversi errori: rapporto di velocità. Usando la notazione di cui sopra, l'approssimazione dx + dy − (1/2)×min(dx,dy) genera un errore fra lo 0% e il 12% (attribuito ad Alan Paeth). Un'approssimazione migliore in termini di errore RMS è dx + dy - (5/8)×min(dx,dy), per la quale è stimato un errore fra il -3% e il 7%.

È bene notare che se è necessario confrontare distanze (per le quali si vuole solo sapere ad esempio qual è la maggiore, e non l'effettiva differenza) non è necessario calcolare la radice quadrata di tutte se si tiene conto delle seguenti proprietà:

Se $A 2$ è maggiore di $B 2$ , allora anche la distanza $A$ sarà maggiore della distanza $B$ ;
Controllare se la distanza $A$ è maggiore della distanza $2 B$ è come confrontare $A 2$ con $(2 B) 2$ , $(4 B) 2$ e così via.

Un esempio del primo caso potrebbe essere quello di provare a determinare in quale punto della griglia di un sistema CAD/CAM 2D potrebbe ricadere (snap to) un punto arbitrario. Questa non è realmente un'approssimazione, comunque, dato che il risultato è esatto.

[modifica] Distanza tri-dimensionale

Per due punti in tre dimensioni, $P=(p_x,p_y,p_z)\,$ e $Q=(q_x,q_y,q_z)\,$ , la distanza è calcolata come:

$\sqrt{(p_x-q_x)^2 + (p_y-q_y)^2+(p_z-q_z)^2}.$

[modifica] Approssimazioni 3D per applicazioni informatiche

Come indicato nella sezione sull'approssimazione 2D, quando si confrontano distanze (per le quali si vuole solo sapere ad esempio qual è la maggiore, e non l'effettiva differenza) non è necessario calcolare la radice quadrata di tutte. Infatti vale la regola che se $A 2$ è maggiore di $B 2$ , allora anche la distanza $A$ sarà maggiore della distanza $B$ .

Ad esempio, se si cerca la minima distanza fra due superfici in uno spazio tridimensionale, usando un sistema CAD/CAM 3D, si potrebbe pensare di costruire una griglia di punti in ogni superficie e confrontare la distanza di ogni singolo punto nella prima superficie da ogni punto della seconda. Non è necessario conoscere la distanza effettiva, ma solo quale distanza è la minore. Una volta individuati i due punti più vicini, si può creare una griglia più piccola attorno a questi punti in ogni superficie e ripetere il procedimento. Dopo diverse iterazioni si riesce a valutare quali sono i punti più vicini in assoluto, e di questi calcolare la radice quadrata per ottenere un'ottima approssimazione della distanza minima fra le due superfici.