Punti dentro triangoli e quadrilateri

Si consideri il problema di verificare se un punto è all'interno di poligoni relativamente semplici come i triangoli o i quadrilateri. La trattazione del caso di poligono generico è più complessa e viene lasciata al lettore (e opzionalmente riconducibile al caso triangolo/quadrilatero).

Nel caso di triangoli e quadrilateri gli approcci che saranno mostrati risultano molto efficienti nel caso in cui sia necessario eseguire confronti tra un singolo poligono verso un numero elevato di punti in quanto tali tecniche permettono l'utilizzo di precalcoli: l'idea base infatti è quella di sfruttare una trasformazione dello spazio delle coordinate del poligono in uno spazio dove risulti più facile eseguire il confronto.

Per esempio, un parallelogramma formato da due vettori generatori può sempre essere trasformato in un quadrato unitario $(0,0)-(1,1)$ attraverso una trasformazione affine $\mathbf{p} \mapsto \left( X, Y \right)$. Un punto $\mathbf {p}$ cade all'interno del parallelogramma se $0<X(\mathbf{p})<1$ e $0<Y(\mathbf{p})<1$. La stessa trasformazione vale anche per i triangoli formati dagli stessi vettori generatori, con però il confronto $0<X(\mathbf{p})<1$ e $0<Y(\mathbf{p})<1-X(\mathbf{p})$. Per valutare se un punto cade all'interno del parallelogramma sono necessarie appena 4 moltiplicazioni e 6 somme. Il costo di creazione della trasformazione affine è più elevato ma se il numero di confronti è alto tale peso, costante, risulta trascurabile.

Per trasformare quadrilateri generici in un quadrato unitario $(0,0)-(1,1)$ si deve usare invece la trasformazione omografica (si veda la sezione 1.10). A scapito di un costo iniziale elevato di creazione della trasformazione, il controllo se un punto appartiene o meno alla figura geometrica è relativamente semplice

$$\begin{array}{l} 0<h_0 p_x + h_1 p_y + h_2 < h_6 p_x + h_7 p... ...3 p_x + h_4 p_y + h_5 < h_6 p_x + h_7 p_y + h_8 \\ \end{array}$$ (1.86)

limitato pertanto a 6 moltiplicazioni, 6 somme e 4 confronti.