实现 Bresenham 的圆形绘制算法
Implementing Bresenham's circle drawing algorithm
我已经编写了 Bresenham 圆绘制算法的实现。 该算法利用了圆的高度对称性（它仅从第一个八分圆计算点，并利用对称性绘制其他点）。因此我期待它会非常快。图形编程黑皮书，第 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 上获得）的第三个实现object)。这些附加实现的唯一目的是将 Bresenham 的算法与它们进行比较。
然后我创建了绘制一堆圆圈的方法，以便能够很好地衡量花费的时间。这是我使用 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 的 paint 方法，以绘制一堆圆圈并测量绘制每种类型所花费的时间。这是绘画方法：
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 的实施速度很慢。我采取了很多比较措施，Bresenham 的实施不仅比 Graphics.drawArc 慢，而且比三角方法慢。查看以下针对绘制的不同数量的圆圈的测量值。
我实现的哪一部分比较time-consuming？有什么解决方法可以用来改进它吗？感谢您的帮助。
[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;
}
}
您的 Bresenham 方法本身并不慢，只是比较慢。
Swing 的 drawArc() 实现依赖于机器，使用本机代码。使用 Java 永远无法击败它，所以不要费心去尝试。 （我真的很惊讶 Java Bresenham 方法与 drawArc() 相比速度一样快，这证明了执行 Java 字节码的虚拟机的质量。）
但是，您的三角函数法快得不必要，因为您没有在同等基础上将它与 Bresenham 进行比较。
trig 方法设置 angular 分辨率为 PI/36（~4.7 度），如 for 语句末尾的此操作：
angle = angle + Math.PI/36
同时，您的 Bresenham 方法依赖于半径，在每个像素变化时计算一个值。由于每个八分圆产生 sqrt(2) 点，将其乘以 8 再除以 2*Pi 将得到等效的 angular 分辨率。因此，要与 Bresenham 方法处于同等地位，您的三角法应具有：
resolution = 4 * r * Math.sqrt(2) / Math.PI;
循环外的某个地方，并增加你的for，如：
angle += resolution
由于我们现在将回到像素级分辨率，您实际上可以改进 trig 方法并删除随后的 drawline 调用和对 x0 和 y0 的赋值，消除不必要的转换，并进一步减少对 Math 的调用。这是完整的新方法：
public static void drawTrigonometricalCircle (double r, double width, double height,
Graphics g) {
double localPi = Math.PI;
double resolution = 4 * r * Math.sqrt(2) / Math.PI;
for (double angle = 0; angle <= localPi; angle += resolution) {
double x = r * Math.cos(angle);
double y = r * Math.sin(angle);
drawPoint(x, y, width, height, g);
}
}
trig 方法的执行频率现在将提高几个数量级，具体取决于 r 的大小。
我很想看看你的结果。
你的问题在于 Bresenham 算法根据圆的大小进行可变次数的迭代，而你的三角方法总是进行固定次数的迭代。
这也意味着 Bresenham 算法总是会生成一个看起来很平滑的圆，而你的三角方法会随着半径的增加生成一个看起来更差的圆。
为了使其更均匀，请更改三角函数方法以产生与 Bresenham 实施大致一样多的点，您将看到它的速度有多快。
我写了一些代码来对此进行基准测试，还打印了产生的点数，这是初始结果：
三角函数：181 毫秒，平均 73 点
Bresenham：120 毫秒，平均 867.568 分
修改三角函数 class 以进行更多迭代以获得更平滑的圆之后：
int totalPoints = (int)Math.ceil(0.7 * r * 8);
double delta = 2 * Math.PI / totalPoints;
for (double angle = 0; angle <= 2*Math.PI; angle = angle + delta) {
这些是结果：
三角函数：2006 毫秒，平均 854.933 点
Bresenham：120 毫秒，平均 867.568 分
我最近为精灵光栅器编写了一个 bresenham 圆绘图实现，并尝试对其进行一些优化。我不确定它是否会比你做的更快或更慢，但我认为它应该有一个相当不错的执行时间。
同样不幸的是，它是用 C++ 编写的。如果我明天有时间，我可能会用移植的 Java 版本和结果的示例图片来编辑我的答案，但现在你必须自己做，如果你愿意的话（或者其他人想要把他的时间并编辑它。）
基本上，它所做的是使用bresenham算法获取圆的外边缘位置，然后对圆的1/8执行算法并通过绘制直线对其余7部分进行镜像从中心到外边缘的线。
Color只是一个rgba值
Color* createCircleColorArray(const int radius, const Color& color, int& width, int& height) {
// Draw circle with custom bresenham variation
int decision = 3 - (2 * radius);
int center_x = radius;
int center_y = radius;
Color* data;
// Circle is center point plus radius in each direction high/wide
width = height = 2 * radius + 1;
data = new Color[width * height];
// Initialize data array for transparency
std::fill(data, data + width * height, Color(0.0f, 0.0f, 0.0f, 0.0f));
// Lambda function just to draw vertical/horizontal straight lines
auto drawLine = [&data, width, height, color] (int x1, int y1, int x2, int y2) {
// Vertical
if (x1 == x2) {
if (y2 < y1) {
std::swap(y1, y2);
}
for (int x = x1, y = y1; y <= y2; y++) {
data[(y * width) + x] = color;
}
}
// Horizontal
if (y1 == y2) {
if (x2 < x1) {
std::swap(x1, x2);
}
for (int x = x1, y = y1; x <= x2; x++) {
data[(y * width) + x] = color;
}
}
};
// Lambda function to draw actual circle split into 8 parts
auto drawBresenham = [color, drawLine] (int center_x, int center_y, int x, int y) {
drawLine(center_x + x, center_y + x, center_x + x, center_y + y);
drawLine(center_x - x, center_y + x, center_x - x, center_y + y);
drawLine(center_x + x, center_y - x, center_x + x, center_y - y);
drawLine(center_x - x, center_y - x, center_x - x, center_y - y);
drawLine(center_x + x, center_y + x, center_x + y, center_y + x);
drawLine(center_x - x, center_y + x, center_x - y, center_y + x);
drawLine(center_x + x, center_y - x, center_x + y, center_y - x);
drawLine(center_x - x, center_y - x, center_x - y, center_y - x);
};
for (int x = 0, y = radius; y >= x; x++) {
drawBresenham(center_x, center_y, x, y);
if (decision > 0) {
y--;
decision += 4 * (x - y) + 10;
}
else {
decision += 4 * x + 6;
}
}
return data;
}
//编辑
哇哦，我才意识到这个问题有多老。
我已经编写了 Bresenham 圆绘制算法的实现。 该算法利用了圆的高度对称性（它仅从第一个八分圆计算点，并利用对称性绘制其他点）。因此我期待它会非常快。图形编程黑皮书，第 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 上获得）的第三个实现object)。这些附加实现的唯一目的是将 Bresenham 的算法与它们进行比较。
然后我创建了绘制一堆圆圈的方法，以便能够很好地衡量花费的时间。这是我使用 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 的 paint 方法，以绘制一堆圆圈并测量绘制每种类型所花费的时间。这是绘画方法：
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 的实施速度很慢。我采取了很多比较措施，Bresenham 的实施不仅比 Graphics.drawArc 慢，而且比三角方法慢。查看以下针对绘制的不同数量的圆圈的测量值。
我实现的哪一部分比较time-consuming？有什么解决方法可以用来改进它吗？感谢您的帮助。
[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;
}
}
您的 Bresenham 方法本身并不慢，只是比较慢。
Swing 的 drawArc() 实现依赖于机器，使用本机代码。使用 Java 永远无法击败它，所以不要费心去尝试。 （我真的很惊讶 Java Bresenham 方法与 drawArc() 相比速度一样快，这证明了执行 Java 字节码的虚拟机的质量。）
但是，您的三角函数法快得不必要，因为您没有在同等基础上将它与 Bresenham 进行比较。
trig 方法设置 angular 分辨率为 PI/36（~4.7 度），如 for 语句末尾的此操作：
angle = angle + Math.PI/36
同时，您的 Bresenham 方法依赖于半径，在每个像素变化时计算一个值。由于每个八分圆产生 sqrt(2) 点，将其乘以 8 再除以 2*Pi 将得到等效的 angular 分辨率。因此，要与 Bresenham 方法处于同等地位，您的三角法应具有：
resolution = 4 * r * Math.sqrt(2) / Math.PI;
循环外的某个地方，并增加你的for，如：
angle += resolution
由于我们现在将回到像素级分辨率，您实际上可以改进 trig 方法并删除随后的 drawline 调用和对 x0 和 y0 的赋值，消除不必要的转换，并进一步减少对 Math 的调用。这是完整的新方法：
public static void drawTrigonometricalCircle (double r, double width, double height,
Graphics g) {
double localPi = Math.PI;
double resolution = 4 * r * Math.sqrt(2) / Math.PI;
for (double angle = 0; angle <= localPi; angle += resolution) {
double x = r * Math.cos(angle);
double y = r * Math.sin(angle);
drawPoint(x, y, width, height, g);
}
}
trig 方法的执行频率现在将提高几个数量级，具体取决于 r 的大小。
我很想看看你的结果。
你的问题在于 Bresenham 算法根据圆的大小进行可变次数的迭代，而你的三角方法总是进行固定次数的迭代。
这也意味着 Bresenham 算法总是会生成一个看起来很平滑的圆，而你的三角方法会随着半径的增加生成一个看起来更差的圆。
为了使其更均匀，请更改三角函数方法以产生与 Bresenham 实施大致一样多的点，您将看到它的速度有多快。
我写了一些代码来对此进行基准测试，还打印了产生的点数，这是初始结果：
三角函数：181 毫秒，平均 73 点
Bresenham：120 毫秒，平均 867.568 分
修改三角函数 class 以进行更多迭代以获得更平滑的圆之后：
int totalPoints = (int)Math.ceil(0.7 * r * 8);
double delta = 2 * Math.PI / totalPoints;
for (double angle = 0; angle <= 2*Math.PI; angle = angle + delta) {
这些是结果：
三角函数：2006 毫秒，平均 854.933 点
Bresenham：120 毫秒，平均 867.568 分
我最近为精灵光栅器编写了一个 bresenham 圆绘图实现，并尝试对其进行一些优化。我不确定它是否会比你做的更快或更慢，但我认为它应该有一个相当不错的执行时间。
同样不幸的是，它是用 C++ 编写的。如果我明天有时间，我可能会用移植的 Java 版本和结果的示例图片来编辑我的答案，但现在你必须自己做，如果你愿意的话（或者其他人想要把他的时间并编辑它。）
基本上，它所做的是使用bresenham算法获取圆的外边缘位置，然后对圆的1/8执行算法并通过绘制直线对其余7部分进行镜像从中心到外边缘的线。
Color只是一个rgba值
Color* createCircleColorArray(const int radius, const Color& color, int& width, int& height) {
// Draw circle with custom bresenham variation
int decision = 3 - (2 * radius);
int center_x = radius;
int center_y = radius;
Color* data;
// Circle is center point plus radius in each direction high/wide
width = height = 2 * radius + 1;
data = new Color[width * height];
// Initialize data array for transparency
std::fill(data, data + width * height, Color(0.0f, 0.0f, 0.0f, 0.0f));
// Lambda function just to draw vertical/horizontal straight lines
auto drawLine = [&data, width, height, color] (int x1, int y1, int x2, int y2) {
// Vertical
if (x1 == x2) {
if (y2 < y1) {
std::swap(y1, y2);
}
for (int x = x1, y = y1; y <= y2; y++) {
data[(y * width) + x] = color;
}
}
// Horizontal
if (y1 == y2) {
if (x2 < x1) {
std::swap(x1, x2);
}
for (int x = x1, y = y1; x <= x2; x++) {
data[(y * width) + x] = color;
}
}
};
// Lambda function to draw actual circle split into 8 parts
auto drawBresenham = [color, drawLine] (int center_x, int center_y, int x, int y) {
drawLine(center_x + x, center_y + x, center_x + x, center_y + y);
drawLine(center_x - x, center_y + x, center_x - x, center_y + y);
drawLine(center_x + x, center_y - x, center_x + x, center_y - y);
drawLine(center_x - x, center_y - x, center_x - x, center_y - y);
drawLine(center_x + x, center_y + x, center_x + y, center_y + x);
drawLine(center_x - x, center_y + x, center_x - y, center_y + x);
drawLine(center_x + x, center_y - x, center_x + y, center_y - x);
drawLine(center_x - x, center_y - x, center_x - y, center_y - x);
};
for (int x = 0, y = radius; y >= x; x++) {
drawBresenham(center_x, center_y, x, y);
if (decision > 0) {
y--;
decision += 4 * (x - y) + 10;
}
else {
decision += 4 * x + 6;
}
}
return data;
}
//编辑
哇哦，我才意识到这个问题有多老。