Графические алгоритмы Брезенхема

Графические алгоритмы Брезенхема - это семейство алгоритмов, позволяющих
рисовать линии и окружности в растре с применением только целочисленной
логики. Т.е. дробные числа в алгоритмах отсутствуют. Ниже приведена
программа на Java, содержащая 5 различных вариантов алгоритмов - три
алгоритма для рисования линий, и два - для рисования окружностей. Алгоритмы
отличаются лишь способом расчета смещения в процессе рисования, а линии
line_s4 и line_s8 - имеют 4-х точечную связанность и 8-ми точечную
соответственно. Существуют и более серьезные реализации алгоритмов
Брезенхема, позволяющие рисовать линии с учетом психологии их наблюдения -
т.е. сглаживать наиболее выделяющиеся углы смещений с помощью палитры цветов.

import java.lang.*;
import java.awt.*;
import java.awt.event.*;
 
public class TestCanvas extends Canvas {

    static final int SIZE_X=600;
    static final int SIZE_Y=500;

    private void line_s4(Graphics g, int x1, int y1, int x2, int y2, Color col) {
        int x = x1, y = y1;
        int dx = Math.abs(x2-x1), dy = Math.abs(y2-y1);
        int sx = (x2-x1)>0?1:((x2-x1)==0?0:-1);
        int sy = (y2-y1)>0?1:((y2-y1)==0?0:-1);
        int e = 2*dy-dx;
        boolean change=false;
        if (dy>dx) {
            int z=dx; dx=dy; dy=z;
            change=true;
        }
        g.setColor(col);
        g.drawLine(x, y, x, y);
        for(int k=1; k<=(dx+dy); k++) {
            if (e<dx) {
                if (change) y+=sy; else x+=sx;
                e += 2*dy;
            }
            else {
                if (change) x+=sx; else y=y+sy;
                e -= 2*dx;
            }
            g.drawLine(x, y, x, y);
        }
    }
    
    private void line_s8(Graphics g, int x1, int y1, int x2, int y2, Color col) {
        int x = x1, y = y1;
        int dx = Math.abs(x2-x1), dy = Math.abs(y2-y1);
        int sx = (x2-x1)>0?1:((x2-x1)==0?0:-1);
        int sy = (y2-y1)>0?1:((y2-y1)==0?0:-1);
        boolean change = false;
        if (dy>dx) {
            int z=dx; dx=dy; dy=z;
            change=true;
        }
        int e = 2*dy-dx;
        g.setColor(col);
        for(int k=1; k<=(dx+dy); k++) {
            g.drawLine(x, y, x, y);
            while(e>=0) {
                if (change) x+=sx; else y+=sy;
                e = e - 2*dx;
            }
            if (change) y+=sy; else x+=sx;
            e = e + 2*dy;
        }
        g.drawLine(x, y, x, y);
    }    
    
    private void line_x(Graphics g, int x1, int y1, int x2, int y2, Color col) {
        int x = x1, y = y1;
        int dx = Math.abs(x2-x1), dy = Math.abs(y2-y1);
        int sx = (x2-x1)>0?1:((x2-x1)==0?0:-1);
        int sy = (y2-y1)>0?1:((y2-y1)==0?0:-1);
        int tx, ty;
        if (dx>=dy) {
            tx = sx; ty = 0;
        } else {
            int z=dx; dx=dy; dy=z;
            tx=0; ty=sy;
        }
        g.setColor(col);
        int scount = 2*dy;
        int count = scount-dx;
        int dcount = count-dx;
        for(;;) {
            dx-=1;
            if (dx<-1) break;
            g.drawLine(x, y, x, y);
            if (count>=0) {
                x+=sx; y+=sy;
                count += dcount;
            } else {
                x+=tx; y+=ty;
                count += scount;
            }
        }
    }

    private void circle_a(Graphics g, int x, int y, int r, Color col) {
        int sx=0;
        int sy=r;
        int d=3-2*r;
        g.setColor(col);
        while(sx<=sy) {
            g.drawLine(x+sx, y-sy, x+sx, y-sy);
            g.drawLine(x+sx, y+sy, x+sx, y+sy);
            g.drawLine(x-sx, y-sy, x-sx, y-sy);
            g.drawLine(x-sx, y+sy, x-sx, y+sy);

            g.drawLine(x+sy, y+sx, x+sy, y+sx);
            g.drawLine(x-sy, y+sx, x-sy, y+sx);
            g.drawLine(x+sy, y-sx, x+sy, y-sx);
            g.drawLine(x-sy, y-sx, x-sy, y-sx);
            
            if (d<0) {
                d = d + 4 * sx + 6;
            } else {
                d = d + 4 * (sx - sy) + 10;
                sy = sy - 1;
            }
            sx += 1;   
        }
    }
    
    private void circle_b(Graphics g, int x, int y, int r, Color col) {
        g.setColor(col);
        int sx = 0;
        int sy = r;
        int d = 2*(1-r);
        int limit = 1;
        int sigma;
        for(;;) {
            g.drawLine(x+sx, y-sy+1, x+sx, y-sy+1);
            g.drawLine(x+sx, y+sy, x+sx, y+sy);
            g.drawLine(x-sx, y-sy+1, x-sx, y-sy+1);
            g.drawLine(x-sx, y+sy, x-sx, y+sy);
            if (sy<=limit) break;
            if (d<0) {
                sigma = 2*d+2*sy-1;
                if (sigma<=0) {
                    sx+=1;
                    d=d+2*sx+1;
                } else if (sigma>0) {
                    sx+=1;
                    sy-=1;
                    d=d+2*sx-2*sy+2;
                }
            } else if (d>0) {
                sigma = 2*d+2*sx-1;
                if (sigma<=0) {
                    sx+=1;
                    sy-=1;
                    d=d+2*sx-2*sy+2;
                }
                else if (sigma>0) {
                    sy-=1;
                    d=d-2*sy+1;
                }
            } else if (d==0) {
                sx+=1;
                sy-=1;
                d=d+2*sx-2*sy+2;
            }
        } // for
        g.drawLine(x+sx, y-sy, x+sx, y-sy);
        g.drawLine(x-sx, y-sy, x-sx, y-sy);
    }
    
    private int rndX() {
        return (int)(Math.random()*getWidth()-40)+20;
    }
    
    private int rndY() {
        return (int)(Math.random()*getHeight()-40)+20;
    }

    private int rndR() {
        return (int)(Math.random()*Math.min(getWidth(),getHeight())/3);
    }

    public void paint(Graphics g) {
        g.fillRect(0, 0, getWidth()-1, getHeight()-1);
        g.setColor(Color.RED);
        g.drawRect(0, 0, getWidth()-1, getHeight()-1);
        for(int i=0;i<3;i++)
            line_s4(g, rndX(), rndY(), rndX(), rndY(), Color.ORANGE);
        for(int i=0;i<3;i++)
            line_s8(g, rndX(), rndY(), rndX(), rndY(), Color.GREEN);
        for(int i=0;i<3;i++)
            line_x(g, rndX(), rndY(), rndX(), rndY(), Color.BLUE);
        int x = 10;
        for(int r=2;r<40;r+=3) {
            circle_a(g, x, getHeight()/3, r, Color.PINK);
            x+=r+r+5;
        }
        x=10;
        for(int r=2;r<40;r+=3) {
            circle_b(g, x, getHeight()/3*2, r, Color.RED);
            x+=r+r+5;
        }
    }
 
    public static void main(String arg[]) {
        final Frame f = new Frame("Test frame");
        f.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                f.dispose();
            }
        });
        f.setSize(SIZE_X, SIZE_Y);
        f.add(new TestCanvas());
        f.setVisible(true);
    }
}