Area Separation 解説

アルゴリズムの概略

「与えられた線分によって領域が何分割されるか」を求める計算幾何の典型的な問題です。

問題をよく読むと， 「距離が 10-10 未満の 2 点は一致するとみなしてよい。 また、|PQ| < 10-10、|QR| < 10-10 でかつ |PR| >= 10-10となるような交点の組 P、Q、R は存在しない。」 という条件が書いてあります。 これらは実数値の計算誤差の対処について書かれているのですが，後半の部分が重要です。 後半は「3つの交点P, Q, Rが存在するならば，計算誤差によってP = Q, Q = Rが成り立つのにP != Rであるということはない」と言っています。 まぁ，確かにそれだと計算誤差で困るよね……ではなくて，これは「この問題を解くアルゴリズムには交点計算が必要です」と言っています。 交点計算が必要なければこんな一文は要らないのです。 このように「アルゴリズムのヒントが問題文に書かれている」ことは多いので，問題文は注意深く読むようにしましょう。

上のヒントから察するに，この問題を解くアルゴリズムでは「交点計算が必要」で， かつ「同じ場所に交点が3つ以上存在することもある（そしてそれが答えに影響する）」ということが分かります。 つまり，「線分の交差判定」を使って解く問題なのです。

では，実際にアルゴリズムを説明していきましょう。 まず，初めは分割された領域数は 1 つです。 線を引くと，どのように引いたとしても，領域数は 1 つ増えて 2 になります。

もう一本引いてみましょう。

普通に引くとどうやら領域数は 1 ずつ増えていくようです。 今度は線が交わるように引いてみましょう。

領域数が 2 つ増えました。 もともと線が通ると領域が二分割されて領域数が 1 増えるのですが， 線を一つ跨ぐことでもう一つ別の領域も二分割されて領域数がさらに 1 増えることになります。 ですから，次のように線を3つ跨げば領域数は4つ増えます。

以上より，一つの線を引いた場合，「増加する領域数 = 交差する線分数 + 1」となります。

しかし，次のように線を引いた場合は上の等式が成り立ちません。

この赤色の線は2つの線分と交差していますが，領域数の増加は 3 ではなく 2 になっています。 それも当然といえば当然で，跨いでいるのは一箇所だけだからです。 このように，既にその場所に交点が存在している場合，重複して数えない（最初の一度しか数えない）ようにする必要があります。 先ほどのように等式で書けば「増加する領域数 = 交差する線分数 - 重複交点数 + 1」です。

注意点として，次のような交点を持つ場合は「交差している」と判断してはいけません。

正方形領域の枠上で交差する場合は交差していないと判定する必要があります。 このような例を忘れるといつまで経っても正解にならないので気をつけてください。

アルゴリズムの計算量

各線を引いていくループ O(n) があって，その中では既に引いている全ての線との交点計算を行うループを回すので， そのループ部分の計算量は O(n2) です。 交点計算自体は線形時間で（つまり O(1) で）できます。 交点の重複を判定するために，今までとの交点との比較のループを回すのでさらに O(n) が増えます。 結局，全体としての計算量のオーダーは O(n3) となります。 n = 100 なので n3 = 1,000,000 = 1M と計算量は問題ありません。

アルゴリズムの実装

この線分の交差判定＋交点計算には，「線分の交差判定と交点計算をまじめに行う」方法と「直線の交点計算で簡単に済ませる」方法の2種類があります。 線分は色々なパターンがあって交差判定や交点計算は面倒になります。 しかし，直線は平行でなければ必ず交わり，交点計算も（外積を求める部分を除けば）1行で簡潔に書けます。 詳しい解説は「平面幾何におけるベクトル演算」を参照してください。

ここでは，直線の交点計算をしておいて，その交点が正方形領域の内か外かを判定する方が楽に実装できます （解答ソースコード p0019-deq.cpp はそのように書いています）。 ただし，どちらにしろ線分の場合も直線の場合も両方使うので，両方書けるようになっておきましょう。 印刷物の持ち込みはありなので，本番は幾何ライブラリ（平面幾何におけるベクトル演算）を印刷して持ち込んでおくとよいでしょう。

毎度のことですが，計算誤差の取り扱いには気をつけてください。 それから，2つのベクトルa,bが等しいかどうかは abs(a-b) < EPS と簡潔に書けますが， 絶対値を取っている，つまり sqrt を毎回やっていて非常に遅いので比較回数の多いループの中で使用することは避けましょう。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $