Java 中的 Bresenham 圆绘制算法实现
Bresenham circle drawing algorithm implementation in Java
我在 Java 中实现了 Bresenham Circle 绘图算法。但是输出没有正确绘制!我找不到问题出在哪里。
我的代码和输出图像如下。感谢任何帮助。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double d = 5 - 4*radius;
while(x<y){
if(d<0){ //dE
x+=.01;
d+=(2*x + 3)*4;
}else{
x+=.01;
y-=.01;
d+=(2*x - 2*y +5)*4;
}
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
试试这个。我现在使用的计算机上没有 java,让我们看看它是否有效。确保使用整数,因为您要规范化的是块大小!
编辑: 添加了整数。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double d = 3 - 2*radius;
while(x<y){
x++;
if(d<0){ //dE
d= d + 4x + 6;
}else{
y--;
d= d+ 4(x - y) + 10;
}
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
请注意,原来的 Bresenham's circle algorithm 仅适用于整数。由于您的更新是 x_{n+1}=x_n+eps
,您可以将 y
更新修改为
y_{n+1}^2 = y_n^2 - 2*eps*n-eps*eps
推导与维基页面给出的相同。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double eps = .01;
double eps2 = eps*eps;
while(x<y){
y = Math.sqrt(y*y-2*eps*x-eps2);
x+= eps;
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
结果:
还要小心aspect ratio。此算法适用于比率 1:1
。但是,如果您的长宽比是 a:b
,那么您的圆方程将变为 x^2/a^2+y^2/b^2=r^2
。您可以相应地更改更新。
下面是使用 Bresenham 算法绘制自定义圆的示例。
完整代码可以在我的仓库中找到:https://github.com/Maiakov/algorithms/tree/master/Task40
/**
* Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point
* <p>
* computations at all.
*/
public class DrawCircleAlgorithm {
public static void drawCircle(int radius, int centerX, int centerY, Graphics g) {
int y = radius;
int x = 0;
int delta = calculateStartDelta(radius);
while (y >= x) {
drawPixelAndReflect(centerX, centerY, x, y, g);
if (delta < 0) {
delta = calculateDeltaForHorizontalPixel(delta, x);
} else {
delta = calculateDeltaForDiagonalPixel(delta, x, y);
y--;
}
x++;
}
}
private static int calculateStartDelta(int radius) {
return 3 - 2 * radius;
}
private static int calculateDeltaForHorizontalPixel(int oldDelta, int x) {
return oldDelta + 4 * x + 6;
}
private static int calculateDeltaForDiagonalPixel(int oldDelta, int x, int y) {
return oldDelta + 4 * (x - y) + 10;
}
private static void drawPixelAndReflect(int centerX, int centerY, int x, int y, Graphics g) {
g.drawLine(centerX + x, centerY + y, centerX + x, centerY + y);
g.drawLine(centerX + x, centerY - y, centerX + x, centerY - y);
g.drawLine(centerX - x, centerY + y, centerX - x, centerY + y);
g.drawLine(centerX - x, centerY - y, centerX - x, centerY - y);
g.drawLine(centerX - y, centerY + x, centerX - y, centerY + x);
g.drawLine(centerX - y, centerY - x, centerX - y, centerY - x);
g.drawLine(centerX + y, centerY + x, centerX + y, centerY + x);
g.drawLine(centerX + y, centerY - x, centerX + y, centerY - x);
}
}
我在 Java 中实现了 Bresenham Circle 绘图算法。但是输出没有正确绘制!我找不到问题出在哪里。
我的代码和输出图像如下。感谢任何帮助。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double d = 5 - 4*radius;
while(x<y){
if(d<0){ //dE
x+=.01;
d+=(2*x + 3)*4;
}else{
x+=.01;
y-=.01;
d+=(2*x - 2*y +5)*4;
}
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
试试这个。我现在使用的计算机上没有 java,让我们看看它是否有效。确保使用整数,因为您要规范化的是块大小!
编辑: 添加了整数。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double d = 3 - 2*radius;
while(x<y){
x++;
if(d<0){ //dE
d= d + 4x + 6;
}else{
y--;
d= d+ 4(x - y) + 10;
}
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
请注意,原来的 Bresenham's circle algorithm 仅适用于整数。由于您的更新是 x_{n+1}=x_n+eps
,您可以将 y
更新修改为
y_{n+1}^2 = y_n^2 - 2*eps*n-eps*eps
推导与维基页面给出的相同。
public void display(GLAutoDrawable drawable) {
final GL2 gl = drawable.getGL().getGL2();
gl.glBegin (GL2.GL_POINTS);
double radius = 0.6;//sc.nextDouble();
double x =0.0;
double y = radius;
gl.glVertex2d(0.0,0.0);
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
double eps = .01;
double eps2 = eps*eps;
while(x<y){
y = Math.sqrt(y*y-2*eps*x-eps2);
x+= eps;
gl.glVertex2d(x,y);
gl.glVertex2d(-x,y);
gl.glVertex2d(x,-y);
gl.glVertex2d(-x,-y);
gl.glVertex2d(y,x);
gl.glVertex2d(-y,x);
gl.glVertex2d(y,-x);
gl.glVertex2d(-y,-x);
}
gl.glEnd();
}
结果:
还要小心aspect ratio。此算法适用于比率 1:1
。但是,如果您的长宽比是 a:b
,那么您的圆方程将变为 x^2/a^2+y^2/b^2=r^2
。您可以相应地更改更新。
下面是使用 Bresenham 算法绘制自定义圆的示例。 完整代码可以在我的仓库中找到:https://github.com/Maiakov/algorithms/tree/master/Task40
/**
* Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point
* <p>
* computations at all.
*/
public class DrawCircleAlgorithm {
public static void drawCircle(int radius, int centerX, int centerY, Graphics g) {
int y = radius;
int x = 0;
int delta = calculateStartDelta(radius);
while (y >= x) {
drawPixelAndReflect(centerX, centerY, x, y, g);
if (delta < 0) {
delta = calculateDeltaForHorizontalPixel(delta, x);
} else {
delta = calculateDeltaForDiagonalPixel(delta, x, y);
y--;
}
x++;
}
}
private static int calculateStartDelta(int radius) {
return 3 - 2 * radius;
}
private static int calculateDeltaForHorizontalPixel(int oldDelta, int x) {
return oldDelta + 4 * x + 6;
}
private static int calculateDeltaForDiagonalPixel(int oldDelta, int x, int y) {
return oldDelta + 4 * (x - y) + 10;
}
private static void drawPixelAndReflect(int centerX, int centerY, int x, int y, Graphics g) {
g.drawLine(centerX + x, centerY + y, centerX + x, centerY + y);
g.drawLine(centerX + x, centerY - y, centerX + x, centerY - y);
g.drawLine(centerX - x, centerY + y, centerX - x, centerY + y);
g.drawLine(centerX - x, centerY - y, centerX - x, centerY - y);
g.drawLine(centerX - y, centerY + x, centerX - y, centerY + x);
g.drawLine(centerX - y, centerY - x, centerX - y, centerY - x);
g.drawLine(centerX + y, centerY + x, centerX + y, centerY + x);
g.drawLine(centerX + y, centerY - x, centerX + y, centerY - x);
}
}