|
凸包とは、平面グラフ上の点（ある点集合）の中で最も｢外側」にある点を直線で結んで出来る線分の集合です。つまり、凸包の直線群はその線の内側にすべての点が含まれるような、いわばその点集合の最短の「境界線」と言えるでしょう。 凸包を求めるアルゴリズムまず、「すでにある凸包上にある点を出発点として次の凸包上の点を探す」アルゴリズムを考えてみましょう。凸包は「直線」の集合なので、２つの点を結ぶ直線の「角度」に注目してみると良さそうですね。 まず凸包上の最も左下にある点を出発点として、その点からｘ軸に平行に直線を延ばしてみましょう。そして、その直線を反時計周りつまりx軸との角度を大きくしていくような方向に回転させていきます。こうして角度を大きくしてき最初に出会った点は、その「外側」に点がないわけですから、明らかに「凸包」上の点になるはずです。 さらに、そうして求めた新たな点を出発点として、同じように直線を回転させて最初にであった点が次の凸包上の点になります。ただし、直線の最初の角度はｘ 軸と平行ではなく出会ったときの角度します。 これで「凸包上にある点」が一つ求まれば、後は次々に「凸包上にある次の点」を求められるアルゴリズムがわかってきました。あとは、最初に適当な凸包上の点（各点の座標から算出）を決めてそこから出発すれば、凸包上の点を次々にたどっていけるでしょう。 プログラムでは、直線を引いていくのではなく点と点を結んだ線の角度を調べています。現在注目している凸包上の点との角度が、前回の角度以上になる点を調査対象とし、その中から直線の角度が最小になる点を次の凸包上の点と判定します。 例として作ったプログラムは、まずマウスでグラフ上に適当に点を打ってからGoボタンを押すとグラフ上の点の凸包を描きます。特に、凸包に含まれると判断した点は赤く表示されますので、凸包の赤い線と見比べて見てください。 凸包上にありながら、赤くならない点が出来る事がありますね。これは、角度のみに注目し、距離に注目していないからです。もし、凸包上の点をすべて求めたいなら、角度だけでなく距離にも注目して、同じ角度の点があるなら距離が最小になる点を次の点にする必要があります。 |