Я написал реализацию алгоритма рисования круга Bresenham. Эти алгоритмы используют высокосимметричные свойства круга (он вычисляет точки только с 1-го октанта и рисует другие точки, пользуясь симметриями). Поэтому я ожидал, что это будет очень быстро. Черная книга программирования графики, глава № 35 была названа " Bresenham - это быстро, а скорость хорошая", и хотя речь шла о алгоритме рисования линий, я мог бы разумно ожидать, что алгоритм рисования окружности также будет быстро (поскольку принцип тот же).
Вот моя реализация java, swing
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 используются для переключения координат из исходного в верхнем левом углу экрана в систему, которая имеет начало координат в центре панели с более классической ориентацией оси.
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). Эти дополнительные реализации предназначены исключительно для сравнения алгоритма Брешенема с ними.
Затем я создал методы, чтобы нарисовать кучу кругов, чтобы иметь возможность получить хорошие оценки затраченного времени. Вот метод, который я использую, чтобы нарисовать кучу кругов с использованием алгоритма Брешенема
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;
}
}