大学の課題で出されたものでプログラムの穴埋めをする問題で、解いてみたのですが、エラーが出て実行できませんでした。
以下がプログラムです。
/*
* TriangulatoinGreedy.java
*
* 凸多角形の最小重み三角化のための貪欲法の実装です。
*
*/
package task12;
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 TriangulationGreedy 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 Choice chooseN;
// メッセージ用ラベル
private Label messageLabel;
// 乱数生成器
private Random random;
public TriangulationGreedy() {
// このフレームの大きさを設定する。
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 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("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<nd; 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 < nd; i++){
weight = weight + diagonal[i].weight;
}
messageLabel.setText("greedy weight = " + weight);
}
// 頂点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 TriangulationGreedy();
}
}
greedy()メソッドと、Diagonalクラスのcrosses()メソッドと、counterClockwize()メソッドと、WeightComparatorクラス
だけです。そのほかの場所は最初から用意されていて変更をしていないので間違ってないはずです。
コンパイルはできたのですが、実行して、多角形の頂点数を決めて多角形を作成し、分割（Greedyボタンを押す）するとエラーが出ました。
エラーメッセージは次のものが出ました。
D:\SCHOOLDATA\でとあ\新しいフォルダー\build>java task12.TriangulationGreedy
Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException
at task12.TriangulationGreedy$Diagonal.crosses(TriangulationGreedy.java:
388)
at task12.TriangulationGreedy$Diagonal.access$300(TriangulationGreedy.ja
va:366)
at task12.TriangulationGreedy.greedy(TriangulationGreedy.java:306)
at task12.TriangulationGreedy.actionPerformed(TriangulationGreedy.java:1
83)
at java.awt.Button.processActionEvent(Button.java:409)
at java.awt.Button.processEvent(Button.java:377)
at java.awt.Component.dispatchEventImpl(Component.java:4861)
at java.awt.Component.dispatchEvent(Component.java:4687)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:729)
at java.awt.EventQueue.access$200(EventQueue.java:103)
at java.awt.EventQueue$3.run(EventQueue.java:688)
at java.awt.EventQueue$3.run(EventQueue.java:686)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDo
main.java:76)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDo
main.java:87)
at java.awt.EventQueue$4.run(EventQueue.java:702)
at java.awt.EventQueue$4.run(EventQueue.java:700)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDo
main.java:76)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:699)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThre
ad.java:242)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.
java:161)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThre
ad.java:150)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:146)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:138)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:91)
プログラムでおかしな点があれば教えてください。
授業時間内に提出できなかったので、期限外になってしまうのですがそれでも提出はしたいので助けてください。
よろしくお願いします。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター