//	Binary space partition tree for Think Tank simulation
//
//	Author	Matthew Caryl
//	Created 17.11.96
//
//	All polygons given to this class should be simple closed clockwise polygons each with identical first and last polygons.
//	Each polygon must also have integer separation, both horizontal and verticle, between points.
//
//	Not all polygon spaces will work.  I think there are problems with coincident lines.
//
//  Although under copywrite to the author (Matthew Caryl) this code can be copied and modified for non-commercial
//  purposes as long as any derivatives contain this condition.

package ADT;

import java.awt.Graphics;
import java.awt.Polygon;
import java.awt.Rectangle;
import java.awt.Point;
import java.io.StreamTokenizer;
import java.io.InputStream;
import java.io.IOException;
import java.lang.Math;

public final class BSPT {
	private Node		tree;
	private Polygon[]	polygons;
	
	public BSPT(Polygon[] p) {
		polygons = p;
		
		Queue	lines = new Queue();
		
		// break polygons up into lines
		for (int l = polygons.length - 1; l >= 0; l--) {
			Polygon	q = polygons[l];
			int[]	xs = q.xpoints;
			int[]	ys = q.ypoints;
			
			for (int k = q.npoints - 1; k >= 1; k--)
				lines.enqueue(new Line(xs[k], ys[k], xs[k - 1], ys[k - 1]));
				// order of points is important, determines inside from outside
			}
		tree = make(lines);
		}
	
	public Polygon[] polygons() {
		return polygons;
		}
	
	public void draw(Graphics g) {
		for (int i = polygons.length - 1; i >= 0; i--)
			g.drawPolygon(polygons[i]);
		}
	
	public boolean in(int x, int y) {
		return tree.in(x, y);
		}
	
	public boolean in(int x, int y, int radius) {
		return tree.in(x, y, radius);
		}
	
	public boolean in(int x1, int y1, int x2, int y2) {
		return tree.in(x1, y1, x2, y2);
		}
	
	public boolean in(Rectangle rect) {
		return tree.in(rect);
		}
	
	public boolean in(int[][][] outline) {
		return tree.in(outline);
		}
	
	public float angle(int x, int y, int radius) {
		return tree.angle(x, y, radius);
		}
	
	public static Polygon[] parsePolygons(InputStream is, int width, int height) throws IOException {
		try {
			StreamTokenizer	st = new StreamTokenizer(is);
			boolean			eof = false;
			Queue			polygonQueue = new Queue();
			Queue			xQueue = new Queue();
			Queue			yQueue = new Queue();
			int				state = 0;
			
			st.eolIsSignificant(true);
			st.commentChar('#');
			st.ordinaryChars('(',',');
			while (!eof) {
				switch (st.nextToken()) {
					default:
						if (state == 0 & st.ttype == '(')
							state = 1;
						else if (state == 2 & st.ttype == ',')
							state = 3;
						else if (state == 4 & st.ttype == ')')
							state = 0;
						else
							throw new IOException("malformed polygon file");
						break;
					case StreamTokenizer.TT_NUMBER:
						if (state == 1) {
							xQueue.enqueue(new Integer((int) (width * st.nval / 100)));
							state = 2;
							}
						else if (state == 3) {
							yQueue.enqueue(new Integer((int) (height * st.nval / 100)));
							state = 4;
							}
						else 
							throw new IOException("malformed polygon file");
						break;
					case StreamTokenizer.TT_EOL:
						if (state != 0)
							throw new IOException("malformed polygon file");
						
						int		size = xQueue.size();
						int[]	xs = new int[size + 1];
						int[]	ys = new int[size + 1];
						
						for (int i = 0; i < size; i++) {
							xs[i] = ((Integer) xQueue.dequeue()).intValue();
							ys[i] = ((Integer) yQueue.dequeue()).intValue();
							}
						xs[size] = xs[0];
						ys[size] = ys[0];
						polygonQueue.enqueue(new Polygon(xs, ys, size + 1));
						
						
						break;
					case StreamTokenizer.TT_EOF:
						eof = true;
						break;
					case StreamTokenizer.TT_WORD:
						throw new IOException("malformed polygon file");
					}
				}
			is.close();
			
			if (state != 0)
				throw new IOException("malformed polygon file");
			
			int			size = polygonQueue.size();
			Polygon[]	polygons = new Polygon[size];
			
			for (int i = 0; i < size; i++)
				polygons[i] = (Polygon) polygonQueue.dequeue();
		
			return polygons;
			}
		catch (QueueEmpty e) {
			throw new IOException("report to programmer");
			}
		}
	
	private TreeNode make(Queue lines) {
		try {
			if (lines.empty())
				return null;
			else {
				Line	root, current;
				Queue	back, front;
				
				root = (Line) lines.dequeue();
				back = new Queue();
				front = new Queue();
				while (!lines.empty()) {
					current = (Line) lines.dequeue();
					if (root.coincident(current))
						; // do nothing
					else if (root.front(current))
						front.enqueue(current);
					else if (root.back(current))
						back.enqueue(current);
					else {
						front.enqueue(current.frontSplit(root));
						back.enqueue(current.backSplit(root));
						}
					}
				return new TreeNode(make(front), root, make(back));
				}
			}
		catch (QueueEmpty e) {
			// should never get here
			System.err.println("BSPT make error - report to programmer");
			return null;
			}
		catch (TreeMakeFailed e) {
			// should never get here
			System.err.println("BSPT make error - report to programmer");
			return null;
			}
		}
	}

final class Line {
	int	x1, y1, x2, y2;
	
	public Line(int X1, int Y1, int X2, int Y2) {
		x1 = X1;
		y1 = Y1;
		x2 = X2;
		y2 = Y2;
		}
	
	public boolean front(Line line) {
		return	(front(line.x1, line.y1) && !back(line.x2, line.y2)) ||
				(!back(line.x1, line.y1) && front(line.x2, line.y2));
		}
	
	public boolean back(Line line) {
		return	(back(line.x1, line.y1) && !front(line.x2, line.y2)) ||
				(!front(line.x1, line.y1) && back(line.x2, line.y2));
		}
	
	public boolean coincident(Line line) {
		return coincident(line.x1, line.y1) && coincident(line.x2, line.y2);
		}
	
	public boolean front(int X1, int Y1, int X2, int Y2) {
		return	(front(X1, Y1) && !back(X2, Y2)) ||
				(!back(X1, Y1) && front(X2, Y2));
		}
	
	public boolean back(int X1, int Y1, int X2, int Y2) {
		return	(back(X1, Y1) && !front(X2, Y2)) ||
				(!front(X1, Y1) && back(X2, Y2));
		}
	
	public boolean coincident(int X1, int Y1, int X2, int Y2) {
		return coincident(X1, Y1) && coincident(X2, Y2);
		}
	
	public Line frontSplit(Line root) throws TreeMakeFailed {
		Point	xy = intersection(root);
		
		if (root.front(x1, y1)) {
			return new Line(x1, y1, xy.x, xy.y);
			}
		else {
			return new Line(xy.x, xy.y, x2, y2);
			}
		}
	
	public Line backSplit(Line root) throws TreeMakeFailed {
		Point	xy = intersection(root);
		
		
		if (root.back(x1, y1)) {
			return new Line(x1, y1, xy.x, xy.y);
			}
		else {
			return new Line(xy.x, xy.y, x2, y2);
			}
		}
	
	public boolean frontInside() {
		return front(x1 + (y2 - y1), y1 + (x1 - x2)); // use typical point inside
		}
	
	public boolean backInside() {
		return back(x1 + (y2 - y1), y1 + (x1 - x2)); // use typical point inside
		}
	
	public boolean front(int x, int y) {
		if (x2 > x1)
			return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 > 0;
		else if (x2 < x1)
			return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 < 0;
		else
			return x < x2;
		}
	
	public boolean back(int x, int y) {
		if (x2 > x1)
			return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 < 0;
		else if (x2 < x1)
			return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 > 0;
		else
			return x > x2;
		}
	
	public boolean coincident(int x, int y) {
		if (x2 != x1)
			return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 == 0;
		else
			return x == x2;
		}
	
	private float sqr(float n) {
		return n * n;
		}
	
	private int sqr(int n) {
		return n * n;
		}
	
	public boolean front(int x, int y, int r) {
		if (x2 > x1) {
			float a = x;
			float b = y;
			
			if (2 * a * (y2 - y1) * (y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y2 - y1) * (sqr(a) - sqr(r)) - sqr(r) * sqr(x2 - x1) < 0)
				return false;
			else
				return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 > 0;
			}
		else if (x2 < x1) {
			float a = x;
			float b = y;
			
			if (2 * a * (y2 - y1) * (y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y2 - y1) * (sqr(a) - sqr(r)) - sqr(r) * sqr(x2 - x1) < 0)
				return false;
			else
				return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 < 0;
			}
		else
			return x + r < x2;
		}
	
	public boolean back(int x, int y, int r) {
		if (x2 > x1) {
			float a = x;
			float b = y;
			
			if (2 * a * (y2 - y1) * (y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y2 - y1) * (sqr(a) - sqr(r)) - sqr(r) * sqr(x2 - x1) < 0)
				return false;
			else
				return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 < 0;
			}
		else if (x2 < x1) {
			float a = x;
			float b = y;
			
			if (2 * a * (y2 - y1) * (y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y1 * x2 - x1 * y2 - b * (x2 - x1)) + sqr(y2 - y1) * (sqr(a) - sqr(r)) - sqr(r) * sqr(x2 - x1) < 0)
				return false;
			else
				return (x2 - x1) * y - (y2 - y1) * x - y1 * x2 + x1 * y2 > 0;
			}
		else
			return x > x2 + r;
		}
	
	private Point intersection(Line l) throws TreeMakeFailed {
		if (x1 != x2 & l.x1 != l.x2) {
			int	x = (int) (
							(float) ((x2 - x1) * (l.y1 * l.x2 - l.y2 * l.x1) - (l.x2 - l.x1) * (y1 * x2 - y2 * x1)) /
							(float) ((y2 - y1) * (l.x2 - l.x1) - (l.y2 - l.y1) * (x2 - x1))
						  );
			int	y = (int) (
							(float) (x * (y2 - y1) + y1 * x2 - x1 * y2) /
							(float) (x2 - x1)
						  );
			
			return new Point(x, y);
			}
		else if (x1 == x2)
			return new Point(x1, (int)  ((float) ((l.y2 - l.y1) * x1 + l.x2 * l.y1 - l.x1 * l.y2) / (float) (l.x2 - l.x1)));
		else if (l.x1 == l.x2)
			return new Point(l.x1, (int)  ((float) ((y2 - y1) * l.x1 + x2 * y1 - x1 * y2) / (float) (x2 - x1)));
		else
			throw new TreeMakeFailed();
		}
	}

abstract class Node {
	abstract public boolean in(int x, int y);
	abstract public boolean in(int x, int y, int r);
	abstract public boolean in(int x1, int y1, int x2, int y2);
	abstract public boolean in(Rectangle rect);
	abstract public boolean in(int[][][] outline);
	abstract public float angle(int x, int y, int r);
	}

final class LeafNode extends Node {
	boolean	in;
	
	public LeafNode(boolean i) {
		in = i;
		}
	
	public boolean in(int x, int y) {
		return in;
		}
	
	public boolean in(int x, int y, int r) {
		return in;
		}
	
	public boolean in(int x1, int y1, int x2, int y2) {
		return in;
		}
	
	public boolean in(Rectangle rect) {
		return in;
		}
	
	public boolean in(int[][][] outline) {
		return in;
		}
	
	public float angle(int x, int y, int r) {
		return 0f;
		}
	}

final class TreeNode extends Node {
	// Maths functions
	private float PI = (float) (Math.PI);
	private float TWOPI = (float) (2f * Math.PI);
	private float sqr(float n) {return n * n;}
	private int sqr(int n) {return n * n;}
	private float atan(float a) {return (float) Math.atan(a);}
	
	private float normalise(float angle) {
		if (angle < 0)
			return angle + TWOPI;
		else if (angle > TWOPI)
			return angle - TWOPI;
		else
			return angle;
		}
	
	private float angle(int x, int y) {
		if (dx != 0)
			return line_angle;
		else if (classify(x, y) == FRONT)
			return 0f;
		else
			return PI;
		}
		
	private static final int	FRONT = 0;
	private static final int	BACK = 1;
	private static final int	COINCIDENT = 2;
	private static final int	EACH = 3;
	
	int x1, y1, x2, y2;
	int	dx, dy;
	int	y1x2_x1y2;
	float line_angle;
	
	private int classify(int x, int y) {
		if (dx != 0) {
			if (dx * y - dy * x - y1x2_x1y2 > 0) {
				if (dx > 0)
					return FRONT;
				else
					return BACK;
				}
			else {
				if (dx > 0)
					return BACK;
				else
					return FRONT;
				}
			}
		else if (x < x2)
			return FRONT;
		else if (x2 < x)
			return BACK;
		else if (x == x2)
			return COINCIDENT;
		else
			return EACH;
		}
	
	private int classify(int x, int y, int X, int Y) {
		if (dy != 0) {
			if (dx * (y - Y) + dy * (x - X) > 0) {
				if (dx > 0)
					return FRONT;
				else
					return BACK;
				}
			else {
				if (dx > 0)
					return BACK;
				else
					return FRONT;
				}
			}
		else if (x < X)
			return FRONT;
		else
			return BACK;
		}
	
	public int classify(int x, int y, int r) {
		if (dx != 0) {
			float a = x;
			float b = y;
			
			if (2 * a * dy * (y1x2_x1y2 - b * dx) + sqr(y1x2_x1y2 - b * dx) + sqr(dy) * (sqr(a) - sqr(r)) - sqr(r) * sqr(dx) < 0)
				return EACH;
			else
				return classify(x, y);
			}
		else if (x + r < x2)
			return FRONT;
		else if (x2 < x - r)
			return BACK;
		else
			return EACH;
		}
	
	private static final Node	INSIDE = new LeafNode(true);
	private static final Node	OUTSIDE = new LeafNode(false);
	
	Node	forward, backward;
	
	public TreeNode(Node f, Line l, Node b) {
		forward = f;
		backward = b;
		x1 = l.x1;
		y1 = l.y1;
		x2 = l.x2;
		y2 = l.y2;
		dx = x2 - x1;
		dy = y2 - y1;
		y1x2_x1y2 = y1 * x2 - x1 * y2;
		
		line_angle = atan((float) dx / (float) -dy);
		if (dy > 0)
			line_angle += PI;
		line_angle = normalise(line_angle);
		
		if (forward == null)
			forward = l.frontInside() ? INSIDE : OUTSIDE;
		if (backward == null)
			backward = l.backInside() ? INSIDE : OUTSIDE;
		}
	
	public boolean in(int x, int y) {
		switch (classify(x, y)) {
			case FRONT:
				return forward.in(x, y);
			case BACK:
				return backward.in(x, y);
			default:
				if (forward.in(x, y))
					return true;
				return backward.in(x, y);
			}
		}
	
	public boolean in(int x, int y, int r) {
		switch (classify(x, y, r)) {
			case FRONT:
				return forward.in(x, y, r);
			case BACK:
				return backward.in(x, y, r);
			default:
				if (forward.in(x, y, r))
					return true;
				return backward.in(x, y, r);
			}
		}
	
	public boolean in(int x1, int y1, int x2, int y2) {
		int p1 = classify(x1, y1);
		int p2 = classify(x2, y2);
		
		if (p1 == p2) {
			if (p1 == FRONT)
				return forward.in(x1, y1, x2, y2);
			else
				return backward.in(x1, y1, x2, y2);
			}
		else {
			if (forward.in(x1, y1, x2, y2))
				return true;
			return backward.in(x1, y1, x2, y2);
			}
		}
	
	public boolean in(Rectangle rect) {
		if (in(rect.x, rect.y, rect.x + rect.width, rect.y))
			return true;
		if (in(rect.x + rect.width, rect.y, rect.x + rect.width, rect.y + rect.height))
			return true;
		if (in(rect.x + rect.width, rect.y + rect.height, rect.x, rect.y + rect.height))
			return true;
		return in(rect.x, rect.y + rect.height, rect.x, rect.y);
		}
	
	public boolean in(int[][][] outline) {
		for (int p = outline.length - 1; p >= 0; p--) {
			int[]	xs = outline[p][0];
			int[]	ys = outline[p][1];
			int		size = outline[p][0].length;
			
			for (int i = size - 1; i >= 1; i--)
				if (in(xs[i], ys[i], xs[i - 1], ys[i - 1]))
					return true;
			}
		return false;
		}
	
	public float angle(int x, int y, int r) {
		switch (classify(x, y, r)) {
			case FRONT:
				return forward.angle(x, y, r);
			case BACK:
				return backward.angle(x, y, r);
			default:
				if (classify(x, y, x1, y1) != classify(x, y, x2, y2))
					return angle(x, y);
				else if (sqr(r) >= sqr(x1 - x) + sqr(y1 - y))
					return angle(x, y);
				else if (sqr(r) >= sqr(x2 - x) + sqr(y2 - y))
					return angle(x, y);
				else if (classify(x, y) == FRONT)
					return forward.angle(x, y, r);
				else
					return backward.angle(x, y, r);
			}
		}
	}

class TreeMakeFailed extends Exception {
    public TreeMakeFailed() {
        super();
        }
    
    public TreeMakeFailed(String s) {
        super(s);
        }
    }