【Processing】四面体の外接球を求める

成果物

www.youtube.com
前回のVoronoi図を3Dに拡張してみたいということで、Delaunay tetrahedralizationを作るために四面体の外接球を求めるプログラムを書いてみました。Delaunay tetrahedralizationって名前が尋常じゃないですね…

仕組み

外接球の中心座標と、半径は次の式で求めることができます。
$\begin{array}{l} u_{i} =v_{i} -v_{0}\\ l_{ij} はv_{i} とv_{j} の距離\\ l_{ij} =||v_{i} -v_{j} ||^{2} =( v_{i} -v_{j}) \cdot ( v_{i} -v_{j})\\ 外接円の中心\ O=\frac{v_{0} +l^{2}_{01}( u_{2} \times u_{3}) +l^{2}_{02}( u_{3} \times u_{1}) +l^{2}_{03}( u_{1} \times u_{2})}{2u_{1} \cdot ( u_{2} \times u_{3})}\\ 外接球の半径はOとv_{0} の距離\\ 外接球の半径\ R=l_{O0} \end{array}$
参考にしたサイト、外接円を使って求める方法も紹介されています。
geometry - Circumsphere of a tetrahedron - Mathematics Stack Exchange