計算幾何(6)

計算幾何という学問自体の歴史は意外と浅いと思う。1972年にGrahamがかの有名な(?)「グラハム走査」アルゴリズムを発表して、1978年にShamosが博士論文「Computational Geometry」を発表し注目を浴びたころをその起源とする。

よってこの分野に対する古い教科書は内容がてんでない上に洗練されておらず往々にして内容が間違っている。そのありえないっぷりにただただ脱帽である。

さて、前回の問題で与えられた多角形が凸でない(ただしねじれてはいない)場合はどうなるだろうか。岩波のソフトウェア科学シリーズ10『グラフィックスとマンマシンシステム』を見てみよう。このソフトウェア科学シリーズは大学生の独習向きであり、なかなかの良書シリーズなのだが、残念なことにこの問題の解法として示されている2つの方法はどちらも不備がある。

示されている方法のうち一つは、もう一つは、半直線を引いて多角形との交点回数の偶奇で調べようというもの。「検査経路がどの頂点の近傍も通らないように選ぶことが重要である」と書いてあるが、その実装はそんなに単純とは言い難い。

もう一つの方法は、(��APi×APi+1)/ 2が 正か 0かで判定しようと言うもの。たぶん何かの積分と勘違いされたのだと思うが、この結果は点Aには依らず多角形の面積にしかならない。

余談ではあるが多角形の面積については、以前の日記のコメントに書いたが、以下のような方法がある。

# yaneurao 『直線と多角形への距離とか交差領域などについて延々と書いてある本『Geometric Tools for Computer Graphics』に面白い記述があったので紹介。

Area(P) = 1/2 �� XiYi+1 - Xi+1Yi (i=0,…,n-1) と導き出したあと、この�瑤良怍❹� �� Xi(Yi+1 - Yi-1) + �� (XiYi-1 - Xi+1Yi)と分離して、後者は X0Y-1 - XnYn-1 = 0となる。よって面積公式は以下のように単純化できる。

Area(P) = 1/2 ��Xi(Yi+1 - Yi-1) { i = 0,…,n-1 }

このFAQはUsenetのcomp.graphics.algorithmsでDan Sunday(2001)が投稿したが、以前 sci.mathにDave Rusin(1995)が投稿している。探せばもっと古いのがあるかも知れないとのこと。』