/*
 * ビジュアル情報処理論
 *    1. bucket sort による走査線変換
 *  Programmed by Yoshizumi TANAKA. 1998/7
 *
 * *Button*
 *  Paint Stert. … 白線で表示されている図形の内部を塗りつぶします。
 *
 * 凹多角形を含む多角形の内部を塗りつぶします。
 *  (1) クリックで点を選んでいきます。
 *  (2) [Paint Stert.] ボタンで白線で表示されている図形の内部を塗りつぶします。
 *  (3) もう一度クリックすると画面がクリアされます。
 *   * 最大で 31 (= Poly.N - 1) 角形まで描けます。
 *
 */


import java.applet.*;
import java.awt.*;

public class ScanConversion extends Applet {
    Vertex v;
    int status;
    Button b;
    
    static final int EMPTY    = 0;
    static final int DRAWING  = 1;
    static final int COMPLETE = 2;

    public void init() {
        setBackground(Color.black);
        setForeground(Color.white);
    
        add(b = new Button("Paint Stert."));
    
	v = new Vertex();
	status = EMPTY;
    }
    public void paint(Graphics g) {
        showStatus("status="+status+", v.n="+v.n);
	if (status == DRAWING) {
	    v.newLine(g);
	} else if (status == COMPLETE) {
	    v.lastLine(g);
	    BucketSort bs = new BucketSort(v);
	    g.setColor(Color.red);
	    bs.paint(g);
	}
    }
    public boolean action(Event e, Object o) {
        if (e.target == b) {  // Paint Stert.
	    if (status == COMPLETE || v.n < 3) {
	        return false;
	    }
	    status = COMPLETE;
	    repaint();
	    return true;
	} else {
	    return false;
	}
    }
    public boolean mouseDown(Event e, int x, int y) {
	if (status == EMPTY || status == DRAWING) {
	    status = DRAWING;
	    v.newPoint(x, y);
	    repaint();
	    return true;
	} else if (status == COMPLETE) {
	    v.n = 0;
	    status = EMPTY;
	    repaint();
	    return true;
	} else {
	    return false;
	}
    }
} // end of class ScanConversion

class BucketSort {
    final int Y_MAX = 400;

    Bucket bucket[] = new Bucket[Y_MAX];
    ActiveTable at = new ActiveTable();

    int x[];
    int n;

    BucketSort(Vertex v) {
        double m_inv;
	x = new int[v.n];

	for (int line = 0; line < Y_MAX; line++) {
	    bucket[line] = new Bucket();
	}
        for (int i = 0; i < v.n; i++) {
            if (v.y[i] < v.y[i+1]) {
                m_inv = (double)(v.x[i]-v.x[i+1])/(v.y[i]-v.y[i+1]);
		bucket[v.y[i]].insert(v.x[i], v.y[i+1], m_inv);
            } else if (v.y[i] > v.y[i+1]) {
                m_inv = (double)(v.x[i]-v.x[i+1])/(v.y[i]-v.y[i+1]);
		bucket[v.y[i+1]].insert(v.x[i+1], v.y[i], m_inv);
	    }
	}
    }
    void paint(Graphics g) {
	for (int line = 0; line < Y_MAX; line++) {
	    n = 0;
	    at.remove(at, line);
	    if (bucket[line].next != null) {
		at.add(at, bucket[line].next);
	    }
	    if (at.next != null) {
		at.xSort(at, at.next, at);
		makeLineBuffer(at.next);
		for (int i = 0; i < n; i += 2) {
		    g.drawLine(x[i], line, x[i+1], line);
		}
		at.xRenew(at.next);
	    }
	}
    }
    void makeLineBuffer(EdgeTable at) {
	if (at != null) {
	    x[n] = (int)at.x_now;
	    n++;
	    makeLineBuffer(at.next);
	}
    }
} // end of class BucketSort	

class List {
    EdgeTable next;

    List() {}
} // end of class List

class Bucket extends List {
    Bucket() {}
    void insert(int x_min, int y_max, double m_inv) {
	EdgeTable tmp = next;
	next = new EdgeTable(x_min, y_max, m_inv);
	next.next = tmp;
    }
} // end of class Bucket

class ActiveTable extends List {
    ActiveTable() {}
    void add(List at, EdgeTable et) {
        if (at.next == null) {
	    at.next = et;
	} else {
	    add(at.next, et);
	}
    }
    void remove(List at, int line) {
	if (at.next != null) {
	    if (line >= at.next.y_max) {
		at.next = at.next.next;
		remove(at, line);
	    } else {
		remove(at.next, line);
	    }
	}
    }
    void xSort(List root, List to_header, List to_min) {
	if (root.next != null) {
	    if (to_header.next == null) {
		if (root.next == to_min.next) {
		    xSort(root.next, root.next.next, root.next);
		} else {
		    EdgeTable tmp = root.next;
		    root.next = to_min.next;
		    to_min.next = to_min.next.next;
		    root.next.next = tmp;
		    xSort(root.next, root.next.next, root.next);
		}
	    } else {
		if (to_min.next.x_now > to_header.next.x_now) {
		    xSort(root, to_header.next, to_header);
		} else {
		    xSort(root, to_header.next, to_min);
		}
	    }
	}
    }
    void xRenew(EdgeTable et) {
	if (et != null) {
	    et.x_now += et.m_inv;
	    xRenew(et.next);
	}
    }
} // end of class ActiveTable

class EdgeTable extends List {
    int x_min, y_max;
    double m_inv, x_now;

    EdgeTable() {}
    EdgeTable(int xmin, int ymax, double minv) {
        x_min = xmin;
        y_max = ymax;
        m_inv = minv;
	x_now = (double)xmin;
    }
} // end of class EdgeTable

class Vertex {
    final int N = 32;
    int n;
    int x[] = new int[N];
    int y[] = new int[N];
  
    Vertex() {}
    void newPoint(int new_x, int new_y) {
        if (n >= N-1)
	    System.err.println("Vertex > too many points");
	x[n] = new_x;
	y[n] = new_y;
	n++;
    }
    void newLine(Graphics g) {
	for (int i = 0; i < n-1; i++) {
	    g.drawLine(x[i], y[i], x[i+1], y[i+1]);
	}
    }
    void lastLine(Graphics g) {
	x[n] = x[0];
	y[n] = y[0];
	for (int i = 0; i < n; i++) {
	    g.drawLine(x[i], y[i], x[i+1], y[i+1]);
	}
    }
} // end of class Vertex