Vicinanza punto-segmento

In diversi problemi è necessario conoscere la distanza tra un punto $\mathbf {p}$ e una polilinea formata da molteplici segmenti. Il peso computazionale di questo problema cresce linearmente con il numero di punti con cui è formata la retta: per poter eseguire queste analisi è necessario che il confronto con il singolo punto sia pertanto molto veloce.

In questa sezione verrà definito come segmento come quella parte di retta limitata tra i punti $\mathbf{a}$ e $\mathbf{b}$. Il punto $\mathbf {p}$ e il segmento possono relazionarsi in 3 modi: il punto più vicino è $\mathbf{a}$, il punto più vicino è $\mathbf{b}$ o il punto più vicino è un punto compreso tra i due estremi. Da un punto di vista prettamente computazionale calcolare queste 3 distanze richiederebbe 9 moltiplicazioni, 6 somme e una divisione, oltre ai necessari 3 confronti. Questa sezione mostra come si può migliorare computazionalmente il confronto facendo uso del prodotto scalare.

Senza perdita di generalità si può supporre che $\mathbf{a}=(0,0)^{\top}$. Dalla definizione di prodotto scalare

$$\mathbf{p} \cdot \mathbf{b} = \cos \alpha \Vert \mathbf{p} \Vert \Vert \mathbf{b} \Vert$$ (1.34)

e della lunghezza della proiezione ortogonale di $\mathbf {p}$ su $\mathbf{b}$

$$\cos \alpha \Vert \mathbf{p} \Vert = \frac { \mathbf{p} \cdot \mathbf{b} } { \Vert \mathbf{b} \Vert }$$ (1.35)

è possibile calcolare la distanza punto-segmento in maniera più efficiente. Il punto più vicino a $\mathbf {p}$ è $\mathbf{a}$ se e solo se $\alpha > \pi/2$ ovvero $\mathbf{p} \cdot \mathbf{b} <0$, mentre il punto più vicino è $\mathbf{b}$ se e solo se la proiezione di $\mathbf {p}$ su $\mathbf{b}$ è maggiore di $\Vert\mathbf{b}\Vert$ ovvero $\mathbf{p} \cdot \mathbf{b} > \Vert \mathbf{b} \Vert^2$. In questo caso per ottenere la sola informazione della vicinanza bastano 4 moltiplicazioni e 2 somme. Se e solo se il punto vicino risulta interno si potrà procedere con la tradizionale distanza punto-retta.