/** A demonstration of a non-parametric circle drawing algorithm
 * using the same ideas as the famous Bresenham line algorithm.
 * Demonstration code used for teaching.
 * <p>
 * Distributed under the Gnu General Public
 * License (GPL). See www.gnu.org for details.
 * <p>
 * @version 20 aug 2003
 * @author Stefan Gustavson (stegu76@liu.se)
 */

import java.applet.*;
import java.awt.*;
import java.awt.image.*;
import java.util.*;
import java.lang.*;

/** Applet to draw lots of circles to test the algorithm */
public class Circles extends Applet implements Runnable {
    Thread myThread;
    Image myImage;
    int width;
    int height;
    int pixels[];

    /** Set up the applet */
    public void init()
    {
		width = getSize().width;
		height = getSize().height;
		
		pixels = new int[width*height];
		for (int i=0; i<width*height; i++)
		    pixels[i]=0xff000000;
		
    }

/** Start the applet and render circles */
    public void run()
    {
		// Create an ImageSource, to supply pixel data to the image.
		MemoryImageSource source = new MemoryImageSource(width, height, pixels, 0, width);
	
		// Progressive update during rendering is actually a kind of animation
		source.setAnimated(true);
	
		// Create an Image taking its pixel data from the ImageSource
		myImage = createImage(source);
	
		int x0 = getWidth()/2; // Circle centerpoint
		int y0 = getHeight()/2;
		int R; // Circle radius
		int x, y; // The pixel plotting coordinates
		int d; // The decision variable, the main focus of this code
		int c; // A color for the pixel plotting
		
		for(R=10; R<=150; R+=5) {
	
/*
			// A straightforward and correct, but quite inefficient algorithm
			x = 0;
			y = R;
			c = packRGB(255,0,0);
			int d1, d2;
		
			while(x<=y) {
				pixels[(y0+y)*width+x0+x]=c;
				pixels[(y0+y)*width+x0-x]=c;
				pixels[(y0-y)*width+x0+x]=c;
				pixels[(y0-y)*width+x0-x]=c;
				pixels[(y0+x)*width+x0+y]=c;
				pixels[(y0+x)*width+x0-y]=c;
				pixels[(y0-x)*width+x0+y]=c;
				pixels[(y0-x)*width+x0-y]=c;
		
				x = x + 1;
				d1 = Math.abs(x*x + y*y - R*R);
				d2 = Math.abs(x*x + (y-1)*(y-1) - R*R);
				if (d2<d1)
					y = y - 1;
			    }
*/

/*
			// Midpoint algorithm with explicit calculation of decision variable dd
			x = 0;
			y = R;
				
			c = packRGB(0,0,255);
			double dd;
			
			while(x<=y) {
				pixels[(y0+y)*width+x0+x]=c;
				pixels[(y0+y)*width+x0-x]=c;
				pixels[(y0-y)*width+x0+x]=c;
				pixels[(y0-y)*width+x0-x]=c;
				pixels[(y0+x)*width+x0+y]=c;
				pixels[(y0+x)*width+x0-y]=c;
				pixels[(y0-x)*width+x0+y]=c;
				pixels[(y0-x)*width+x0-y]=c;
		
				x = x + 1;
				dd = x*x + y*y - y + 0.25 - R*R;
				if(dd>0.0)
					y = y - 1;
			    }
*/
	
			// Midpoint algorithm with incremental update of decision variable d
			x = 0;
			y = R; // Starting point
			d = 5-(R<<2); // Potential function scaled by 4 to have integer values
			c = packRGB((int)(Math.random()*200.0+56.0),
					(int)(Math.random()*200.0+56.0),
					(int)(Math.random()*200.0+56.0));
	
			while(x<=y) { // Keep going until we cross the line x=y
				pixels[(y0+y)*width+x0+x]=c; // Mirror (x,y) to all eight octants
				pixels[(y0+y)*width+x0-x]=c;
				pixels[(y0-y)*width+x0+x]=c;
				pixels[(y0-y)*width+x0-x]=c;
				pixels[(y0+x)*width+x0+y]=c;
				pixels[(y0+x)*width+x0-y]=c;
				pixels[(y0-x)*width+x0+y]=c;
				pixels[(y0-x)*width+x0-y]=c;
	
				x = x + 1; // Always take a step to the right
				if(d>0) {
						d = d + (x<<3) - (y<<3) + 12; // Update d
						y = y-1; // Take a step down when needed
					}
					else {
						d = d + (x<<3) + 4; // Update d
					}
		    	} // end while
	
				source.newPixels(0,0,width,height); // Lazy update: redraw the entire image
				repaint();
			} // end for
	}
	
    /** Convert (r, g, b) color values to a 32-bit integer ARGB color */
    private int packRGB(int r, int g, int b)
    {
		if(r>255) r = 255;
		if(g>255) g = 255;
		if(b>255) b = 255;

		return 0xff000000 | ((r&0xff)<<16) | ((g&0xff)<<8) | (b&0xff);
    }

    /** Start the run() thread to render the image */
    public void start()
    {
		if (myThread == null)
		{
			myThread = new Thread(this);
			myThread.start();
    	}
    }

    /** Stop the applet */
    public void stop()
    {
		myThread = null;
    }

    /** Update the graphics (simply invokes paint())
     @param g The graphics context
    */
    public void update(Graphics g)
    {
		paint(g);
    }

    /** Paint the graphics
     @param g The graphics context
    */
    public void paint(Graphics g)
    {
	if(myImage != null)
	    g.drawImage(myImage, 0, 0, width, height, this);
    }

    /** Provide some information about the applet */
    public String getAppletInfo() 
    {
	return "Midpoint algorithm circle drawing demo\nimplemented by Stefan Gustavson\n(stegu76@liu.se) 2003\nDistributed under the Gnu GPL\n(see http://www.gnu.org for details)";
    }
}