授業で完成させたのが次のプログラムです。
/*
* TriangulatoinGreedyDP.java
*
* 凸多角形の最小重み三角化のための貪欲法と動的計画法の実装です。
*
*/
package task13;
import java.awt.Button;
import java.awt.Choice;
import java.awt.Color;
import java.awt.FlowLayout;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Label;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class TriangulationDP extends Frame
implements ActionListener {
// フレームの幅と高さ
private static final int WIDTH = 900;
private static final int HEIGHT = 700;
// デフォールトの頂点数
private static final int NP_DEFAULT = 10;
// 乱数の初期シード
private static final int INITIAL_SEED = 1111111;
// 描画領域の余白
private static final int LEFT_MARGIN = 100;
private static final int RIGHT_MARGIN = 100;
private static final int TOP_MARGIN = 150; // ボタン配置のための余裕
private static final int BOTTOM_MARGIN = 50;
private static final int NET_WIDTH = WIDTH - LEFT_MARGIN - RIGHT_MARGIN;
private static final int NET_HEIGHT = HEIGHT - TOP_MARGIN - BOTTOM_MARGIN;
// 点描画のための円盤の半径
private static final int RADIUS = 3;
// 表示座標の縮尺
private static final int SCALE = 10;
// 多角形頂点の個数
private int np;
// 頂点の配列
private Point point[];
// 対角線の本数
private int nd;
// 対角線の配列
private Diagonal diagonal[];
// 以下は、動的計画法のために用いる大域的な変数です。
// 部分問題の最適値の表
private int opt[][];
// 部分問題の最適分割頂点の表
private int bestDivider[][];
// 点数選択欄
private Choice chooseN;
// メッセージ用ラベル
private Label messageLabel;
// 乱数生成器
private Random random;
public TriangulationDP() {
// このフレームの大きさを設定する。
setSize(WIDTH, HEIGHT);
// 配置の方式をFlowLayout に設定
setLayout(new FlowLayout());
// 数入力
Label label1 = new Label("Polygon size:");
add(label1);
chooseN = new Choice();
chooseN.addItem("4");
chooseN.addItem("5");
chooseN.addItem("6");
chooseN.addItem("7");
chooseN.addItem("8");
chooseN.addItem("9");
chooseN.addItem("10");
chooseN.addItem("15");
chooseN.addItem("20");
chooseN.addItem("30");
chooseN.addItem("100");
add(chooseN);
// 多角形生成
Button generatePolygon = new Button("Generate Polygon");
add(generatePolygon);
generatePolygon.addActionListener(this);
// 貪欲法三角化
Button greedyButton = new Button("Greedy");
add(greedyButton);
greedyButton.addActionListener(this);
Button dpButton = new Button("DP");
add(dpButton);
dpButton.addActionListener(this);
// クリアボタン
Button clearButton = new Button("Clear");
add(clearButton);
clearButton.addActionListener(this);
// 終了ボタン
Button closeButton = new Button("Close");
add(closeButton);
closeButton.addActionListener(this);
// メッセージ用のラベル
messageLabel = new Label(
"message is displayed here .........");
add(messageLabel);
// フレームを可視化する
setVisible(true);
// 乱数生成器
// デバッグのため、初期シードを指定
random = new Random(INITIAL_SEED);
}
// フレームの描画が必要になったときに呼ばれる。
// 多角形や、対角線の描画をここで行う。
public void paint(Graphics g) {
// 点の描画。
for (int i = 0; i < np; i++) {
drawPoint(i, g);
}
// 辺の描画
for (int i = 0; i < np; i++) {
drawEdge(i, (i + 1) % np, g);
}
// 対角線の描画
if (diagonal != null) {
for (int i = 0; i < nd; i++)
if (diagonal[i] != null) {
drawEdge(diagonal[i].i1, diagonal[i].i2, g);
}
}
}
private void drawPoint(int i, Graphics g) {
g.setColor(Color.blue);
g.fillOval(point[i].xInFrame() - RADIUS,
point[i].yInFrame() - RADIUS,
RADIUS * 2, RADIUS * 2);
}
private void drawEdge(int i, int j,
Graphics g) {
g.setColor(Color.red);
g.drawLine(
point[i].xInFrame(),
point[i].yInFrame(),
point[j].xInFrame(),
point[j].yInFrame()
);
}
public void actionPerformed(ActionEvent ae) {
String commandName = ae.getActionCommand();
if (commandName.equals("Generate Polygon")) {
// 三角化のクリア
clear();
// 多角形の生成
generate();
}
else if (commandName.equals("Greedy")) {
// 三角化のクリア
clear();
// 貪欲法三角化アルゴリズムの呼び出し
greedy();
}
else if (commandName.equals("DP")) {
// 三角化のクリア
clear();
// 動的計画法三角化アルゴリズムの呼び出し
dp();
printTables();
}
else if (commandName.equals("Clear")) {
// 三角化のクリア
clear();
}
else if (commandName.equals("Close")) {
System.exit(0);
}
// フレームの再描画を要求する。
repaint();
}
// 多角形の生成（余裕のある人以外は読まなくてよい）
// 凸性を保証するために、（安易だが）楕円上に点をとる。
private void generate() {
String polygonSizeString = chooseN.getSelectedItem();
try {
np = Integer.parseInt(polygonSizeString);
}
catch (Exception e) {
// 頂点数入力欄が空欄などの場合：頂点数のデフォールト
np = NP_DEFAULT;
}
point = new Point[np];
int nq = np * 2; //全角2piを分割する数
int angleSequence[] = new int[np];
// nq 個の角度 2*i*pi / nq のうち、使うものnp個の番号
int k = 0;
for (int i = 0; i < nq; i++) {
// 確率 (np - k) / (nq - i)で iを選択
if (random.nextInt(nq - i) < np - k) {
angleSequence[k++] = i;
}
}
assert k == np;
double delta = Math.PI * 2.0 / (double) (nq);
for (int i = 0; i < np; i++) {
double theta = delta * (double) (angleSequence[i]);
double x = (NET_WIDTH * SCALE/ 2.4) * Math.cos(theta) +
NET_WIDTH * SCALE / 2.0;
double y = (NET_HEIGHT * SCALE/ 2.4) * Math.sin(theta) +
NET_HEIGHT * SCALE / 2.0;
point[i] = new Point((int) x, (int) y);
}
}
private void clear() {
diagonal = null;
messageLabel.setText("");
}
// 貪欲法による三角化
// 凸多角形の頂点数は大域変数 np で、
// 頂点の列（反時計回り）は 大域配列 point で与えられる
private void greedy() {
// すべての対角線の本数naを求める
int na = np * ( np - 3) / 2;
// すべての対角線を入れる配列を用意する
Diagonal all[] = new Diagonal[na];
// すべての対角線を生成して配列に格納する
// ２重の for 文になる
// Diagonal クラスを見て、コンストラクタの呼び出し方
// 確認する必要がある
// 特に、Diagonal オブジェクトは、両端点の頂点を
// その番号（point 配列中の添え字）によって憶えること
// に注意する。
// 隣接した点を結ぶ辺は対角線ではないことに注意する
// (0 番の頂点と np - 1 番の頂点も隣接している！）
int k=0;
for(int i=0; i<np; i++){
for(int j=i+2; j<np; j++){
if(!(i==0 && j==np-1)){
all[k++] = new Diagonal(i,j);
}
}
}
// 対角線を軽い順に整列
// Arrays クラスの sort メソッドを用いる
// 要素の比較には、下で定義するクラス WeightComparator
// を用いる
// WeightComparator クラスの定義も未完成なので
// 完成する必要がある。
//作成した対角線を重みの小さい順に整列させる。
Arrays.sort(all,new WeightComparator());
// 実際に採用する対角線の本数
nd = np - 3;
// 採用した対角線を入れる配列
diagonal = new Diagonal[nd];
// 配列 all 中の対角線を一本ずつ見ていき、
// 「これまでに採用された対角線のどれとも交差しないならば
// 採用する」 ということを繰り返す
//穴埋めで記述した部分です。
int l=0;
int flag = 0;
for(int i=0; i<na; i++){
for(int j=0; j<l; j++){
if(all[i].crosses(diagonal[j])){
flag = 1;
}
}
if(flag == 0){
diagonal[l++]=all[i];
}
flag = 0;
}
// 求まった重みを表示
int weight = 0; // 仮に重みの合計は 0としておく
for(int i=0; i < l; i++){
weight = weight + diagonal[i].weight;
}
messageLabel.setText("greedy weight = " + weight);
}
// 動的計画法による最小重み三角化
private void dp() {
// まず最適値の表を作成する。
opt = new int[np][np];
bestDivider = new int [np][np];
// opt[i][j] （0 <= i < j < np) は、頂点i, i + 1, ..., j
// からなる凸多角形の最小重み三角化の重みを表す。
// 特に、j = i + 1 のときはopt[i][j] = 0 とする。
/* j = i + 1 の場合について、opt[i][j] の表を埋める。*/
for(int i = 0; i < np; i++){
int j = i + 1;
//i=np-1のときj=npとなってしまい用意されている配列の最大を超えてしまうので0に戻す。
if(i==np-1){
opt[i][0] = 0;
}
else{
opt[i][j] = 0;
}
}
// bestDivider[i][j] は、頂点i, i + 1, ..., jからなる
// 凸多角形の最小重み三角化において、辺(i, j) を一辺とする
// 三角形のもうひとつの頂点の番号を表す。
// この凸多角形に対する最適分割頂点と呼ぶことにする。
// d = j - i =2, 3, ... の順に表を埋める
for (int d = 2; d < np; d++) {
for (int i = 0; i < np - d; i++) {
int j = i + d;
//頂点を i + 1 をとりあえずの最適分割頂点としておく
bestDivider[i][j] = i + 1;
// 分割頂点を指定したときの最適値は
// メソッド optWhenDivided によって求める
opt[i][j] =
optWhenDivided(i, j, i + 1);
// 最適分割頂点の候補 k = i + 2, .., j - 1
// について、次々と調べる。
for (int k = i + 2; k < j; k++) {
/* もし、kを分割頂点としたときの最適値が
* これまでのopt[i][j] よりも小さければ
* opt[i][j] と bestDivider[i][j]を更新する。
*/
if(optWhenDivided(i,j,k)<opt[i][j]){
opt[i][j] = optWhenDivided(i,j,k);
bestDivider[i][j] = k;
}
}
}
}
// 今回は、表が完成したところで終わり
}
// 頂点i, i + 1, ..., j からなる凸多角形において、
// i と k、j と k を結ぶと決めたときの最適な三角化の重みを計算して返す
private int optWhenDivided(int i, int j, int k) {
/*opt[i][k] と opt[k][j] を用いて計算する。
* (i, k) が対角線のときは、その重み、
* (k, j) が対角線のときは、その重み
* を含める。
*/
int result = 0;
//最適な三角化の重みを計算する。
result = opt[i][k]+opt[k][j];
//iがkに隣接していなければ(i,k)は対角線となるのでその重みを先ほどのものに加える。
if(k!=i+1){
result = result + weight(i,k);
}
//jがkに隣接していなければ(k,j)は対角線となるのでその重みを先ほどのものに加える。
if(j!=k+1){
result = result + weight(k,j);
}
return result;
}
// 重みの表と動的計画法の表のプリント
private void printTables(){
int w = 5;
System.out.println("対角線の重み");
System.out.print(" i|j");
for (int j = 0; j < np; j++) {
printWithWidth(j, w);
}
System.out.println();
for (int i = 0; i < np - 2; i++) {
printWithWidth(i, w);
printSpaces((i + 2) * w);
for (int j = i + 2; j < np; j++) {
printWithWidth(weight(i, j), w);
}
System.out.println();
}
System.out.println("最適値の表");
System.out.print(" i|j");
for (int j = 0; j < np; j++) {
printWithWidth(j, w);
}
System.out.println();
for (int i = 0; i < np - 2; i++) {
printWithWidth(i, w);
printSpaces((i + 2) * w);
for (int j = i + 2; j < np; j++) {
printWithWidth(opt[i][j], w);
}
System.out.println();
}
System.out.println("最適分割頂点の表");
System.out.print(" i|j");
for (int j = 0; j < np; j++) {
printWithWidth(j, w);
}
System.out.println();
for (int i = 0; i < np - 2; i++) {
printWithWidth(i, w);
printSpaces((i + 2) * w);
for (int j = i + 2; j < np; j++) {
printWithWidth(bestDivider[i][j], w);
}
System.out.println();
}
}
// 空白をw個プリント。w <= 0 ならば何もしない。
private void printSpaces(int w) {
for (int i = 0; i < w; i++)
System.out.print(" ");
}
// 整数nをプリントする。
// 直前のスペースの個数で、可能ならば幅がwになるように調節。
private void printWithWidth(int n, int w) {
String s = " " + n;
printSpaces(w - s.length());
System.out.print(s);
}
// 頂点iと頂点j を結ぶ対角線の重み
//（長さの切捨て)
private int weight(int i, int j) {
int dx = point[i].x - point[j].x;
int dy = point[i].y - point[j].y;
return (int) Math.sqrt(dx * dx + dy * dy);
}
// ２次元平面上の点を表すクラス
private class Point {
// 論理的な座標（フレームで表示される座標とは
// 縮尺、上下反転などを通して対応）
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// フレーム上の表示場所の x 座標
private int xInFrame() {
return x / SCALE + LEFT_MARGIN;
}
// フレーム上の表示場所の y 座標
// 座標 0 がフレーム下端になるように上下反転
private int yInFrame() {
return HEIGHT - BOTTOM_MARGIN - y /SCALE;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
// 対角線を表すクラス
private class Diagonal {
int i1, i2; // 端点の番号
int weight; // この辺の重さ（長さを切り捨てた整数値）
private Diagonal(int i1, int i2) {
this.i1 = i1;
this.i2 = i2;
weight = weight(i1, i2);
}
// 対角線 d と交わるか？
// 座標の計算は必要ない。
// 凸多角形なので、頂点の番号の並びから判定できる。
private boolean crosses(Diagonal d) {
// 頂点 i1, d.i1, i2, d.i2 が反時計まわりに
// この順であらわれるか、または
// 頂点 i1, d.i2, i2, d.i1 が反時計まわりに
// この順であらわれるならば、交差する。
// 反時計まわりの順かどうかの判定は下の
// counterClockwise メソッドを実装して用いる。
//穴埋めで記述した部分です。
if(counterClockwise(i1,d.i1,i2,d.i2)||counterClockwise(i1,d.i2,i2,d.i1)) return true;
else return false;
}
// 番号が i1, i2, i3, i4 の頂点が、
// 多角形中でこの順に反時計まわりに並んでいるならば true
// そうでなければ false を返す。下のコードでは答えが
// trueとなるひとつの場合をひとつだけ考えているが、
// この他に三つ、trueになる場合があるので、それらをOR (||)で
// 結ばなければならない。
private boolean counterClockwise
(int i1, int i2, int i3, int i4) {
return i1 < i2 && i2 < i3 && i3 < i4 ||
i4 < i1 && i1 < i2 && i2 < i3 ||
i3 < i4 && i4 < i1 && i1 < i2 ||
i2 < i3 && i3 < i4 && i4 < i1;
}
}
//穴埋めで記述した部分です。
public class WeightComparator implements Comparator<Diagonal> {
public int compare(Diagonal d, Diagonal e) {
// 対角線の重みによる比較
// d.weight < e.weight ならば 負の値
// d.weight > e.weight ならば 正の値
// d.weight = e.weight ならば 0 を返す
Integer a = new Integer(d.weight);
Integer b = new Integer(e.weight);
return a.compareTo(b);
}
}
public static void main(String[] args) {
// TriangulationRecursive オブジェクトの生成
new TriangulationDP();
}
}ＤＰボタンを押すと動的計画法で三角化がおこなわれ、
対角線の表と最適値の表opt[][]と最適な分割の情報を表す表bestDivder[][]が出力されます。
頂点数を6にして動的計画法を行うと次の表が出力されました。
ですがこの表の意味がいまいちよくわかりません。
まず対角線の重みの頂点iがなぜ0~3までしかないのでしょうか？
i=4とi=5の行がいらない理由がわかりません。
また表の重みが入っていない部分が（i=0,j=2など）あるのですが、なぜですか？
最適値の表と最適分割頂点の表ですが、これはどのような値が表に入っているのでしょうか？
よろしくお願いします。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター