//Linear-constrain circle anti-aliased algorithm.
//Copyright (c) 2011 Konstantin Kirillov
//License: MIT
/*
A l g o r i t h m ` s b r i e f d e s c r i p t i o n
Circle is a solution of constraint F=0 where
function F(x,y)=R^2 - x^2 - y^2.
When moving from x=R, y=0 till y=R/2 we
1. change x-- when F becomes <0
2. we calculate intensities I1, I2 of neighbour pixels assuming
that I1/I2 ~ DF1/DF2 at fixed y.
Following notations are used in program:
E=R^2-y^2 ( "available excess" )
x - point on the left from circle
xTop - x+1, point to the right from circle
L - "low difference", L=E-x^2 =DF1
U - "upper difference", U=(x+1)^2-E =-DF2
u - intensity "contributed" by difference from upper node
l - intensity "contributed" by lower node
I - summary intensity I=u+l of both left and right pixels
(2) implies u/l=U/L
u=IU/(U+L)
We must assign u to the left pixel and l to the right.
End of second algorithm.
*/
import java.applet.Applet;
import java.awt.*;
public class NoSqrt extends Applet{
//==========================================================================
//Algorithm:
//--------------------------------------------------------------------------
//Principal parameters:
int I=255; //Intensity range. Determines algorithms' accuracy.
//----------------------------------------------------------------
// Calculation of an arc
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//No precalculation is required.
//Calculation of the 1/8 of circle will take
// R/sq(2) steps = R/sq(2)*(3mult+1div+8add) ~ 1.4R(3mult+1div)
// All operations are of integer type.
//Input: uses precalculated variables D and I.
public void drawArch( int R ) {
int R2=R*R;
int y=0;
int x=R;
int B=x*x;
int xTop=x+1;
int T=xTop*xTop;
while( y<x ) {
int E=R2-y*y;
int L=E-B;
int U=T-E;
if(L<0){ //We had Wu's lemma before: if( dnew < d ) x--;
xTop=x;
x--;
T=B;
U=-L;
B=x*x;
L=E-B;
}
int u=I*U/(U+L);
//good for debug:
con("x="+x+" y="+y+" E="+E+" B="+B+" T="+T+" L="+L+" U="+U+" u="+u);
//These two statements are not a part of the algorithm:
//Each language, OS, or framework has own ways to put a "pixel".
putpixel(x, y, u, doDemo);
putpixel(xTop, y, (I-u), !doDemo);
y++;
}
}
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Calculation of an arc
//----------------------------------------------------------------
//----------------------------------------------------------------
//End of Algorithm.
//==========================================================================
/////////////////////////////////////////////////////////////////////////////
// DEMO
//
// The rest of this file is an application of above code.
// It is done in form of Java applet to make above code
// the part of a live demo.
// Radius R can be set in index.htm file.
//==========================================================================
//Test:
int R=20; //Radius.
//Platform specific graphics auxiliary.
Dimension scrDimension;
Image img;
Graphics g;
boolean imageIsReady = false;
//Graphics Aux:
int xCenter = 5;
int yCenter;
int squareSize = 14;
//Demonstration
boolean doDemo = true;
int lightBackground = 0;
Color realCurveColor = new Color( 255,0,0 );
//This is a standard method used to initialize an applet:
public void init(){
//Preparation:
try{ String s=getParameter("Radius"); if( s != null && s != "" ) R = Integer.parseInt(s); }catch( Exception e ) {};
scrDimension = new Dimension( (squareSize*R+400), (squareSize*R+200) );
yCenter = R * 12 / 10;
setSize(scrDimension);
img = createImage( scrDimension.width, scrDimension.height );
g = img.getGraphics();
//Algorithm Principal:
con( "initRoot" );
setImageBackground(255);
con("DrawArch");
drawArch(R);
drawCoodinateLines(R);
if(doDemo) drawRealCircleInDemo(R);
imageIsReady = true;
//con("repaint");
repaint();
}
public void paint( Graphics g ) {
//con("update. " + "imageIsReady=" + imageIsReady + " image=" + img);
if( imageIsReady && img != null ) {
con( "draw image" );
//Move result image to master image:
g.drawImage( img, 0,0, null );
}
}
private void putpixel( int x, int y, int intensity, boolean addDescription ){
//Demo Circle:
con("put: x=" + x + " y=" + y + " i=" + intensity);
int i = lightBackground == 1 ? I - intensity : intensity;
g.setColor( new Color( i, i, i ) );
int xScr = (xCenter+x)*squareSize;
int yScr = (yCenter-y)*squareSize;
g.fillRect( xScr, yScr, squareSize, squareSize);
g.setColor(realCurveColor);
int sQ2 = squareSize/2;
if(addDescription) g.drawString( "x=" + x + "," + ((float)Math.sqrt(R*R-y*y)) + "," + (x+1) + " y=" + y + " i=" + intensity + "," + (I-intensity), xScr+3*squareSize, yScr+sQ2);
//Real Circle:
int rX = xCenter*squareSize + sQ2 + x;
int rY = yCenter*squareSize + sQ2 - y;
g.setColor(new Color(i,i,i));
g.drawLine( rX, rY, rX, rY );
}
private void setImageBackground(int background){
int xSize = scrDimension.width;
int ySize = scrDimension.height;
int c = background*lightBackground;
g.setColor( new Color(c,c,c) );
g.fillRect( 0, 0, xSize, ySize );
}
private void drawCoodinateLines(int R){
g.setColor(new Color(0,0,255));
int sQ2 = squareSize/2;
int x1 = xCenter*squareSize+sQ2;
int x2 = (xCenter + R)*squareSize+sQ2;
int y1 = yCenter*squareSize+sQ2;
int y2 = (yCenter-R)*squareSize+sQ2;
g.drawLine( x1, y1, x2, y1 ); //Axis x.
g.drawLine( x1, y1, x1, y2 ); //Axis y.
g.drawString( "Intensity=" + I + " Radius=" + R, x1 + 40, y1 + 20);
}
private void drawRealCircleInDemo( int R ){
g.setColor(realCurveColor);
int sQ2 = squareSize/2;
int sXCenter = xCenter*squareSize;
int sYCenter = yCenter*squareSize;
int sR=R*squareSize;
int x=sR;
int y=0;
while(y<x){
x = (int) Math.sqrt((double)(sR*sR-y*y));
int xC = sXCenter+x+sQ2;
int yC = sYCenter-y+sQ2;
g.drawLine(xC,yC,xC,yC);
y++;
}
}
public static void prn( Object ob ){
System.out.println( ob );
}
static public void con( Object ob) {
String s1 = " " + System.currentTimeMillis();
int wLen = s1.length();
s1 = s1.substring( wLen - 7, wLen-1 );
String s2 =Thread.currentThread().getName() + " ";
s2 = s1 + " \"" + s2.substring ( 0, 20 ) + "\" " + ob;
System.out.println(s2);
}//con
//===========================================================================
// END OF DEMO
/////////////////////////////////////////////////////////////////////////////
}
Copyright (C) 2011 Konstantin Kirillov. MIT License