Bresenham の円描画アルゴリズムの実装を作成しました。このアルゴリズムは、円の高度な対称性を利用しています(1 番目の八分円から点のみを計算し、対称性を利用して他の点を描画します)。したがって、私はそれが非常に速いと予想していました。グラフィックス プログラミング ブラック ブック、第 35 章のタイトルは「ブレゼンハムは速く、速いことは良い」であり、線描画アルゴリズムに関するものでしたが、円描画アルゴリズムも高速であると合理的に期待できました (原理は同じ）。
これが私のJava、スイングの実装です
public static void drawBresenhamsCircle(int r, double width, double height, Graphics g) {
int x,y,d;
y = r;
x = 0;
drawPoint(x, y, width, height,g);
d = (3-2*(int)r);
while (x <= y) {
if (d <= 0) {
d = d + (4*x + 6);
} else {
d = d + 4*(x-y) + 10;
y--;
}
x++;
drawPoint(x, y, width, height,g);
drawPoint(-x, y, width, height,g);
drawPoint(x, -y, width, height,g);
drawPoint(-x, -y, width, height,g);
drawPoint(y, x, width, height,g);
drawPoint(-y, x, width, height,g);
drawPoint(y, -x, width, height,g);
drawPoint(-y, -x, width, height,g);
}
}
この方法では、次の方法を使用しますdrawPoint。
public static void drawPoint(double x, double y,double width,double height, Graphics g) {
double nativeX = getNativeX(x, width);
double nativeY = getNativeY(y, height);
g.fillRect((int)nativeX, (int)nativeY, 1, 1);
}
getNativeX と getNativeY の 2 つのメソッドを使用して、座標を画面の左上隅を起点とする座標系から、より古典的な軸方向でパネルの中央を原点とする座標系に切り替えます。
public static double getNativeX(double newX, double width) {
return newX + (width/2);
}
public static double getNativeY(double newY, double height) {
return (height/2) - newY;
}
x=R*Math.cos(angle)また、三角関数の公式 (および)に基づく円描画アルゴリズムのy= R*Math.sin(angle)実装と、標準の drawArc メソッド (Graphics オブジェクトで使用可能) の呼び出しを使用した 3 つ目の実装も作成しました。これらの追加の実装は、ブレゼンハムのアルゴリズムをそれらと比較することのみを目的としています。
次に、費やされた時間を適切に測定できるように、たくさんの円を描くメソッドを作成しました。Bresenhamのアルゴリズムを使用して多数の円を描くために使用する方法は次のとおりです
public static void drawABunchOfBresenhamsCircles(int numOfCircles, double width, double height, Graphics g) {
double r = 5;
double step = (300.0-5.0)/numOfCircles;
for (int i = 1; i <= numOfCircles; i++) {
drawBresenhamsCircle((int)r, width, height, g);
r += step;
}
}
最後に、使用している JPanel のペイント メソッドをオーバーライドして、多数の円を描画し、各タイプの描画にかかった時間を測定します。ペイント方法は次のとおりです。
public void paint(Graphics g) {
Graphics2D g2D = (Graphics2D)g;
g2D.setColor(Color.RED);
long trigoStartTime = System.currentTimeMillis();
drawABunchOfTrigonometricalCircles(1000, this.getWidth(), this.getHeight(), g);
long trigoEndTime = System.currentTimeMillis();
long trigoDelta = trigoEndTime - trigoStartTime;
g2D.setColor(Color.BLUE);
long bresenHamsStartTime = System.currentTimeMillis();
drawABunchOfBresenhamsCircles(1000, this.getWidth(), this.getHeight(), g);
long bresenHamsEndTime = System.currentTimeMillis();
long bresenDelta = bresenHamsEndTime - bresenHamsStartTime;
g2D.setColor(Color.GREEN);
long standardStarTime = System.currentTimeMillis();
drawABunchOfStandardCircles(1000, this.getWidth(), this.getHeight(),g);
long standardEndTime = System.currentTimeMillis();
long standardDelta = standardEndTime - standardStarTime;
System.out.println("Trigo : " + trigoDelta + " milliseconds");
System.out.println("Bresenham :" + bresenDelta + " milliseconds");
System.out.println("Standard :" + standardDelta + " milliseconds");
}
生成されるレンダリングの種類は次のとおりです (各タイプの 1000 個の円を描画)
残念ながら、私の Bresenham の実装は非常に遅いです。私は多くの比較測定を行いましたが、ブレゼンハムの実装は よりGraphics.drawArcも遅いだけでなく、三角法のアプローチよりも遅いです。描かれたさまざまな数の円について、次の対策を見てください。
実装のどの部分がより時間がかかりますか? それを改善するために使用できる回避策はありますか？助けてくれてありがとう。
[EDITION] : @higuaro のリクエストに応じて、円を描くための三角法アルゴリズムを次に示します。
public static void drawTrigonometricalCircle (double r, double width, double height, Graphics g) {
double x0 = 0;
double y0 = 0;
boolean isStart = true;
for (double angle = 0; angle <= 2*Math.PI; angle = angle + Math.PI/36) {
double x = r * Math.cos(angle);
double y = r * Math.sin(angle);
drawPoint((double)x, y, width, height, g);
if (!isStart) {
drawLine(x0, y0, x, y, width, height, g);
}
isStart = false;
x0 = x;
y0 = y;
}
}
そして、三角関数の円の束を描くために使用される方法
public static void drawABunchOfTrigonometricalCircles(int numOfCircles, double width, double height, Graphics g) {
double r = 5;
double step = (300.0-5.0)/numOfCircles;
for (int i = 1; i <= numOfCircles; i++) {
drawTrigonometricalCircle(r, width, height, g);
r += step;
}
}