うまくいけば、次の問題で私を助けることができる計算幾何学の人々がここにいます-
私が3空間で自由に動くボールを取り、その周りに通行不能な座標のセットSc（つまり、拡散するボールの一部が重ならない3空間のポイント）を定義することによって「ケージ」を作成することを想像してください。これらの点は、V（ケージ）>> V（ボール）である、より大きな球のボリュームV（ケージ）内にあります。
通行不能な座標のセットScが提供された場合、ボールがケージから逃げることができるかどうかを判断するための計算効率の高い、および/または優れた方法はありますか？
MathOverflowの以前の投稿をご覧ください-https ://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of- impassib
ボールの半径がRだとします。MathOverflow の友人が指摘しているように、この問題は、通過できない点を半径Rの球に置き換え、球を点Pに置き換えることと同じです。問題は、Pがボールで密閉された部屋にいるかどうかです。
この質問に答えるには、ボールの結合を計算してから、この結合の表面Sを取得する必要があります。PがSのコンポーネントのいずれかの内部にある場合、トラップされます。そうでない場合、エスケープできます。
ボールの結合を計算するための十分に確立されたアルゴリズムは、少なくともEdelsBrunner によるこの論文にさかのぼります。そのアルゴリズムを理解して実装するにはかなりの学習曲線がありますが、幸いなことに CGAL ライブラリに実装されています。
CGAL がスキンを計算したら、スキンの接続されたコンポーネント (すべてが閉じたメッシュである必要があります) を見て、Pがそれらの中にあるかどうかを確認できます (サポートが必要な場合は、叫んでください)。
テッセレーションされたスキンは実際の球面の近似であるため、精度の問題があるかどうかを尋ねる場合があります。メッシュ フェースは実際には元のボールの内側にあると予想されます。また、Pが元々すべてのボールの外側にあると仮定すると、 Pがいずれかのスキン コンポーネントの内側にあるかどうかを確認すると、正確な結果が得られると思います。