Polygonal Line Search 解説

この問題には解法が2種類あります。 一つは,問題通りに図形を回転させて照合する方法です。 もう一つは,与えられた点列から「各線の長さと向き(右左どちらに曲がったか)」という情報を抽出し,それを照合する方法です。

図形の回転

アルゴリズムの概略

問題によると,1) 平行移動,2) 回転,3) 逆からチェック,の3種類の操作で同じと判定されるものが同一な図形です。 平行移動は単に両方とも原点に移動すればOKです。 各線分はx軸かy軸に沿ってしか動かないので,回転は90度単位で行えばよく,4種類あります。 逆からチェックは,順方向と逆方向の2種類を判定する必要があるということです。 なので,結局 1 * 4 * 2 = 8 通りを調べる必要があります。

アルゴリズムとしては素直で,照合元の図形を「90度回転して正方向と逆方向でチェック」を4回繰り返せば, 与えられた図形が同一かどうか判定できます。

アルゴリズムの計算量

それぞれの図形の判定に必要な計算量は線形時間(オーダーが定数)なので,計算量は問題ありません。 正確には,折れ線の本数nが 1 < n < 50 で折れ線を構成する頂点数mが 3 < m < 10 なので O(n×m) の計算量です。 具体的には n=50, m=10 で8通りの調べ方があるのでだいたい 50×10×8 = 4,000 くらいの計算量で一つのデータセットに解答できます。

アルゴリズムの実装

素直にコーディングすればOKです。 回転はそのまま元のデータを書き換えてしまってOKですし,さらにその状態で同一が分かった場合にループを抜けてしまっても, 次のデータに対しては最大4回転するので問題ありません。

解答ソースコード (2684-deq_1.cpp) では C++ STL の complex テンプレートを使うことで回転を楽に書いています。 complexを使うと複素数平面上での計算が行えるので,虚数 i を掛ければ反時計回りに90度回転できます。

回転を手でコーディングする場合は,時計回りの90度回転であれば

x = y
y = -x

となります。この程度であればcomplexを使わなくても簡単ですね。

線の長さと向き

アルゴリズムの概略

問題としてはxy平面上の座標として各点の列が与えられていますが,これをあらかじめ「各線分の長さと向き」に置き換えておくと, 照合判定時には平行移動や回転移動を無視することができます。 向きは必ず90度変わるので,「右に曲がった or 左に曲がった」という情報を覚えておけばOKです (最初の線分だけは曲がっていないのでその状態も要ります)。

逆からのチェックはこのアルゴリズムでも必要です。 逆からの場合,「右に曲がった」ということは「左に曲がった」と等しくなります。

アルゴリズムの計算量

基本的には一つ目の「図形の回転」アルゴリズムと一緒で O(n×m) になります。 回転が不要なので「図形の回転」アルゴリズムの 1/4 の計算量になるはずですが, 最初に「各線分の長さと向き」に変換する計算が必要になるので実際は 1/3 か 1/2 くらいでしょう。

アルゴリズムの実装

「右に曲がった」と「左に曲がった」場合の値は符号を逆にしておくと楽になります。 例えば,右=1,そのまま=0,左=-1としておくと,逆からのチェック時に -1 をかければよくなります。

曲がる方向は一つ前の線分の向きに依存します。 言い換えれば,3点の情報があってはじめて右に曲がったか左に曲がったかが分かります。 前の線分が曲がった方向(上下左右)と今回の線分が動いた方向(上下左右)から曲がった方向(左向きor右向き)が分かるので, 最大16通りの表を作る必要がありそうです。 ただし,前回上下(y軸方向)に動いた場合は今回は必ず左右(x軸方向)に動くので,実際は8通りの表になります。 例えば「上→右」なら右向きなので1,「上→左」なら左向きなので-1,という感じです。

この問題においては,本質的な情報を抽出してモデル化する「線の長さと向き」アルゴリズムよりも, 単純な「図形の回転」アルゴリズムの方が問題をすばやく解ける感じがします。

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