algorithm - 3Dフラットポリゴン間の交差

Question

2つ（またはそれ以上）の3D平面ポリゴン間の交差を見つける方法（最も単純なケースでは、それらはすべて凸状です）？交線がある場合はそれを提供できるアルゴリズムを探しています。無限平面-平面の場合に提案された方法は有用ではないことに注意してください。

Answer 1

2つのケースがあります：

両方のポリゴンは同じ平面上にあります。

最初のポリゴンへのすべての内部ポイントを見つけます。

最初のポリゴンを任意に取得し、2番目のポリゴンのすべての頂点をループして、それらが最初のポリゴンの内側にあるか外側にあるかを判断します。凸多角形の場合、これを行うのは簡単です。ここを参照してください。

2つのポリゴン間の交点を見つけます

交点を見つけるには、一方のポリゴンの各エッジを取得し、もう一方のポリゴンのすべてのエッジをループして、それらがどこかで交差するかどうかを確認します。これは、2本の線の交点の式を使用して見つけることができます。

交差する領域は、内部の点と交差する点の頂点で形成されるポリゴンです。

2つのポリゴンは異なる平面上にあります。

2番目のポリゴンと最初のポリゴンの平面との交点を見つけます。これを行うには、2番目のポリゴンの各エッジを検討し、エッジと最初のポリゴンの平面との交点を見つけます。これは、線と平面の交点の式を使用して見つけることができます。

見つけた交点が最初のポリゴンの内側にあるか外側にあるかを確認します。

Answer 2

これが1つの方法です。1つのポリゴンをXY平面に回転させることで、3Dの問題を（ほとんどの場合）2Dの問題に減らすことができます。通常、パフォーマンスの問題はそれほど多くありません。

1. 最初のポリゴンのポイントを回転して、XY平面上に配置します。
2. 2番目のポリゴンのポイントを最初のポリゴンと同じ方向と量だけ回転させます。
3. 2番目のポリゴンの各線をチェックし、XY平面と交差するかどうかとどこで交差するかを確認します。凸多角形の場合、これはポイントAとBで2回発生するはずです。
4. 線ABと最初のポリゴンのエッジとのすべての交点を見つけます。最初のポリゴンが凸面の場合は、0、1、または2つの交差が必要です。
5. ケース：交差点がゼロ：線ABは、最初のポリゴンの完全に内側または外側にあります。内側の場合、ABは平面の交差線です。外の場合、交差点はありません。
6. ケース：1つの交差点、点C：AまたはBのいずれかが最初の平面の内側にあります。平面の交線は、Cへの内側の点（AまたはB）です。
7. ケース：2つの交差点：平面の交差線はABです。
8. 交差する線を元の位置に回転させます。これは、手順1で行った回転の逆です。

この方法を非凸多角形に拡張することは、読者の練習問題として残されています。:)（実際にはかなり簡単です。）

ポイントが2Dポリゴンの内側にあるかどうかを確認する1つの方法は、そのポイントから上に向かってポリゴンのすべてのエッジとの線の交点を取得することです。0または2：外。1：中。（これは、外側と内側に偶数と奇数を使用する非凸多角形でも機能します。）

Answer 3

両方のポリゴンが同一平面上にある場合、少なくともこの特定の場合の解決策は次のとおりです。

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

アルゴリズムを示す素敵なアプレットもあります。