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

１．多角形の面積を求める

多角形が凸多角形であるときは、その面積を求めることは簡単である。例えば、多角形の頂点の列が\(v_1, v_2, v_3,..,v_n\)であるとき、\(v_1\)から\(v_3\)へ、さらに\(v_1\)から\(v_4\)へ、同じように\(v_1\)から\(v_{n-1}\)まで、線分を引くと、多角形は、三角形に分割される。
三角形の面積は、各辺の長さを\(a,b,c\)、また、\(s = \frac {a+b+c}{2} \)としたとき、\( \sqrt {s \times (s-a) \times (s-b) \times (s-c)}\)で求めることができる。これを用いるとプログラムは次のようになる。

area :: Polygon -> Area
area poly
  | length poly < 3 = 0
  | convex poly     = area' poly
  | otherwise       = error "The polygon is concave. This case is not supported yet."
  where
    area' (v1:v2:v3:[]) = sqrt $ 
      s * (s - a) *
          (s - b) *
          (s - c)
      where
        a = sideLength v1 v2
        b = sideLength v2 v3
        c = sideLength v3 v1
        s = (a + b + c) / 2
    area' (v1:v2:v3:vs) = area' (v1:v2:v3:[]) + area' (v1:v3:vs)

２．頂点の角度を求める

隣接する頂点\(v_1=(x_1,y_1), v_2=(x_2,y_2), v_3=(x_3,y_3)\)において、\(v_2\)にできる角度は\(\cos \theta = \frac{(x_1 – x_2) \times (x_3 – x_2) + (y_1 – y_2) \times (y_3 – y_2)}{l_1 \times l_2}\)から求めることができる。ここで、\(l_2,l_2\)はそれぞれ辺\(v_1,v_2\)と辺\(v_3,v_2\)の長さである。これを利用すると、各頂点の角度は次のように求めることができる。

serAngle :: Polygon -> [Angle]
serAngle poly
  | length poly < 3 = []
  | convex poly     = serAngle' $ (last poly) : poly ++ [head poly]
  | otherwise       = error "The polygon is concave. This case is not supported yet."
  where
    serAngle' :: [Vertex] -> [Angle]
    serAngle' (v1:v2:v3:[]) = [angle v1 v2 v3]
    serAngle' (v1:v2:v3:vs) = angle v1 v2 v3 : serAngle' (v2:v3:vs)
    angle :: Vertex -> Vertex -> Vertex -> Angle
    angle v1 v2 v3 = (acos $ (inner v1 v2 v3)/ (sideLength v1 v2) / (sideLength v3 v2)) / pi * 180
      where
        inner :: Vertex -> Vertex -> Vertex -> Double
        inner (x1,y1) (x2,y2) (x3,y3) = ((x1 - x2) * (x3 - x2) + (y1 - y2) * (y3 - y2))

３．課題

凹多角形を凸多角形に分割しなさい。

４．課題

凹多角形の面積を求めなさい。

５．課題

凹多角形の各頂点の角度を求めなさい。

６．課題

点\(x\)が凸多角形の内部にあるかどうか判定しなさい。多角形を反時計回りに回った時、常に、左側に\(x\)があれば、内部にあることになる。また、そうでなければ、内部にはないことになる。これは、多角形が凸多角形であるかどうかを判定したプログラムを少し改良すると簡単に作成することができる。しかし、これはディスプレイ上に表示するときに重要である。ディスプレイ上では、多角形を塗りつぶして表示するだろうから、画面上の各点が、多角形の内部に含まれているかどうかの判定が必要となる。従って、この判定は、論理の世界から、ディスプレイでの表示という現実の世界への投影となる。