四角形の頂点の座標から四角形の面積を得る

三角形(頂点を A, B, C とし、その対辺の長さをそれぞれ a, b, c とする)の面積を求める方法には、次のものが知られている。

  • (底辺)×(高さ)÷2
  • (1/2)ab sinC
  • ヘロンの公式(Heron's formula): √(s(s-a)(s-b)(s-c)), ただし, s=(a+b+c)/2

では、これを四角形に拡張できないものかと考えていたが、すでにブレートシュナイダーの公式(Bretschneider's formula)が存在することが知られている(ブラーマグプタの公式(Brahmagupta's formula)では四角形が円に内接するという条件が必要であるためプログラムには適さない)。四角形(頂点を順にA, B, C, D とし, AB=p, BC=q, CD=r, DA=s)に対応するブレートシュナイダーの公式は次のとおりである。

√((T-p)(T-q)(T-r)(T-s)-pqrscos2((A+C)/2))), ただし, T=(p+q+r+s)/2

ただし、今回の場合は頂点の座標から p, q, r, s, ∠A, ∠C を導出する必要がある.よって, 与えられた頂点の座標を四角形の頂点の順番に並べ替えなければならない.

いろんな方法を模索している中で、次の記述を発見した。

  1. x座標が小さい順番に並べ、それぞれの点を P1, P2, P3, P4 とする.
    • P1y<P2yのとき
      • P3y>P3yとなるように
        P3, P4を入れ替える.
    • P1y>P2yのとき
      • P3y<P3yとなるように
        P3, P4を入れ替える.

一見してよさそうに見えるが, ∠P3が平角よりも大きくなる場合はうまくいかない. それどころか,
P2P3を入れ替えてもなお四角形となる場合があることに気づいてしまった.
なので, 座標だけを与えられても凹四角形の場合はうまくいかないことが判明した...

よって、頂点の座標から四角形の面積を計算する場合は、次のような設計を考えなければならない.

  • 入力者は頂点の座標を四角形の頂点の順序となるように入力する.
  • 面積を算出する側は与えられた頂点座標から四角形が描けることを確認してから角度と辺の長さを計算しブレートシュナイダーの公式を適用する.

ということで、現在、面積を算出する側は与えられた頂点座標から四角形が描けることを確認する手段を思索中である.
おそらく, 内角の和が 2π になることは四角形であることの必要十分条件であることをいえばいいはずなのだが...

順序付けて与えられた4点がこの順に四角形の頂点となる必要十分条件は, やはり内角の和が 360° に等しいことでいいようだ.
この命題を満たさない場合は8の字を描くように線分を引くことになるため, 線が交わった部分の対頂角の分だけ 360° に足りなくなる.

しかし, ここからさらに大変なのは, 優角 (始点を同じくする2本の半直線のなす角が 180° 超過である方の角度) と劣角 (始点を同じくする2本の半直線のなす角が 180° 未満である方の角度) のどちらが内角になるのかを判定するのかということだ.

いうまでもなく, 平角や周角なら四角形をなさないので考えなくてもよい.

凸四角形なら劣角しか存在しないので大した問題にならない.
問題は, 凹四角形の場合だ. その場合は優角が必ず1つ存在する.

そこで, ベクトルで考えてみた. AB ベクトル, AD ベクトル, AC ベクトルを考える.
AB ベクトルと AD ベクトルが一次従属であれば, ∠A は平角か周角なので,
A, B, C, D はこの順に四角形の頂点の組とはならない.

そうでない場合はベクトル ACAB ベクトルと AD ベクトル の線形和で表現できる.
すなわち, AC = u AB + v AD である.

このときの u, v の値に着目すればよいのではないかと考えた.

  1. u>0 かつ v>0 ならば ∠A は劣角
  2. u<0 かつ v<0 ならば ∠A は優角
  3. uv が異符号かつ u+v>1 ならば ∠A は劣角
  4. いずれにも当てはまらなければ, そもそも各点 A, B, C, D がこの順に四角形の頂点をなすことはない.

この考えで問題ないことがわかった.
しかし, 多角形に拡張するとなると, この手法には限界がある.
ベクトルの分野には外積の考えがあり, これを用いると簡潔に表現できることがわかった.

そこで, この件を
与えられた点を頂点とする多角形の面積という文書にまとめてみた.

コメントを残す