Verificare posizione di un punto rispetto a circumcerchio e circumsfera

L'idea alla base dell'algoritmo per il calcolo della triangolazione di Delaunay (vista in [1]) può essere sfruttata per verificare (in 2D) se un punto $D$ è interno, esterno o appartiene al cerchio circoscritto al triangolo individuato da tre punti $A$, $B$ e $C$.

In quel caso era necessario proiettare i punti del piano sul paraboloide $z = x^2 + y^2$, creare l'involucro convesso in 3D e proiettare le facce inferiori di quest'ultimo sul piano. Facendo passare un piano intersecante i tre punti di una faccia inferiore qualsiasi dell'involucro convesso, il risultato è un ellisse sul paraboloide che verrà proiettata come una circonferenza sul piano, si veda figura sotto, a sinistra. Guardando, invece, la figura a destra, si nota che i punti del paraboloide sotto il piano intersecante verranno proiettati nella circonferenza, quelli che si trovano all'intersezione tra paraboloide e piano intersecante verranno proiettati sulla circonferenza e, infine, quelli che si trovano sopra il piano intersecante verranno proiettati al di fuori della circonferenza.

Per stabilire quindi la posizione di un punto $D$, nel piano, rispetto al cerchio circoscritto del triangolo individuato da tre punti $A$, $B$ e $C$, si può usare quanto visto in [2] riguardo la verifica di complanarità in 3D. A tale scopo, infatti, stabilita l'orientazione dei tre punti $A$, $B$ e $C$, non resta che valutare il segno del volume del tetraedro individuato da $A$, $B$, $C$ e $D$.
Assumendo un orientazione antioraria di $A$, $B$ e $C$, se il volume è nullo $D$ giace sul piano intersecante e quindi verrà proiettato sulla circonferenza. Se il volume è positivo, invece, $D$ è al di sopra del piano intersecante e quindi verrà proiettato al di fuori della circonferenza. Se, infine, il volume è negativo, $D$ è al di sotto del piano intersecante e quindi verrà proiettato all'interno della circonferenza. Assumendo, al contrario, orientazione oraria i risultati di volume positivo e negativo sono invertiti. Il calcolo del volume si può valutare tramite il determinante della matrice che ha per elementi le coordinate dei punti (per maggiori dettagli si veda [2]). Dato che, in questo caso, si tratta dei punti proiettati sul paraboloide il determinante diventa

\[\begin{vmatrix} x_a & y_a & x_a^2 + y_a^2 & 1\\ x_b & y_b & x_b^2 + y_b^2 & 1\\ x_c & y_c & x_c^2 + y_c^2 & 1\\ x_d & y_d & x_d^2 + y_d^2 & 1 \\ \end{vmatrix} = \begin{vmatrix} x_b - x_a & y_b - y_a & (x_b - x_a)^2 + (y_b - y_a)^2\\ x_c - x_a & y_c - y_a & (x_c - x_a)^2 + (y_c - y_a)^2\\ x_d - x_a & y_d - y_a & (x_d - x_a)^2 + (y_d - y_a)^2\\ \end{vmatrix}\]
Per la sua valutazione si può semplicemente sviluppare il determinate, come visto in [2], sostituendo opportunamente le coordinate $z$ (vedi \eqref{eq:1} sotto).

\begin{equation}\label{eq:1}(x_d - x_a) [(y_b - y_a)((x_c - x_a)^2 + (y_c - y_a)^2) - (y_c - y_a)((x_b - x_a)^2 + (y_b - y_a)^2)] + \\ (y_d - y_a) [(x_c - x_a)((x_b - x_a)^2 + (y_b - y_a)^2) - (x_b - x_a)((x_c - x_a)^2 + (y_c - y_a)^2)] + \\ ((x_d - x_a)^2 + (y_d - y_a)^2) [(x_b - x_a)(y_c - y_a) - (x_c - x_a)(y_b - y_a) = 0\end{equation}
Oppure si può sfruttare quanto visto in [3] per il calcolo del determinante di una matrice $4 \times 4$.
L'aspetto interessante è che tutto questo può essere utilizzato anche in dimensioni superiori. Se ad esempio si è interessati a valutare la posizione di un punto $E$, nello spazio 3D, rispetto alla sfera circoscritta al tetraedro individuato dai punti $A$, $B$, $C$ e $D$ si considereranno i punti proiettati sull'iperparaboloide $w = x^2 + y^2 + z^2$ e per questo il determinante diventa

\[\begin{vmatrix} x_a & y_a & z_a & x_a^2 + y_a^2 + z_a^2& 1\\ x_b & y_b & z_b & x_b^2 + y_b^2 + z_b^2 & 1\\ x_c & y_c & z_c & x_c^2 + y_c^2 + z_c^2 & 1\\ x_d & y_d & z_d & x_d^2 + y_d^2 + z_d^2 & 1\\ x_e & y_e & z_e & x_e^2 + y_e^2 + z_e^2 & 1 \\ \end{vmatrix} = \begin{vmatrix} x_b - x_a & y_b - y_a & z_b - z_a & (x_b - x_a)^2 + (y_b - y_a)^2 + (z_b - z_a)^2\\ x_c - x_a & y_c - y_a & z_c - z_a & (x_c - x_a)^2 + (y_c - y_a)^2 + (z_c - z_a)^2\\ x_d - x_a & y_d - y_a & z_d - z_a & (x_d - x_a)^2 + (y_d - y_a)^2 + (z_d - z_a)^2\\ x_e - x_a & y_e - y_a & z_e - z_a & (x_e - x_a)^2 + (y_e - y_a)^2 + (z_e - z_a)^2 \\ \end{vmatrix}\]


Riferimenti
[1] Convex Hull in 3D
[2] Collinearità e Complanarità in 3D
[3] Matrice inversa in Computer Graphics