Ruby/SDLで計算幾何(4) 点が多角形の中に内部にあるか判定する1

さて、『アルゴリズムC第二巻』ISBN:4764902567 p.185にある、点が多角形に包含されているか判定するコードを見ていきましょう。

判定したい点から無限遠(扱う領域の端)まで、一方向に線分を延ばします。ここではx軸正方向とします。

そして、その線分が多角形の辺、もしくは頂点と交差する回数を数え、その数が偶数なら多角形の外部、奇数なら多角形の内部、としたいのですが、これだけでは問題があるわけです。

上図の2点について、ともに延ばした線分が1辺と1頂点と交差しているので条件は同じはずなのですが、多角形の内部か外部かは異なっています。

辺については問題ないのですが、頂点については、その交わり方にはカウントしていいものといけないものがあります。ここでは上図のように、「横断的」「非横断的」と名付けておきます。*1「非横断的」な交差は交点としてカウントする必要はありませんので、その検出も必要です。

以上のことが意識された関数 inside (p.185) は以下です。ただ、自分なりにコーディングスタイルを変えたり、ちょこちょこコメントを付したりしています。*2

int inside (
    struct point t,   /* 点 */
    struct point p[], /* 多角形の頂点集合 */
    int          N    /* 多角形の頂点数 */
)
{
    int         i;
    int         count = 0;
    int         j = 0;
    struct line lt, lp;
    
    p[0] = p[N];
    p[N+1] = p[1];

    /* ltの設定 */
    lt.p1 = t;
    lt.p2 = t;
    lt.p2.x = INT_MAX;

    for (i = 1; i <= N; i++)
    {
        lp.p1 = p[i];
        lp.p2 = p[i];

        if (ccw(lt.p1, lt.p2, p[i]) != 0) /* p[i]がlt上に乗ってないとき */
        {
            if (i == j+1)
　　　　　　{
                lp.p2 = p[j];   /* p[i]p[j]は多角形の一辺 */
                if (intersect(lp, lt))
                    count++;
            }
            else
            {
                /* p[i]とp[j]の間の頂点が、すべてlt上に乗っている */
                /* 横断的か非横断的かを判定 */
                if (ccw(lt.p1, lt.p2, p[i]) * ccw(lt.p1, lt.p2, p[j]) < 0)
                    count++;
            }
            j = i;
        }
    }
    return count & 1;    /* 偶奇を返す */
}

現在これをRubyに書き換えてる最中なのですが･･･さらっと出来ないのが当方のオツムの至らないところでございまして･･･。

Array#injectが使えるのかな･･･。

続きはまた今度です。

*1:ちなみにこの用語は、自分が学生時代にかじっていた微分トポロジーの用語「横断的に交わる」intersect transversally からの連想で名付けました。http://en.wikipedia.org/wiki/Transversal_intersection

*2:また、多角形にもちょっと条件が必要になってくるらしいのですが、そこの分析も今度です。