Distanze in spazi 3D
Ciao!
Ho un piccolo problema che non riesco ad aggirare, eccolo:
Ho due punti noti (chiamiamoli A e B) in uno spazio tridimensionale per cui passa una retta (r) di equazione non nota (andrà ricavata da A e B). Ho un terzo punto noto (C) e voglio calcolare la distanza minima tra C ed r. Credo che questo problema corrisponda a trovare il punto in cui una retta perpendicolare a r e passante per C interseca proprio r. Credo... Il mio problema, incertezza a parte, è che non saprei proprio da dove cominciare. Qualcuno sa come fare?
Mi scuso se nel forum esiste già una domanda simile, ma comunque io non l'ho trovata.
Grazie in anticipo!
Ho un piccolo problema che non riesco ad aggirare, eccolo:
Ho due punti noti (chiamiamoli A e B) in uno spazio tridimensionale per cui passa una retta (r) di equazione non nota (andrà ricavata da A e B). Ho un terzo punto noto (C) e voglio calcolare la distanza minima tra C ed r. Credo che questo problema corrisponda a trovare il punto in cui una retta perpendicolare a r e passante per C interseca proprio r. Credo... Il mio problema, incertezza a parte, è che non saprei proprio da dove cominciare. Qualcuno sa come fare?
Mi scuso se nel forum esiste già una domanda simile, ma comunque io non l'ho trovata.
Grazie in anticipo!
Risposte
Una strada, quella più brute force, passa dall'esplicitare l'equazione della retta passante per $A, B$. Poi si applicano le formule note per la distanza punto-retta. Ma non ti conviene, meglio cercare qualcosa di più efficace.
Quello che mi viene in mente è fare un discorso geometrico. La distanza che ti serve è infatti l'altezza del triangolo $ABC$, sei d'accordo? E dato che l'area del triangolo è $("base"*"altezza")$, possiamo calcolare l'area e dividere per la base (che è nota...vero?) per ottenere l'altezza.
Per calcolare l'area di un triangolo piano in uno spazio tridimensionale la cosa migliore è passare dal prodotto vettore. Ne parlammo tempo fa qui: https://www.matematicamente.it/forum/pos ... tml#280952
Quello che mi viene in mente è fare un discorso geometrico. La distanza che ti serve è infatti l'altezza del triangolo $ABC$, sei d'accordo? E dato che l'area del triangolo è $("base"*"altezza")$, possiamo calcolare l'area e dividere per la base (che è nota...vero?) per ottenere l'altezza.
Per calcolare l'area di un triangolo piano in uno spazio tridimensionale la cosa migliore è passare dal prodotto vettore. Ne parlammo tempo fa qui: https://www.matematicamente.it/forum/pos ... tml#280952
Grazie per la risposta tempestiva.
Il metodo che mi hai appena proposto è esattamente quello che sto usando in questo momento. La cosa che non ho evitato di riportare nel post precedente è che devo implementare questo algoritmo in un programma e il metodo è computazionalmente pesante (calcolare molte distanze implica fare molte radici) e speravo (è solo una speranza) che il metodo da me richiesto fosse leggermente più leggero.
Il metodo delle distanze punto-retta è computazionalmente più pesante? Potresti riportarmi i passi principali?
Grazie ancora.
Il metodo che mi hai appena proposto è esattamente quello che sto usando in questo momento. La cosa che non ho evitato di riportare nel post precedente è che devo implementare questo algoritmo in un programma e il metodo è computazionalmente pesante (calcolare molte distanze implica fare molte radici) e speravo (è solo una speranza) che il metodo da me richiesto fosse leggermente più leggero.
Il metodo delle distanze punto-retta è computazionalmente più pesante? Potresti riportarmi i passi principali?
Grazie ancora.
Beh guarda da un punto di vista computazionale (assolutamente non il mio forte) questo di trovare la distanza di un punto da una retta mi pare un classico problema di minimi quadrati. Sicuramente quindi è un problema codificato per il quale c'è una soluzione ottimale, magari qualcuno più ferrato di me in Analisi Numerica è in grado di trovarla.
@ dissonance: nel tuo post precedente hai scritto che la base per il triangolo è $"base"*"altezza"$ ma ovviamente manca la divisione per $2$...
Ma si può ovviamente considerare il parallelogramma definito dai due vettori $B - A$ e $C - A$ e la formula viene corretta. Il prodotto vettoriale non esiste in 2D. Ma è possibile definire quello che viene chiamato perp (dot) product in inglese per fare la stessa cosa. In effetti si tratta semplicemente del termine lungo $z$ del prodotto vettoriale e si interpreta come il prodotto scalare per il vettore perpendicolare. Tutti gli altri metodi che conosco richiedono un maggior numero di calcoli e quindi secondo me è il migliore.
Ma si può ovviamente considerare il parallelogramma definito dai due vettori $B - A$ e $C - A$ e la formula viene corretta. Il prodotto vettoriale non esiste in 2D. Ma è possibile definire quello che viene chiamato perp (dot) product in inglese per fare la stessa cosa. In effetti si tratta semplicemente del termine lungo $z$ del prodotto vettoriale e si interpreta come il prodotto scalare per il vettore perpendicolare. Tutti gli altri metodi che conosco richiedono un maggior numero di calcoli e quindi secondo me è il migliore.
Si si mi sono scordato la divisione per 2. Classico errore da scuola elementare. 
Comunque l'ambito di Xeno è il 3d. Quindi il problema del prodotto vettore non si pone.
Il punto è che il calcolo del prodotto vettore richiede 6 moltiplicazioni, a cui poi aggiungere altre 3 moltiplicazioni e una estrazione di radice per calcolarne la lunghezza. Infine bisogna dividere il risultato ottenuto per $1/2*"base"$ e sono altre 2 moltiplicazioni. Totale: 11 moltiplicazioni e una estrazione di radice.
Domanda: si può risolvere il problema facendo meno calcoli? In particolare, si riesce a bypassare quell'estrazione di radice?
Comunque l'ambito di Xeno è il 3d. Quindi il problema del prodotto vettore non si pone.
Il punto è che il calcolo del prodotto vettore richiede 6 moltiplicazioni, a cui poi aggiungere altre 3 moltiplicazioni e una estrazione di radice per calcolarne la lunghezza. Infine bisogna dividere il risultato ottenuto per $1/2*"base"$ e sono altre 2 moltiplicazioni. Totale: 11 moltiplicazioni e una estrazione di radice.
Domanda: si può risolvere il problema facendo meno calcoli? In particolare, si riesce a bypassare quell'estrazione di radice?
Avevo letto velocemente e non avevo visto che stava lavorando in 3D. Ma non è necessario dividere un per $1/2$ della base. Puoi infatti lavorare direttamente con il parallelepipedo (invece che con il triangolo) e quindi si deve semplicemente dividere per la base il prodotto vettoriale tra $B - A$ e $C - A$. Nota che per trovare la base ($|B - A|$) è necessario calcolare un'altra lunghezza... Quindi il numero di operazioni è superiore a quello che hai scritto... In formule il metodo è il seguente
$v = B - A$
$w = C - A$
$dist = |vxxw|/|w|$
Il numero totale di operazioni è 2 radici quadrate, 1 divisione, 12 moltiplicazioni, 4 addizioni e 9 sottrazioni.
Un altro metodo che mi viene in mente è quello di calcolarsi la proiezione del punto sulla retta e quindi la distanza tra il punto e la proiezione. Questo metodo ha tra l'altro il vantaggio di valere in qualsiasi dimensione (anche se non è sempre il metodo migliore per farlo). In formule viene il seguente:
$v = B - A$
$w = C - A$
$dist = |w - (v*w)/(v*v) v|$
In questo caso dovrebbero quindi essere necessari: 1 radice quadrata, 1 divisione, 12 moltiplicazioni, 6 addizioni e 9 sottrazioni. È quindi migliore in questo caso.
$v = B - A$
$w = C - A$
$dist = |vxxw|/|w|$
Il numero totale di operazioni è 2 radici quadrate, 1 divisione, 12 moltiplicazioni, 4 addizioni e 9 sottrazioni.
Un altro metodo che mi viene in mente è quello di calcolarsi la proiezione del punto sulla retta e quindi la distanza tra il punto e la proiezione. Questo metodo ha tra l'altro il vantaggio di valere in qualsiasi dimensione (anche se non è sempre il metodo migliore per farlo). In formule viene il seguente:
$v = B - A$
$w = C - A$
$dist = |w - (v*w)/(v*v) v|$
In questo caso dovrebbero quindi essere necessari: 1 radice quadrata, 1 divisione, 12 moltiplicazioni, 6 addizioni e 9 sottrazioni. È quindi migliore in questo caso.
@ apatriarca: La versione corretta del metodo basato sul prodotto vettore è quella che proponi tu.
Stavo pensando che, tra l'altro, questo metodo non è poi così male se usiamo un piccolo accorgimento.
Riprendendo le tue notazioni, quindi, il metodo consiste in questi passi:
1) $v:=B-A$, $w:=C-A$;
2) $"dist"=(|vxxw|)/(|v|)$ (*).
Nel 2) invece di calcolare direttamente $"dist"$ potremmo calcolare $"dist"^2=(|vxxw|)^2/(|v|)^2$ che non richiede estrazioni di radice. Se poi Xeno non si accontenta della distanza al quadrato (dipende dallo scopo del suo programma, magari la distanza al quadrato va bene lo stesso) calcoliamo $"dist"$ come radice quadrata di $"dist"^2$. In questa maniera c'è una sola estrazione di radice e il metodo del prodotto vettore torna ad essere migliore. Che ne dite?
_________________________________________
(*) @apatriarca: al denominatore, secondo me, va $|v|$. mi sbaglio?
Stavo pensando che, tra l'altro, questo metodo non è poi così male se usiamo un piccolo accorgimento.
Riprendendo le tue notazioni, quindi, il metodo consiste in questi passi:
1) $v:=B-A$, $w:=C-A$;
2) $"dist"=(|vxxw|)/(|v|)$ (*).
Nel 2) invece di calcolare direttamente $"dist"$ potremmo calcolare $"dist"^2=(|vxxw|)^2/(|v|)^2$ che non richiede estrazioni di radice. Se poi Xeno non si accontenta della distanza al quadrato (dipende dallo scopo del suo programma, magari la distanza al quadrato va bene lo stesso) calcoliamo $"dist"$ come radice quadrata di $"dist"^2$. In questa maniera c'è una sola estrazione di radice e il metodo del prodotto vettore torna ad essere migliore. Che ne dite?
_________________________________________
(*) @apatriarca: al denominatore, secondo me, va $|v|$. mi sbaglio?
Sì, mi sembra una buona idea.
@ Xeno: cosa stai cercando di fare? Tutti questi metodi hanno complessità costante e quindi non dovrebbero incidere molto sulle performance della tua applicazione (visto che comunque il numero di operazioni coinvolte non è poi tanto alto) a meno di eseguirlo un enorme numero di volte. Ma in questo caso è allora più conveniente concentrare i propri sforzi per diminuire il numero di volte in cui il metodo viene applicato, rispetto all'ottimizzare questo metodo.
@ Xeno: cosa stai cercando di fare? Tutti questi metodi hanno complessità costante e quindi non dovrebbero incidere molto sulle performance della tua applicazione (visto che comunque il numero di operazioni coinvolte non è poi tanto alto) a meno di eseguirlo un enorme numero di volte. Ma in questo caso è allora più conveniente concentrare i propri sforzi per diminuire il numero di volte in cui il metodo viene applicato, rispetto all'ottimizzare questo metodo.
Innanzi tutto, grazie per i consigli.
E' difficile spiegare cosa sto facendo... mi limito a dire che devo trovare un'euristica basata sulle distanze. Questo calcolo viene eseguito 100 volte al secondo (+ mooooolti altri calcoli) per ogni punto di ogni spazio 3d. Il frame rate dell'applicazione deve essere 100 fps, ergo non va diminuito. Chiaramente il collo di bottiglia è altrove, però è bene ottimizzare un po' tutto.
Computazionalmente parlando, l'unica cosa che dà noia è la radice quadrata. Potrei effettivamente prendere le distanze al quadrato, come suggerito da dissonance, ma forse dovrei rivedere l'euristica... Il fatto è che mi serve una funzione che decada esponenzialmente con la distanza. La soluzione è chiaramente una iperbole, il cui esponziale dipende, in qualceh modo, dalla distanza. Se la distanza divenza il suo quadrato, non vorrei che la faunzione decada troppo velocemente.
E' difficile spiegare cosa sto facendo... mi limito a dire che devo trovare un'euristica basata sulle distanze. Questo calcolo viene eseguito 100 volte al secondo (+ mooooolti altri calcoli) per ogni punto di ogni spazio 3d. Il frame rate dell'applicazione deve essere 100 fps, ergo non va diminuito. Chiaramente il collo di bottiglia è altrove, però è bene ottimizzare un po' tutto.
Computazionalmente parlando, l'unica cosa che dà noia è la radice quadrata. Potrei effettivamente prendere le distanze al quadrato, come suggerito da dissonance, ma forse dovrei rivedere l'euristica... Il fatto è che mi serve una funzione che decada esponenzialmente con la distanza. La soluzione è chiaramente una iperbole, il cui esponziale dipende, in qualceh modo, dalla distanza. Se la distanza divenza il suo quadrato, non vorrei che la faunzione decada troppo velocemente.
Per cosa devi utilizzare questa euristica? Sono sempre convinto che il modo migliore per aumentare le performance sia quella di usare strutture dati o algoritmi che facciano diminuire la complessità del tuo algoritmo. Non credo che la radice quadrata sia comunque un enorme problema (hai provato ad usare un profiler per vedere quanto incide sulla tua applicazione?), ma non vedo grossi problemi nell'uso della distanza al quadrato.
Sì, certo, la radice è il male minore, ma come ho già detto preferivo usarne il meno possibile... Poco male, funziona anche così. Grazie mille per tutti!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo