/* Homework 3
 * CS 506 Fall 2006
 * Hans Fugal
 */

import java.awt.*;
import javax.swing.*;

/* Problem:  You are to write a triangle filling algorithm.
 *           The only  graphics call(other than setColor) you are allowed to
 *           use at this time is page.drawLine(x1,y1,x2,y2). You may use
 *           fillOval and drawoval to make an interesting image, but not as a
 *           part of your fill triangle routine.
 */
public class hw3 extends JApplet
{
    private Graphics page;

    public void init()
    {
        setBackground(Color.gray);
        setForeground(Color.black);
        setSize(600,600);
    }

    public void paint(Graphics g)
    {
        page = g;
        fill_triangle(300,250,295,50,305,20);
        fill_triangle(305,250,315,50,325,50);
        fill_triangle(350,300,450,295,495,280);
        fill_triangle(350,320,450,315,450,330);
    }

    public static void main(String s[])
    {
        JFrame f = new JFrame("Homework 3 - Hans Fugal");
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        JApplet applet = new hw3();
        f.getContentPane().add("Center", applet);
        applet.init();
        f.pack();
        f.setSize(new Dimension(610,630));
        f.setVisible(true);
    }

    void fill_triangle(int x1, int y1, int x2, int y2, int x3, int y3)
    {
        int t;

        // find maxes and mins
        int xmin, xmax, ymin, ymax;
        xmin = xmax = x1;
        if (x2 < xmin)
            xmin = x2;
        if (x3 < xmin)
            xmin = x3;
        if (x2 > xmax)
            xmax = x2;
        if (x3 > xmax)
            xmax = x3;
        ymin = ymax = y1;
        if (y2 < ymin)
            ymin = y2;
        if (y3 < ymin)
            ymin = y3;
        if (y2 > ymax)
            ymax = y2;
        if (y3 > ymax)
            ymax = y3;

        // determine whether steep, and if not swap xs and ys
        boolean unsteep = (ymax-ymin) < (xmax-xmin);
        if (unsteep)
        {
            t = x1;
            x1 = y1;
            y1 = t;

            t = x2;
            x2 = y2;
            y2 = t;

            t = x3;
            x3 = y3;
            y3 = t;
        }

        // sort points by y
        if (y1 > y3)
        {
            t = x1;
            x1 = x3;
            x3 = t;

            t = y1;
            y1 = y3;
            y3 = t;
        }
        if (y1 > y2)
        {
            t = x1;
            x1 = x2;
            x2 = t;

            t = y1;
            y1 = y2;
            y2 = t;
        }
        if (y2 > y3)
        {
            t = x2;
            x2 = x3;
            x3 = t;

            t = y2;
            y2 = y3;
            y3 = t;
        }

        // precalculations
        int l,r;                // left and right x extents
        int fl,fr;              // fraction
        int dxl,dyl,dxr,dyr;    // deltas
        int sl,sr;              // sign of slope (-1 or +1)
        l = r = x1;
        boolean x2_left = ((x2-x1) < (y2-y1)*(x3-x1)/(y3-y1));
        if (x2_left)
        {
            dxl = x2-x1;
            dyl = y2-y1;
            dxr = x3-x1;
            dyr = y3-y1;
        }
        else
        {
            dxl = x3-x1;
            dyl = y3-y1;
            dxr = x2-x1;
            dyr = y2-y1;
        }
        sl = (dxl < 0 ? -1 : 1);
        sr = (dxr < 0 ? -1 : 1);
        fl = sl*dyl;
        fr = 0;

        // fill from y1 to y2
        if (y1 == y2)
            if (unsteep)
                page.drawLine(y1,x1,y2,x2);
            else
                page.drawLine(x1,y1,x2,y2);
        else
        {
            for (int y=y1; y<=y2; y++)
            {
                if (r<l)r=l;
                if (unsteep)
                    page.drawLine(y,l,y,r);
                else
                    page.drawLine(l,y,r,y);

                if (y == y2) // don't calculate the next extents if we're done
                    break;

                // left edge scan
                fl += dxl;
                while (Math.abs(fl) > dyl)
                {
                    fl -= sl*dyl;
                    l += sl;
                }

                // right edge scan
                fr += dxr;
                while (Math.abs(fr) >= dyr)
                {
                    fr -= sr*dyr;
                    r += sr;
                }
            }
        }

        // fill from y2 to y3
        if (y2 == y3)
            if (unsteep)
                page.drawLine(y2,x2, y3,x3);
            else
                page.drawLine(x2,y2, x3,y3);
        else
        {
            if (x2_left)
            {
                dxl = x3-x2;
                dyl = y3-y2;
                sl = (dxl < 0 ? -1 : 1);
                fl = 0;
                l = x2;
            } else {
                dxr = x3-x2;
                dyr = y3-y2;
                sr = (dxr < 0 ? -1 : 1);
                fr = 0;
                r = x2;
            }

            for (int y=y2; y<=y3; y++)
            {
                if (r<l)r=l;
                if (unsteep)
                    page.drawLine(y,l,y,r);
                else
                    page.drawLine(l,y,r,y);

                // left edge scan
                fl += dxl;
                while (Math.abs(fl) > dyl)
                {
                    fl -= sl*dyl;
                    l += sl;
                }

                // right edge scan
                fr += dxr;
                while (Math.abs(fr) >= dyr)
                {
                    fr -= sr*dyr;
                    r += sr;
                }
            }
        }
    }
}