私の目標は、ポリゴンの順序付けられていない頂点と平面の方程式が与えられた n 個の頂点を持つ 3D 平面ポリゴンの符号なし領域を見つけることです。ポイントが時計回りまたは反時計回りの順序でソートされたら、面積を計算するための効率的なアルゴリズムが既にあります (このサイトから: http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm#3D%20Polygons )
ポイントを並べ替えるためにGrahamのスキャンを実装することにしました.2Dの場合には多くの例がありますが、3Dの場合は多くありません. 私の最善の選択肢は、変換行列を使用して 3 次元の点を 2 次元に変換するか (これを行う方法がわかりません)、3 点が反時計回りのターンを形成するかどうかを判断する際に外積を使用して 3 次元で行うことです。後者の方がより効率的だと思います。ポイントを並べ替えると、各外積で見つかった面積を合計し、最終的な答えを計算できるからです。
ただし、Graham のスキャンを 3D で実装する方法はまだわかりません。また、頂点のセットが同一平面上にあり、それらすべてが凸包に含まれている必要があることを既に知っているという事実を利用できますか?
編集:さらに検討すると、ここでグラハムのスキャンを使用する必要さえありますか? すべてのポイントが船体に含まれていることは既にわかっているので、角度でソートするだけで十分ではないでしょうか? 最終的な目標は、面積を計算できるようにポイントを反時計回り/時計回りの順序にすることであり、それを達成するにはスキャンが必要だと思いました。