交差する三角形 (および一般に凸多角形) の問題は、特に関連するエッジの数に関して線形時間で解決したい場合は、見た目よりもはるかに困難です。
このページは、一般的な凸多角形の実用的なアルゴリズムのアイデアを持っていると考えることができます (アルゴリズムは、キャリパーの回転に基づいています。実際、特に幾何学的ハン・バナッハの定理の背後には、いくつかの抽象的な幾何学があります)。
凸状の交差ポリゴンを取得したら、面積を評価するのは簡単だと考えてください。
したがって、次の 2 つのオプションがあります。
問題を抽象化して(どういうわけか、三角形を凸多角形と見なすだけです)、 GPC ライブラリ(C で記述されています) を使用するか、たとえばブーストを使用して、C/C++ で高速なソリューションを実現できます。 :ジオメトリ.
あなたは三角形だけを専門としています。この場合、私のアドバイスは、 関連する交差の可能な方法をトポロジー的に詳しく説明し、ソリューションの効率的な実装を提供するこの素晴らしい論文を検討することです.
もう 1 つ言いたいことがあります。おもちゃの三角形(つまり、歪度が低く、サイズが機械の精度よりもはるかに大きい) に関する問題を考えると、独自のアルゴリズムを実装してそれで遊ぶことを考えることができます。しかし、1 秒間に何百万もの条件の悪い三角形と交差する必要がある場合は、優れた高速なライブラリに頼ったほうがよいでしょう。