performance - N個の球の間の交点を決定します

Question

N個の球の交点を決定するための（速度と精度の観点から）最良のアプローチを知りたいだけです（ここでは2つの球が求められました）。これを行うのに最適な言語を知りたいと思いました。私がやりたいことについてのより詳細な説明はここにあります。

Answer 1

私が知る限り、あなたはN3D球の各ペアの交差軌跡を求めています。対称性を数えると、N *（N-1）/2ペアがあります。

だから、各ペアを取ります。中心間の距離がそれらの半径の合計よりも大きい場合、交差はありません。（編集：または、@ Benが指摘しているように、距離が半径の差よりも小さい場合、交差もありません。）

等しい場合、交点は単一の点であり、中心間の線分で簡単に見つかります。それより少ない場合、軌跡は点ではなく円になります。

その円の中心とその半径を見つけるには、2つの球を通る平面スライスを取得する必要があります。これにより、2つの円の交点を見つける問題が軽減されます。そのためには余弦定理が必要です。

手の込んだ：そのウィキペディアの図を見てください。aとbは2つの球の半径であり、cは中心間の距離です。最後から2番目の方程式を使用して、cos（alpha）を解きます。それから、 sin（alpha）を簡単に取得できます。次に、b sin（alpha）は円の半径であり、b cos（alpha）はその中心までの距離です。（注-これはtrig関数を呼び出さず、sqrtのみを呼び出します。）

交差する円の中心と半径がわかれば、円自体は球の中心を結ぶ線分に垂直な平面内にあります。

それを超えて、私はあなたが何を望んでいるのか本当にわかりません。

Answer 2

私があなたを正しく理解するなら、あなたはN個の球のグループから少なくとも2つの球のすべての交差点が欲しいですよね？

もしそうなら、少なくとも正確なソリューションが必要な場合は、これはハイパフォーマンスコンピューティングにとって実際には簡単な問題ではありません。この問題は、分子の「縮小表面」を計算するときにも解決されます。

http://www.ncbi.nlm.nih.gov/pubmed/8906967

これらの点と円を効率的に計算する方法についてはいくつかの出版物がありますが、それは簡単な作業ではありません。CUDAでこれらの値を計算する出版物があったと思いますが、詳細は覚えていません。Google（Scholar）は、この方向であなたを助けることができるはずです。

ただし、達成したいことによっては、より簡単な解決策がある場合があります。それで、おそらくあなたはあなたの質問を詳述することができますか？