ヘクトのメモ

なんとなくいろいろ書いていくと思います．

複素数演算による幾何ライブラリの実装

この記事はMCC Advent Calendar 2016 15日目の記事です．ICPC向けの複素数演算による幾何ライブラリの実装について話します．
MCC Advent Calendar 2016 - Adventar
遅れてすいません...

背景

ICPCでは幾何の問題が出てきます．
ただし，ICPCでは電子的な事前準備の禁止と標準ライブラリしか使えない制約があります．
このため，標準ライブラリ縛りで幾何に必要な関数を一から実装する必要があります．
しかし，事前準備なしで幾何に必要な関数を実装するのは大変なことであり，多くのチームは紙媒体でライブラリを用意していると思います．
幾何に必要な関数を一から実装するとコード量も膨大になりがちです．
そこで，複素数演算を活用することで実装量を減らすことができます．
(ただし，2D限定です．あと，事実だけを淡々と書いていきます．)

ベクトル

2次元のベクトルを複素数と考えます．
\displaystyle \vec{a}=[a_x,a_y] \rightarrow a=a_x+ia_y
そうすると，ベクトル \displaystyle \vec{a} と \displaystyle \vec{b}の内積と外積は次の式で表される．
\displaystyle \vec{a} \cdot \vec{b} = \Re(\overline{a} b)
\displaystyle \vec{a} \times \vec{b} = \Im(\overline{a} b)

この手のテクニックは以下の記事とかで知りました．(他にも有益情報があります)
複素数と平面幾何 - 純粋関数型雑記帳

射影

点\displaystyle \vec{s}と点\displaystyle \vec{t}を結ぶ直線に対して，点\displaystyle \vec{p}の射影 \displaystyle \text{proj}( \vec{s},\vec{t},\vec{p})
\displaystyle \text{proj}(\vec{s},\vec{t},\vec{p})=(1-u)s+ut
\displaystyle u=\Re(\frac{p}{l})

より詳しい説明はこのサイトを見ると良さそう．
正射影ベクトルの公式の証明と使い方 | 高校数学の美しい物語

初めて知ったのは，notさんのツイートだった気がするけど，見つけられず...

線分の交差判定

点\displaystyle \vec{a_s}と点\displaystyle \vec{a_t}を結ぶ線分aと点\displaystyle \vec{b_s}と点\displaystyle \vec{b_t}を結ぶ線分bの交差判定 (線分の端点と線分では交差しないと判断)

\displaystyle \left( (\vec{a_t}-\vec{a_s}) \cdot (\vec{b_s}-\vec{a_s}) \right) \left( (\vec{a_t}-\vec{a_s}) \cdot (\vec{b_t}-\vec{a_s}) \right) < 0
\displaystyle \left( (\vec{b_t}-\vec{b_s}) \cdot (\vec{a_s}-\vec{b_s}) \right) \left( (\vec{b_t}-\vec{b_s}) \cdot (\vec{a_t}-\vec{b_s}) \right) < 0

直線の交点

点\displaystyle \vec{a_s}と点\displaystyle \vec{a_t}を結ぶ直線aと点\displaystyle \vec{b_s}と点\displaystyle \vec{b_t}を結ぶ直線bの交点 \displaystyle \text{cross}(\vec{a_s},\vec{a_t},\vec{b_s},\vec{b_t})
\displaystyle \text{cross}(\vec{a_s},\vec{a_t},\vec{b_s},\vec{b_t})=(1-u)a_s+ua_t
\displaystyle u=\frac{ (\vec{b_s}-\vec{a_s}) \cdot (\vec{b_t}-\vec{a_s})}{ (\vec{a_t}-\vec{a_s}) \cdot (\vec{b_t}-\vec{b_s})}

点が多角形の内部にあるかの判定

自分はWinding Number Algorithmを使っています．
詳細はこちら
【第2回】点の多角形に対する内外判定 ｜【公式】NTTPC

利点

  • 自己交差を持つ多角形(競プロにあまり出ないけど)も正しく判定できる．
  • 内積と外積の符号と座標の大小比較だけで書けるので誤差に強い．
  • 短く書ける．(自分の実装は10行くらい)

まとめ

とりあえず，いくつか書いてみました．
途中までしか書いていないので，おそらく加筆修正される予定です．