凹むこともある多角形（２）

１．凸多角形

多角形には凸多角形と凹多角形とがある。多角形の面積を求めるときは、三角形に分解してぞれぞれの面積を求め、最後に、それらの総和を求め、これを多角形の面積とする。しかし、凹多角形の場合には、間違ったアルゴリズムを利用すると、多角形の内側ではなく外側の三角形を求めてしまう。残念なことに、この様にならないアルゴリズムを考えようとすると、必要以上に神経を使う。そこで、凹多角形のままで問題を解くことをあきらめ、凹んでいるところで、多角形を分割し、凸多角形の集まりとして考えると、色々な問題は易しくなる。
そこで、ここでは、与えられた多角形が凸多角形であるかどうかを判定するプログラムを考えてみることにする。多角形を反時計回りに回ると次の頂点は左手の方向に出てくる。例えば、三頂点\(v_1=(x_1,y_1),v_2=(x_2,y_2),v_3=(x_3,y_3)\)が隣り合っていたとする。今、\(v_1\)から\(v_2\)へ進んでいるとし、多角形の周りを反時計回りに回っているとすると、\(v_3\)は左手見える。
これの判定は次のように行うことができる。\(v_1\)を原点に移動し、辺\(v_1, v_2\)を\(x\)軸と重なるように回転する。但し、\(v_2\)は\(x\)軸の右側に位置させる。この時、\(v_3\)が左手にあるのであれば、\(v_3\)の移動・回転後の頂点\(v'_3=(x'_3,y'_3)\)は\(x\)軸よりは上、即ち、\(y'_3>)\)となる。\(v'_3\)は以下の式により求めることができる。
\[
\left(
\begin{array}{c}
x'_3 \\
y'_3
\end{array}
\right)
=
\left(
\begin{array}{cc}
\cos \theta & \sin \theta \\
-\sin \theta & \cos \theta
\end{array}
\right)
\times
\left(
\begin{array}{c}
x_3 - x_1 \\
y_3 - y_1
\end{array}
\right)
\]

ここで、\(\cos \theta = \frac {x_2 – x_1}{l}\), \(\sin \theta = \frac {y_2 – y_1}{l}\)、また、\(l\)は辺\(v_1,v_2\)の長さである。

２．判定プログラム

凸多角形かどうかを判定するプログラムは次のようになる。まず、最初に、次の頂点が左側にあるかどうかを判定する関数leftsideは、上述した式を用いて次のようになる。

    leftside :: Vertex -> Vertex -> Vertex -> Bool
    leftside (x1,y1) (x2,y2) (x3,y3)
      | y > 0     = True
      | otherwise = False
      where
        cos = (x2 - x1) / sideLength (x2,y2) (x1,y1)
        sin = (y2 - y1) / sideLength (x2,y2) (x1,y1)
        y = (x3 - x1) * (- sin) + (y3 - y1) * cos

次に、それぞれの頂点に対して、それが手前の辺の左側にあるかどうかを判定する関数directionは次のようになる。なお、この判定においては、各頂点は先行する辺を必要とする。そこで、多角形を表す頂点列に対して、先頭に最後の頂点を、最後に最初の頂点をつけ、その頂点列を基に判定する。その時の関数はdirection’である。

    direction :: Polygon -> [Bool]
    direction poly
      | length poly < 0 = []
      | otherwise       = direction' $ (last poly) : poly ++ [head poly]
      where
        direction' :: [Vertex] -> [Bool]
        direction' (v1:v2:v3:[]) = [leftside v1 v2 v3]
        direction' (v1:v2:v3:vs) = leftside v1 v2 v3 : direction' (v2:v3:vs)

最終判定は次の関数convexで行う。反時計回りで、全ての頂点が左手にあるときは、Trueのリストが返されるので、その時は、Trueで戻るようにする。また、もしかすると、頂点の列が時計回りで入力されているかもしれない。この時は、頂点の列を逆順にしてやり、これまでと同じ判定を行い、Trueであるとき、凸多角形となる。これ以外の時は、凸多角形ではないということになる。

convex :: Polygon -> Bool
convex poly = (foldl (&&) True $ direction poly) || 
              (foldl (&&) True $ direction $ reverse poly)

今までのプログラムを一つにまとめると、以下のようになる。

convex :: Polygon -> Bool
convex poly = (foldl (&&) True $ direction poly) || 
              (foldl (&&) True $ direction $ reverse poly)
  where
    direction :: Polygon -> [Bool]
    direction poly
      | length poly < 0 = []
      | otherwise       = direction' $ (last poly) : poly ++ [head poly]
      where
        direction' :: [Vertex] -> [Bool]
        direction' (v1:v2:v3:[]) = [leftside v1 v2 v3]
        direction' (v1:v2:v3:vs) = leftside v1 v2 v3 : direction' (v2:v3:vs)
    leftside :: Vertex -> Vertex -> Vertex -> Bool
    leftside (x1,y1) (x2,y2) (x3,y3)
      | y > 0     = True
      | otherwise = False
      where
        cos = (x2 - x1) / sideLength (x2,y2) (x1,y1)
        sin = (y2 - y1) / sideLength (x2,y2) (x1,y1)
        y = (x3 - x1) * (- sin) + (y3 - y1) * cos

前回と比較すると、ちょっと大変でした。