public class Algorithm extends Demo{
public String title="Anti-aliased implicit curve linear algorithm";
public String version="0.0.18";
public String description="Intended for convex curves traversed in counter-clock-wise direction";
public String copyright="Copyright (c) 2011 Konstantin Kirillov. License MIT.";
public String date="October 4, 2011";
//Updates Tangent turn condition changed. No "empirical" right shift.
// Right neighbor possibly accumulates intensity from next step and printed then.
// Version 0.0.9 Approach: iPast +=l;
// Version 0.0.10 Approach: iPast +=(iPast+l)/2;
// Version 0.0.11 Refactored : Algorithm is a child of Demo.
// Version 0.0.12 Changing neighbor shade.
// Version 0.0.13 Project structure fixed
// Version 0.0.15 Using R-Function f=min(x,y)
// Version 0.0.16 GUI-based curve selection
// Version 0.0.17 Project refactored
// Version 0.0.18 Comments restructured
//TODO easy: fill internals of the curve with Imax to make demo of "figure". Shift its picture to the right.
// half-lighted internal bars will have Imax also.
// add medium circle in red
//Intensity range:
int I=255;
int IMAX=I;
//Auxilary variable. Tangent:
int[][] T= {
{ 0, 1 },
{ -1, 1 },
{ -1, 0 },
{ -1,-1 },
{ 0,-1 },
{ 1,-1 },
{ 1, 0 },
{ 1, 1 }
};
//================================================================
//Algorithm
//----------------------------------------------------------------
public void drawCurve( ) {
//Initials
int x0=curve.x0;
int y0=curve.y0;
int t=0; //Tangent
int x=x0;
int y=y0;
int xPast=x0+1;
int yPast=y0;
int iPast=0;
int right=6;
int rightX=T[right][0];
int rightY=T[right][1];
//To protect against infinite loop
//when developing an algorithm:
curve.iterationsCounter=0;
while(t<7 || y<=y0 ) {
int course=t%8;
con("");
con("p=("+x+","+y+") course="+t+"("+T[course][0]+","+T[course][1]+")");
if(curve.outOfLimits(x,y))break;
int courseX=T[course][0];
int courseY=T[course][1];
int x2=x+courseX;
int y2=y+courseY;
int F=curve.constraint(x2,y2);
if(F<0){
con("failed right policemen: p=("+x2+","+y2+") F="+F);
course=(t+1)%8;
courseX=T[course][0];
courseY=T[course][1];
x2=x+courseX;
y2=y+courseY;
F=curve.constraint(x2,y2);
con("went with left policemen: p=("+x2+","+y2+") course="+course+"=("+courseX+","+courseY+") F="+F);
if(F<0){
t++;
con("CHANGING PRIMARY COURSE. to "+t+"("+courseX+","+courseY+")");
course=(course+1)%8;
courseX=T[course][0];
courseY=T[course][1];
x2=x+courseX;
y2=y+courseY;
F=curve.constraint(x2,y2);
if(course/2*2==course){
right=(course+6)%8;
rightX=T[right][0];
rightY=T[right][1];
}
if( F<0 ) continue;
}
}
int xRight=x2+rightX;
int yRight=y2+rightY;
int FRight = curve.constraint(xRight,yRight);
int L=F;
//Not very consistent:
int U=FRight<0 ? -FRight : 0;
int u=I*U/(U+L);
int l=I-u;
//Merge intensity of past point:
//Apparently, this is useless when right direction is along x.y axes:
if(xRight==xPast && yRight==yPast){
con("current past ("+xPast+","+yPast+") iPast="+iPast+" will be mixed with l="+l);
//iPast += l; //This works also.
iPast =(iPast+l)/2;
if(iPast>IMAX)iPast=IMAX;
}
//good for debug:
con("course=(" + courseX+","+courseY+") led to F("+x2+","+y2+")*"+u+", ("+xRight+","+yRight+")with l=*"+ l +
" l="+l+" L="+L+" U="+U+" FRight="+FRight+" right direction="+right+"=("+rightX+","+rightY+")");
//These two statements are not a part of the algorithm:
//Each language, OS, or framework has own ways to put a "pixel".
putpixel(x2, y2, u, doDemo, xPast, yPast, iPast);
putpixel(xPast, yPast, iPast, !doDemo, xPast, yPast, iPast);
if(xRight!=xPast || yRight!=yPast) iPast=l;
xPast=xRight;
yPast=yRight;
x=x2;
y=y2;
}
con("eoj. putting past=("+xPast+","+yPast+")*"+iPast);
putpixel(xPast, yPast, iPast, !doDemo, xPast, yPast, iPast);
}// while( ....
//----------------------------------------------------------------
//End of Algorithm
//================================================================
Curve curve;
class Curve{
public String description="";
public int R;
public int A;
public int B;
public int x0;
public int y0;
int yLimitMax=100;
int yLimitMin=-100;
int xLimitMax=100;
int xLimitMin=-100;
int iterationsLimit=1000;
//Aux: infinite loop protector:
public int iterationsCounter=0;
public int constraint(int x, int y){
return -1;
}
public boolean outOfLimits(int x, int y){
if(iterationsCounter++>iterationsLimit)return true;
return (x>xLimitMax || x<xLimitMin || y>yLimitMax || y<yLimitMin );
}
}
/////////////// Test curves: ////////////////////
class Ellipse extends Curve{
Ellipse(int R,int A,int B){
this.R=R;
this.A=2;
this.B=B;
x0=R/A;
y0=0;
this.description=" Ellipse. R="+R;
}
public int constraint(int x, int y){
return R*R - A*A*x*x - B*B*y*y;
}
}
class Line extends Curve{
int C;
Line(int A, int B, int C, int y0){
this.A=A;
this.B=B;
this.C=C;
this.y0=y0;
x0=(-constraint(0,y0))/A-1;
this.description="Line";
}
public int constraint(int x, int y){
return A*x+B-C*y;
}
}
class LineAndEllipse extends Curve{
int C;
Ellipse el;
Line ln;
LineAndEllipse(int R, int A, int B, int ALine, int BLine, int CLine){
this.R=R;
this.A=A;
this.B=B;
x0=R/A;
y0=0;
el = new Ellipse(R,A,B);
ln = new Line(ALine, BLine, CLine, -1000);
this.description=" Line and Ellipse. R="+R;
}
public int constraint(int x, int y){
int a=el.constraint(x, y);
int b=ln.constraint(x, y);
return Math.min(a,b);
}
}
/////////////// Test curves end ////////////////////
public Algorithm(){ super.child=this; generateCurvesArray(); con("child supplied"); }
Curve[] curves;
public void generateCurvesArray(){
Curve[] curves = {
new Line(-1,10,4,-6),
new Ellipse(16,2,1),
new LineAndEllipse(16,2,1,-1,10,2)
};
//Enumerate descriptions for GUI:
for(int i=0; i<curves.length; i++){
curves[i].description = (i+1) +". "+ curves[i].description;
}
this.curves = curves;
con("In generate Crv. child="+child);
}
/////////////// Demo cases: ////////////////////
protected void supplyParameters(int curveIndex){
con("in child supply pars. child="+child+" curveIndex="+curveIndex);
//Select here which curve to draw:
curve=curves[curveIndex];
super.I=this.I;
super.description=curve.description;
}
}
Copyright (C) 2011 Konstantin Kirillov. MIT License