２つの三角形が重なる部分の面積を求める

プログラミングのＴＡをしているときに話題に出た問題です。いろいろ考えて、やっと納得のいく結論が出ました。
二つの任意の三角形があります。この二つの三角形が重なったとき、重なった部分の面積はどのように求めたらいいかという問題です。
おそらく一番シンプルな解法はモンテカルロ法を用いることだと思います。まず、二つの三角形を囲む長方形を考えます。その長方形の横幅をwidth、縦幅をheightとし、左下の角を原点とした二次元座標系を考えます。そして、この長方形の中からある点をランダムサンプリングします。そしてこの点が二つの三角形の内部に含まれている場合の数を数え上げ、ランダムサンプリングした回数で割れば、長方形に対する重なる領域の面積の割合が求まります。

function commonArea( Triangle a, Triangle b ){
    count = 0;
    repeat(10000){
        x = random( 0 .. width );
        y = random( 0 .. height );
        if( a.include?(x,y) && b.include?(x,y) )
            count = count + 1;
    }
    return width * height * (count/10000);
}

ただ、モンテカルロ法は確かに便利なんですが…激しく負けた気がするので、代数的に解く方法などいろいろ考えてました。で、良い方法が思いつかなかったので、計算幾何学的に解いてみました。まだ検証をしてないので、正しく動作するかどうかは分かりませんが、大丈夫だと思います。
まず、二つの三角形の重なりは、次の形のいずれかになります。

重ならない
点
線分
三角形
四角形
五角形
６角形

しかも、これらの図形は全て凸な図形になります。なぜなら、三角形は凸な図形なので、その重なりも凸になるからです。なお、最初の三つは面積を持たないので考慮しません。
凸な図形の面積は、各頂点の座標が分かれば一意に求めることができます。ですから、重なりの面積を求めるには、その図形の頂点の座標を求めればいいことになります。
さて、その求め方ですが、任意の点の集合が与えられたとき、その点を全て包括する最小の凸図形を求める（包装問題）アルゴリズムの一つを変化させたものを考えました。
まず、二つの三角形の辺の交点の座標を求めます。この交点の集合と三角形の頂点の集合を全体の点の集合とします。そして、一番下にある点から３時方向から反時計回りに点を探索していきます。このとき、探索した点が二つの三角形の領域外にあれば無視して次の点を探索し、領域内にあれば選択します。次の点を探索するときは、一つ前の点からいまの点に向かう方向から反時計まわりで探索していきます。そして全ての点を調べつくしたとき、選択された点が二つの三角形が重なる図形になります。
また、点を選択するときに順序を持たせておけば、そのまま面積を求めることができます。
まだコード化して検証を行ってないので正しいか分かりませんが、これで二つの三角形の重なる面積を求めることができると思います。
なお、この解き方は三角形に限らず、任意の凸図形の重なる領域を求めることができると思います。３つ以上の図形の重なりも大丈夫でしょう、きっと。