幾何のテストケースの作り方

これはCompetitive Programming Advent Calendar 2014に投稿された記事です。

ICPCではいる君に幾何は任せていたので担当ではないのですが、JAGに入ってからは何故か高頻度で幾何の担当になってしまっています。幾何のプロがJAGに入ってもう当たらんだろうと思ったら、この前のICPC模擬地区予選も幾何が2問あって結局データセットを作ってました。
というわけで今まで作ってきたテストケースの手法を書いていきます。

2次元幾何の場合

最低限、コーナーケースや誤差死を防ぐための制約などの洗い出しは事前にやっておきましょう。
generatorを作るのが難しい場合は問題自体を少し変えるのも有りです。例えば、流れ星に願いをでは、当初は最後の星が消える時間のみを出力する予定だったのですが、1つのテストケースで落とせる確率が無駄に減るので、星が消える時間を全て出力するようにしました。

ランダムに作る

点の位置くらいしかない場合はランダム生成でもある程度機能します。この時ランダムの分布をいじって偏りのあるケースなども作っておくと良いです。例えば、平行な線分がコーナーケースの場合はそういったものが多く出るようにします。もしくは、誤答を先に作っておいて誤答になるケースが出るまで生成するというのもありです。
注意点としては、問題によっては生成した入力が、幾何でよくある「EPS以下の距離には〜が無い」といった制約に引っかかる場合があります。そういった制約に引っかかる場合はgeneratorの中でvalidatorを動かして、そういった入力があったら再生成してしまいましょう。あまり適当にやっているとgeneratorが無限ループにおちいる場合もあるので、一旦小さいサイズで生成し、validatorが通ったらサイズを徐々に大きくするなどもありです。

人力で作る

ランダムだけではまともなケースを作るのが厳しい、例えば自己交差の無い多角形とかグラフ要素が混ざってくる場合などです。個別のテストケースを1つずつプログラムを書いて作るのは大変すぎるので、手で作ってしまうのが楽です。
私はdiaというダイアグラム作成ツールでテストケースを作成しています。diaで線分、多角形、折れ線などベクター画像を書き、svgで出力し、C++でパースして問題の入力に変換してます。多角形の頂点の追加などが面倒ですが、100頂点くらいの物ならこれで作れると思います。

色も付けれますし、コピペもできるのでこんくらいのテストケースならすぐに作れます。ただし、入力サイズが大きかったり、数値をちゃんと計算しないと作れないコーナーケース等を作るのは難しいので、プログラムを書いて生成するのと併用する必要があります。

ビジュアライズする

手入力で作った方は既にあるので良いのですが、ランダム生成したものは本当に意図した入力になっているか画像で確認しておきたいです。やり方は人それぞれだと思いますが、私はsvg形式で出力してます(こんな感じ)。利点は標準のファイル形式なのでブラウザやubuntuのフォルダから画像が普通に見れることです。ちゃんと書けばアニメーションもいけると思いますが、そこまでやってないです。

3次元幾何の場合

頑張ってください。
人力でやるのはかなり無理があるので、プログラムを書くしか無いと思います。
テクニックとしては、z=0の入力を作る際は2次元と同じ方法が使えます。縮退した入力はどっちみち必要になるので、2次元で落とせる解答は2次元で落としましょう。3次元の入力が弱くてもなんとかなるかもしれません。
また、ランダムな正規直交基底(平面)を作りたい場合はランダムなベクトルe_1,vを作ってe_3=e_1 \times ve_2=e_1 \times e_3外積を2回かけるとできます。

ビジュアライズする

ply形式で保存すると楽です。ply形式は下のような感じのtxtファイルで、ちゃんとヘッダーを書けばポリゴンも扱えます。

ply
format ascii 1.0
element vertex 2000 
property float x
property float y
property float z
property uchar diffuse_red
property uchar diffuse_green
property uchar diffuse_blue
end_header
1.122748 2.322027 2.471454 255 0 0
1.125541 2.323361 2.465986 255 0 0
1.128307 2.324675 2.460499 255 0 0
1.131045 2.325967 2.454994 255 0 0
1.133755 2.327239 2.449470 255 0 0
1.136438 2.328489 2.443927 255 0 0
1.139093 2.329717 2.438367 255 0 0
...

ply形式はMeshLab等で見ることが可能です。以下はRingsのデータです。

まとめ

というわけでこんな感じで幾何のテストケースを作ってきました。幾何はやる事が多くて時間がかかる上にめんどくさいので早めに取りかからないと死にます。
あと、やる気のある人はJAGに入って作っていただけるとありがたいです。

担当した幾何問題一覧

最終防衛問題は解けないので担当してません(あと最近ないし)
テストケースを作った問題

解答のみ