こんにちは。NUMです。
Processingで遊んでいると多角形を作りたくなることってありませんか？
vertex関数で座標を指定して多角形を作るのは結構手間になります。
任意の点集合から凸包を作成することができれば、色んなバリエーションの多角形を作る事ができます。
今回はGraham Scanと呼ばれる凸包を生成するアルゴリズムについて学んでいきます。
目次
概要
Graham Scanとは凸包を求めるアルゴリズムの一種です。
凸包とは与えられた点をすべて包含する最小の凸多角形（凸多面体）のことです。
釘を沢山打ち付けて、輪ゴムで一番外側を囲んでできた形をイメージすると分かりやすいですね。
図1
Graham Scanは点集合をx軸にソートして、順番に点を処理していきます。
ソート後の点を3つ取得し、右回りかどうかを判定していきます。
左回りの場合は取得した3つの点から中間の点（2つめの点）をリストから削除する処理を
点の数分だけ行っていきます。
最終的に残った点が凸包の頂点になります。
それでは具体的にアルゴリズムについて説明していきます。
アルゴリズム
アルゴリズムは大きく3つの処理に分類されます。
上部凸包（A,B,E,I,J,K）の作成
下部凸包（K,L,M,O,N,C,A）の作成
上部凸包と下部凸包の連結
図2
引数：x座標の昇順にソートされた点が格納されたリスト（以降はlistPと呼ぶ）
戻り値：凸包の頂点が格納されたリスト
■上部凸包の作成
listPの第1要素（点A）を取得
listPの第2要素（点B）を取得
上部凸包リスト（以降はupperListと呼ぶ）に1,2で取得した点を追加
listPの第3要素から最後の要素まで処理を繰り返す
点を取得し、upperListに追加
upperListの要素数が3つ以上かつupperListの最後から３つの点が反時計回りの場合処理を繰り返す
upperListの最後から2つ目の点を削除
upperListの最後から３つの点（n,n-1,n-2）を取得
■下部凸包の作成
listPの最後の要素（点K）を取得
listPの最後から2番目の要素（点L）を取得
下部凸包リスト（以降はlowerListと呼ぶ）に1,2で取得した点を追加
listPの最後から3番目の要素から第1要素まで処理を繰り返す
点を取得し、lowerListに追加
lowerListの要素数が3つ以上かつlowerListの最後から３つの点が反時計回りの場合処理を繰り返す
lowerListの最後から３つの点（n,n-1,n-2）を取得
lowerListの最後から2つ目の点を削除
lowerListの最後から３つの点（n,n-1,n-2）を取得（iiでlowerListのサイズが変わったため再度取得し直す）
■上部凸包と下部凸包の連結
上部凸包リスト（A,B,E,I,J,K）と下部凸包リスト（K,L,M,O,N,C,A）を連結
※点A,Kは上部凸包リストと下部凸包リストで重複しているため、被らないように処理する。
解説
x座標の昇順でソートされたリストの作成
Graham Scanはx座標の昇順でソートされたリストを元に処理を行なっていきます。
なのでソートを行わないといけないですが、今回はProcessingで用意されているIntDictのsortValuesメソッドを使用してソートをします。
ちなみにsortValueメソッドでソートされるのはKeyではなくValueです。
そのため点集合の座標をIntDict（Key：y座標 Value：x座標）で保持します。
注意点としてはGraham Scanはx座標の値が重複しないようにしておく事です。
x座標が重複すると3点が右回りか判定する時に意図した計算結果が得られないためです。
３点が右回りか判定
右回り判定はベクトル外積を使用します。
ベクトル外積：（予備ノリさんの動画が分かりやすいです。）
2つのベクトルaからベクトルbに対して、右ねじの方向に回転させた角で出来上がる平行四辺形の面積の値が平行四辺形に垂直方向（Z軸方向）に伸ばしたベクトルと同じ値になります。
Processingでは座標系が左手系のため、手前がZ座標の正となります。
外積の結果が正の場合、右回りとなります。
ベクトル外積の計算式はベクトルP2_P1(始線)×ベクトルP2_P3で表せます。
つまり、ベクトルP2_P3(始線)×ベクトルP2_P1のように始線が変わると、親指の方向が手前から奥に変わるため、計算結果がマイナスになり計算結果が変わる
3点が右回りかどうかはベクトルP2_P1×ベクトルP2_P3>0で（右ねじの親指の方向が手前）あれば良いということが分かります。
右回りの視覚的イメージとして、右回りはP1,P2,P3です。
始線がP2_P1となっている場合です。
左回りはP4,P5,P6です。始線がP5_P4となっている場合です。
図3
プログラム
以下はGraham Scanで使用するプログラムです。
grahamScan()
/**
* graham Scanメイン処理
* @param1 IntDict x座標の昇順にソートされた点集合の座標Dictionary
*/
ArrayList<PVector> grahamScan(IntDict id) {
ArrayList<PVector> upperList = createUpperList(id);//上部凸包リスト生成
ArrayList<PVector> lowerList = createLowerList(id);//下部凸包リスト生成
return combineUpperLowerList(upperList, lowerList);
}
createSortCoordinateDict()
/**
* 点集合の座標がx座標の昇順でソートされたDictionaryを作成
* @param1 int x座標の最小値 random関数の引数に使用
* @param2 int x座標の最大値 random関数の引数に使用
* @param3 int y座標の最小値 random関数の引数に使用
* @param4 int y座標の最大値 random関数の引数に使用
* @param5 int 点の数
*/
IntDict createSortCoordinateDict(int x1, int x2, int y1, int y2, int dictSize) {
IntDict coordinateDictKeyX = new IntDict();//Key:x座標 Value:y座標
IntDict coordinateDictKeyY = new IntDict();//Key:y座標 Value:x座標
//Key:x座標 Value:y座標のDictionaryを作成
for (int i = 0; i<dictSize; i++) {
int x = int(random(x1, x2));
int y = int(random(y1, y2));
String strX = str(x);
if (!coordinateDictKeyX.hasKey(strX)) {
coordinateDictKeyX.set(strX, y);
}
}
String[] keyArrayX = coordinateDictKeyX.keyArray();
//Key:y座標 Value:x座標のDictionaryを作成
for (String x : keyArrayX) {
String strY = str(coordinateDictKeyX.get(x));
if (!coordinateDictKeyY.hasKey(strY)) {
coordinateDictKeyY.set(strY, int(x));
}
}
//x座標の昇順にソート
coordinateDictKeyY.sortValues();
return coordinateDictKeyY;
}
createUpperList()
/**
* 上部凸包の作成
* @param1 IntDict x座標の昇順にソートされた点集合の座標Dictionary
*/
ArrayList<PVector> createUpperList(IntDict id) {
ArrayList<PVector> upperList = new ArrayList<PVector>();//上部凸包リスト
//Key:y座標 Value:x座標のDictionaryからKeyの配列を取得
String[] keyArrayX = id.keyArray();
int dictXArrSize = keyArrayX.length;//要素数取得
//最初の要素からPVectorオブジェクトを生成
PVector upperP1 = new PVector(id.get(keyArrayX[0]), int(keyArrayX[0]));
//2番目の要素からPVectorオブジェクトを生成
PVector upperP2 = new PVector(id.get(keyArrayX[1]), int(keyArrayX[1]));
//リストにPVectorオブジェクトを追加
upperList.add(upperP1);
upperList.add(upperP2);
//上部凸包リストの生成
//上部凸包リストの最後から3つの要素を時計回りか判定するため、iは2に設定している
for (int i = 2; i<dictXArrSize; i++) {
String Key = keyArrayX[i];
//Dictionaryのi番目の要素を取得し、PVectorオブジェクトを生成
int x = id.get(Key);
int y = int(Key);
PVector p = new PVector(x, y);
upperList.add(p);//上部凸包リストに追加
int upperListSize = upperList.size();//上部凸包リストのサイズ取得
//上部凸包リストの最後から3つの配列Indexを取得
int upperListLastIndex = upperListSize-1;
int upperListLast2Index = upperListLastIndex-1;
int upperListLast3Index = upperListLast2Index-1;
//上部凸包リストの最後から3つの要素を取得
PVector lastP = upperList.get(upperListLastIndex);
PVector last2P = upperList.get(upperListLast2Index);
PVector last3P = upperList.get(upperListLast3Index);
//上部凸包リストの最後から3つの要素が反時計回りの場合、リストから削除
while (upperListSize>=3 & checkRightTurn(last3P, last2P, lastP)) {
upperList.remove(upperListLast2Index);//削除
//削除後、再度最後から3つの要素を取得
upperListSize = upperList.size();
if (upperListSize>=3) {
upperListLastIndex = upperListSize-1;
upperListLast2Index = upperListLastIndex-1;
upperListLast3Index = upperListLast2Index-1;
lastP = upperList.get(upperListLastIndex);
last2P = upperList.get(upperListLast2Index);
last3P = upperList.get(upperListLast3Index);
}
}
}
return upperList;
}
createLowerList()
/**
* 下部凸包の作成
* @param1 IntDict x座標の昇順にソートされた点集合の座標Dictionary
*/
ArrayList<PVector> createLowerList(IntDict id) {
ArrayList<PVector> lowerList = new ArrayList<PVector>();//下部凸包リスト
//Key:y座標 Value:x座標のDictionaryからKeyの配列を取得
String[] dictXArr = id.keyArray();
int dictXArrSize = dictXArr.length;//要素数取得
//最初の要素からPVectorオブジェクトを生成
PVector lowerP1 = new PVector(id.get(dictXArr[dictXArrSize-1]), int(dictXArr[dictXArrSize-1]));
//2番目の要素からPVectorオブジェクトを生成
PVector lowerP2 = new PVector(id.get(dictXArr[dictXArrSize-2]), int(dictXArr[dictXArrSize-2]));
//リストにPVectorオブジェクトを追加
lowerList.add(lowerP1);
lowerList.add(lowerP2);
//下部凸包リストの生成
//下部凸包リストの最後から3つの要素を時計回りか判定するため、iは2に設定している
for (int i = dictXArrSize-3; i>=0; i--) {
String Key = dictXArr[i];
//Dictionaryのi番目の要素を取得し、PVectorオブジェクトを生成
int x = id.get(Key);
int y = int(Key);
PVector p = new PVector(x, y);
lowerList.add(p);//下部凸包リストに追加
int lowerListSize = lowerList.size();//下部凸包リストのサイズ取得
//下部凸包リストの最後から3つの配列Indexを取得
int lowerListLastIndex = lowerListSize-1;
int lowerListLast2Index = lowerListLastIndex-1;
int lowerListLast3Index = lowerListLast2Index-1;
//下部凸包リストの最後から3つの要素を取得
PVector lastP = lowerList.get(lowerListLastIndex);
PVector last2P = lowerList.get(lowerListLast2Index);
PVector last3P = lowerList.get(lowerListLast3Index);
//下部凸包リストの最後から3つの要素が反時計回りの場合、リストから削除
while (lowerListSize>=3 & checkRightTurn(last3P, last2P, lastP)) {
lowerList.remove(lowerListLast2Index);//削除
//削除後、再度最後から3つの要素を取得
lowerListSize = lowerList.size();
if (lowerListSize>=3) {
lowerListLastIndex = lowerListSize-1;
lowerListLast2Index = lowerListLastIndex-1;
lowerListLast3Index = lowerListLast2Index-1;
lastP = lowerList.get(lowerListLastIndex);
last2P = lowerList.get(lowerListLast2Index);
last3P = lowerList.get(lowerListLast3Index);
}
}
}
return lowerList;
}
checkRightTurn()
/**
* 3点のベクトルが右回りか判定
* @param1 PVector 点1
* @param2 PVector 点2
* @param3 PVector 点3
*/
boolean checkRightTurn(PVector p1, PVector p2, PVector p3) {
float cross = vectorAngleBetween(p1, p2, p3).z;//ベクトル外積の計算結果を取得
//ベクトル外積の計算結果が負の場合trueを返す
if (cross <= 0) {
return true;
} else {
return false;
}
}
vectorAngleBetween()
/**
* ベクトル外積
* @param1 PVector 点1
* @param2 PVector 点2
* @param3 PVector 点3
*/
PVector vectorAngleBetween(PVector p1, PVector p2, PVector p3) {
PVector p1_2 = new PVector(p2.x-p1.x, p2.y-p1.y);
PVector p2_3 = new PVector(p3.x-p2.x, p3.y-p2.y);
PVector crossP = p1_2.cross(p2_3);//ベクトル外積
return crossP;
}
combineUpperLowerList()
/**
* 上部凸包と下部凸包を連結する
* @param1 ArrayList<PVector> 上部凸包
* @param2 ArrayList<PVector> 下部凸包
*/
ArrayList<PVector> combineUpperLowerList(ArrayList<PVector> upperList, ArrayList<PVector> lowerList) {
//上部凸包リストと下部凸包リストを結合させたリスト
ArrayList<PVector> combineList = new ArrayList<PVector>();
//上部凸包リストの要素を結合リストに追加
for (PVector p : upperList) {
combineList.add(p);
}
//下部凸包リストの要素を結合リストに追加(最初と最後の要素は重複しているためi=1,i<lowerListSize-1としている)
int lowerListSize = lowerList.size();
for (int i = 1; i<lowerListSize-1; i++) {
PVector p = lowerList.get(i);
combineList.add(p);
}
return combineList;
}
drawConvexHull()
/**
* 凸包の描画
* @param1 ArrayList<PVector> 凸包の頂点座標が格納されたリスト
*/
void drawConvexHull(ArrayList<PVector> grahamScanList) {
beginShape();
for (PVector p : grahamScanList) {
vertex(p.x, p.y);
}
endShape(CLOSE);
}
drawPoint()
/**
* 指定色、影、光の色を配列に格納する
* @param1 color 色
*/
void drawPoint(IntDict id) {
String[] keyArrayY = id.keyArray();
for(String y : keyArrayY){
int x = id.get(y);
point(x,int(y));
}
}
setup()
void setup() {
size(850, 850);
background(0);
pixelDensity(displayDensity());
smooth();
int margin = 100;
int pointSize = 30;
IntDict id = createSortCoordinateDict(margin, width-margin, margin, height-margin, pointSize);
ArrayList<PVector> grahamScanList = grahamScan(id);
strokeWeight(5);
stroke(color(255,0,0));
noFill();
drawConvexHull(grahamScanList);
strokeWeight(15);
stroke(color(255,255,0));
drawPoint(id);
}
まとめ
以上がGraham Scanを使用した凸包の作成方法です。
実は、今回実装したGraham Scanプログラムを使用して作った作品を
「出現画廊」というグループ展で展示する事が決まりました。
日時：2023年3月3日(金)～3月26日(日)予定
-東京：池袋PARCO 本館7F ARTIE'S PARCO
-名古屋：名古屋PARCO 西館６F PARCO GALLERY
-京都：京都国際マンガミュージアム
公式URL：https://shutsugen.com/
このグループ展のテーマは「出現」です。
展示作品は開催してからのお楽しみですが、graham Scanを使用して「出現」を良い感じに表現しています笑
この展示のために結構頑張って作品を作ったので展示審査が通って本当に良かったです。
ぜひ見に来ていただけると嬉しいです！
凸包を作成するプログラムを実装するだけでも、色んな数学の知識を得る事ができて
表現の幅が広げる事ができました。
皆さんもぜひGraham Scanプログラムで遊んでみてください。
最後まで読んでいただきありがとうございました！
参考文献
Comments