ギフト包装法(凸包アルゴリズム)|Excel VBAで学ぶ数学とアルゴリズム

今回は凸包とつほうアルゴリズムの「ギフト包装法」について解説していきます。
凸包アルゴリズムはいろいろな種類がありますが、ギフト包装法は最も単純で理解しやすいアルゴリズムです。その分、他の凸包アルゴリズムに比べて処理時間は多くかかってしまいますが、これから凸包アルゴリズムを理解し始めるという場合にはうってつけのアルゴリズムといってもいいです。

本ページではこの「ギフト包装法」のアルゴリズムがどういった仕組みなのかを解説し、Excel VBAのコードとして実装していきます。

こういったアルゴリズムはPythonやC++などのがっつりしたプログラム言語では紹介されていることがあります。これは実際にその言語で使われるというのもそうですが、プログラムのコードとして見ることでアルゴリズムの中身をより深く理解することができるためです。

ここではそういった”がっつりとしたプログラミング言語”ではないVBAを使うことで、幅広い方に向けてギフト包装法のアルゴリズムの内容をご紹介していきます。

 

凸包アルゴリズムとは

凸包(Convex Hull)とは

凸包とは「与えられた点をすべてを包含する最小の凸多角形」のことをいいます。
文字の説明だけだとイメージしづらいかもしれませんが下画像のように2次元上にある複数の点に対して、輪ゴムをかけたときにできるような形状が凸包の形状です。

凸包はパターン認識・画像処理・統計学・地理情報システム・抽象解釈による静的コード解析などの幅広い分野で利用がされています。
 

凸包アルゴリズム

凸包アルゴリズムとはその名の通りで、凸包を求めるアルゴリズムです。
点集合を入力した場合に、その凸包頂点を求めるアルゴリズムで、代表的なものは下記の通りです。

・ギフト包装法       処理時間:nh
・グラハムスキャン 処理時間:n log n
・クイックハル   処理時間:n log n
(※処理時間表記 入力する点の数:n , 凸包頂点数:h とする)

どれも凸包を求めるまでの過程や処理時間は違いますが、基本的には最終出力は同じです。
※各アルゴリズムの利用可能な次元の範囲は違いますが、ここではすべて2次元のみで考えます。

以下では処理時間はかかりますが最も理解しやすく処理内容が単純な「ギフト包装法」のアルゴリズムをVBAコードを使って紹介していきます。

 

ギフト包装法

ギフト包装法のアルゴリズムはいたって単純で下記の処理を行います。

① Y座標が最も小さい点を基準点として取得
 (※最小Y座標が一致する点が複数ある場合は、その中でもX座標が最も小さい点を取得)
② 選んだ1点から別の点に直線を結び他のすべての点がその直線の片側に来るような点を見つける
③ ②の処理を基準点が再び選ばれるまで繰り返す

 

Animation depicting the gift wrapping algorithm.gif ©Maonus (Licensed under CC BY 4.0)

処理のイメージとしては上のgif画像の通りで、はじめに凸包頂点となる1点(基準点)を取得し、その他のすべての点を網羅的に確認して“基準点の次にある最も左側の点”を取得。取得した点を新たな基準点として設定し、再び同じ処理を行っていきます。
(※判定の”側”が常に一定であるのであれば”最も右側の点”でも求めることができます)

ここでいう“基準点の次にある最も左側の点”は外積を求めることで判定することができます。

たとえば上画像の点Aを基準点とした時、ベクトルABとベクトルACの外積を求めることで、下記の通り点Cが直線ABに対して左側にあるか、右側にあるかを判定することが出来ます

・ベクトルABとベクトルACの外積が0より大きい場合、点Cは直線ABに対して左側にある
・ベクトルABとベクトルACの外積が0より小さい場合、点Cは直線ABに対して右側にある

上画像の場合は点Cが直線ABより右側にあることからもわかる通りで、ベクトルABとベクトルACの外積が0より小さい場合です。

外積は点座標から求めることができるので、この考えを使って常に最も左側(もしくは最も右側)の点を順に取得していけば、最終的に初めの点に戻ってきて凸包が導き出せるという訳です。

これは少し考え方を変えてみると、下図のように点集合を一定方向に回転させながら凸包を導き出しているというふうにも考えることもできます。このとき、まるでギフト(贈り物)を包装しているように見えることから、このアルゴリズムは「ギフト包装法」と呼ばれています。

 

サンプルコード

ギフト包装法をVBAコードで書くと下記の通りです。
Excel VBAでの実装ということでShapeオブジェクトの「円」を点として扱います
上画像(左側)のような点集合を入力すると上画像(右側)のような凸包のエッジを直線で作成します。

 
icon-code 円を作るのが面倒な場合

円をいちいち作成するのは面倒だと思うので下記コードを利用してください。
「RandomCircle」を実行すれば指定した範囲内に指定した個数だけ円をランダムで作成することができます。(最上部の定数の値を書き換えることで作成範囲や個数を変更することができます)

 

まとめ

今回は凸包アルゴリズムの「ギフト包装法」の解説でした。

① Y座標が最も小さい点を基準点として取得
 (※最小Y座標が一致する点が複数ある場合は、その中でもX座標が最も小さい点を取得)
② 選んだ1点から別の点に直線を結び他の全ての点がその直線の片側に来るような点を見つける
③ ②の処理を基準点が再び選ばれるまで繰り返す

ギフト包装法は凸包アルゴリズムの中で最も単純で理解しやすい処理内容です。
しかし網羅的に処理を行っているため無駄が多く、効率はあまり良いとはいえません。

では、どういう処理にしたら処理が高速化できるでしょうか?
その謎はギフト包装法を少し進化させたアルゴリズムの「グラハムスキャン」や「クイックハル」の中身を理解すればおのずと分かってくるので、ぜひこれらのアルゴリズムも勉強してみて下さい。

 
 icon-book オススメ書籍

2022年9月3日Excel, VBA, アルゴリズム, 数学

Posted by Lic