La soluzione per il caso 3-d può essere trovata qui ; Mi piacerebbe avere la versione generalizzata. Non c'è una semplice generalizzazione dell'algoritmo di Mathworld poiché il prodotto incrociato è definito solo per le dimensioni 3 e 7, quindi capisco.
Se si utilizza l'algebra vettoriale (che è facile con una libreria algebrica vettoriale), non vi è alcuna reale differenza tra il caso 3-d e il caso N-d. Sfortunatamente, la pagina a cui ti colleghi ha scritto l'elemento matematico vettoriale per elemento, che tende a oscurarlo.
Quindi, parafrasando dall'articolo: data una linea attraverso due punti A e B , la distanza minima d a un punto P può essere calcolata come:
n_vector pa = P - A
n_vector ba = B - A
double t = dot(pa, ba)/dot(ba, ba)
double d = length(pa - t * ba)
Si noti che l'aggiunta di due% di% di% è come aggiungere un vettore a 3, tranne che si aggiungono N elementi corrispondenti invece di 3 di essi e ridimensionare un n_vector di% scalar% co_de è come ridimensionare un 3 -vettore tranne che riduci gli elementi N anziché 3.
Valutare il n_vector di un t è solo leggermente più complicato: sommi i quadrati di tutti gli elementi N (invece del solo 3) e prendi la length() del risultato. Infine, come avrai intuito, il prodotto n_vector è la somma dei prodotti degli elementi N corrispondenti (di nuovo, invece del solo 3).
Esprimi la linea in funzione di un singolo parametro t. Chiamalo X (t).
La distanza da un punto P a un punto sulla linea X (t0) è solo u (t) = || X (t0) - P ||, e in realtà non hai bisogno di fare la radice quadrata.
Ora trova il valore di t che minimizza u (t). Il metodo standard dal calcolo del primo semestre è quello di formare la derivata du / dt, impostarlo a zero e risolvere per t.
Se la linea è in realtà una linea retta, otterrai una soluzione. Se la linea è una curva, potresti ottenere molte soluzioni e dovrai esaminarle tutte per trovare il minimo effettivo.
L'algoritmo serve a minimizzare la distanza tra il punto e la linea.
La linea è un insieme di punti. Scrivi un'equazione per esprimere la distanza tra il punto dato e ogni punto della linea - sarà qualcosa come d = sqrt((a1 - b1)^2 + (a2-b2)^2 + ... + (an-bn)^2) .
Ora riduci l'equazione.
Piuttosto che implementare questo algoritmo da solo, suggerirei di trovare una libreria per equazioni lineari nella lingua scelta. Ho sentito parlare di JAMA (per Java), ma non ho mai avuto bisogno di farlo, quindi non l'ho studiato .
Leggi altre domande sui tag algorithms measurement