/* import of Java packages */

import java.applet.Applet;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Component;
import java.awt.Event;
import java.awt.Font;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Image;


/* data classes */

class Vertex
{
	public double x;
	public double y;
	public int edge;
	
	public Vertex()
	{
		x = 0.0;
		y = 0.0;
		edge = -1;
	}
}

class Line
{
	public int vertexFrom;
	public int vertexTo;

	public Line()
	{
		vertexFrom = -1;
		vertexTo = -1;
	}
}

class Edge
{
	public int vertexFrom;
	public int vertexTo;
	public int faceLeft;
	public int faceRight;
	public int edgePrevious;
	public int edgeNext;
	
	public Edge()
	{
		vertexFrom = -1;
		vertexTo = -1;
		faceLeft = -1;
		faceRight = -1;
		edgePrevious = -1;
		edgeNext = -1;
	}
}

class Face
{
	public int vertex;
	
	public Face()
	{
		vertex = -1;
	}
}

/* main applet class */

public class RegularizePSLG extends Applet
{
	/* constants */
	
	static final int LINES_MAX_COUNT = 1000;
	static final int VERTICES_MAX_COUNT = 1000;
	static final int EDGES_MAX_COUNT = 1000;
	static final double PI = 3.14159265358979323846;
	static final double COORD_XMIN = -10.0;
	static final double COORD_XMAX = 10.0;
	static final double COORD_YMIN = -10.0;
	static final double COORD_YMAX = 10.0;

	/* global data */

	/* geometry */
	Vertex vertices[];
	int verticesCount = 0;
	Line lines[];
	int linesCount = 0;
	Edge edges[];
	int edgesCount = 0;
	int scanVertex = -1; /* vertex on the scan line */
	int scanEdges[]; 
		/* indices of the edges intersected by the scan line 
		 * from left to right 
		 */
	int scanEdgesCount = 0;
	int minimumVertices[]; 
		/* indices of vertices with locally minimal y coordinate 
		 * left of the scan edge at the corrsponding
		 * position in scanEdges.
		 */
	int minimumVerticesCount = 0; 	
	Face faces[];
	int facesCount = 0;

	/* user interface */
	int stepsCount = 0;
	int dragVertex = -1;
	int newVertexFrom = -1;
	int windowWidth;
	int windowHeight;
	String message = "";

	/* core methods */
	
	void initializeData()
		/* initializes global data */
	{
		int index;
		
		edgesCount = 0;
		scanEdgesCount = 0;
		minimumVerticesCount = 0;
		facesCount = 0;
		scanVertex = -1;
		for (index = 0; index < verticesCount; index++)
		{
			vertices[index].edge = -1;
		}
	}

	void computeData(int stepsCount)
		/* performs stepsCount steps of the algorithm */
	{
		message = "press left mouse button to set points and lines";
		if (verticesCount < 2)
		{
			return;
		}
		message = "press the `right arrow' key to step through the animation";
		if (--stepsCount < 0) 
		{
			return;
		}


		/* ... insert algorithm here ... */


		message = "finished; `left arrow' key backtracks, `home' restarts.";

		return;
	}

	/* rendering methods */

	void display()
		/* renders the current state */
	{
		int index;

		/* initialize and partially compute data */
		initializeData();
		computeData(stepsCount);

		/* clear screen */
		setColor(0.0, 0.0, 0.0);
		clearScreen();

		/* render input points in blue */
		setColor(0.3, 0.3, 1.0); 
		for (index = 0; index < verticesCount; index++)
		{
			if (index != newVertexFrom)
			{
				setPointSize(7.0);
			}
			else
			{
				setPointSize(14.0);
			}
			drawPoint(vertices[index].x, vertices[index].y);
		}

		/* render lines in blue (if there is no scanline) */
		if (scanVertex < 0)
		{
			setLineWidth(3.0);
			setColor(0.3, 0.3, 1.0);
			for (index = 0; index < linesCount; index++)
			{
				int from = lines[index].vertexFrom;
				int to = lines[index].vertexTo;

				drawLine(vertices[from].x, vertices[from].y, 
					vertices[to].x, vertices[to].y);
			}
		}

		/* render doubly connected edges in white */
		for (index = 0; index < edgesCount; index++)
		{
			int from = edges[index].vertexFrom;
			int to = edges[index].vertexTo;
			int edge;
			int vertex;
			double x1, x2, x3;
			double y1, y2, y3;
			
			setLineWidth(5.0);
			setColor(1.0, 1.0, 1.0);
			drawLine(vertices[from].x, vertices[from].y, 
				vertices[to].x, vertices[to].y);
				
			/* render link to previous edge in light blue */
			edge = edges[index].edgePrevious;
			if (0 <= edge)
			{
				if (edges[edge].vertexTo == from)
				{
					vertex = edges[edge].vertexFrom;
				}
				else if (edges[edge].vertexFrom == from)
				{
					vertex = edges[edge].vertexTo;
				}
				else
				{
					System.out.println("error in display(): inconsistent vertices");
					return;
				}
				x1 = vertices[from].x + (vertices[to].x - vertices[from].x) / 4.0;
				y1 = vertices[from].y + (vertices[to].y - vertices[from].y) / 4.0;
				x3 = vertices[from].x + 
					(vertices[vertex].x - vertices[from].x) / 5.0;
				y3 = vertices[from].y + 
					(vertices[vertex].y - vertices[from].y) / 5.0;
				x2 = x1 + x3 - vertices[from].x;
				y2 = y1 + y3 - vertices[from].y;
				setLineWidth(0.5);
				setColor(0.7, 0.7, 1.0);
				drawLine(x1, y1, x2, y2);
				drawLine(x2, y2, x3, y3);
			}
	
			/* render link to next edge in light green */
			edge = edges[index].edgeNext;
			if (0 <= edge)
			{
				if (edges[edge].vertexTo == to)
				{
					vertex = edges[edge].vertexFrom;
				}
				else if (edges[edge].vertexFrom == to)
				{
					vertex = edges[edge].vertexTo;
				}
				else
				{
					System.out.println("error in display(): inconsistent vertices");
					return;
				}
				x1 = vertices[to].x + (vertices[from].x - vertices[to].x) / 4.0;
				y1 = vertices[to].y + (vertices[from].y - vertices[to].y) / 4.0;
				x3 = vertices[to].x + 
					(vertices[vertex].x - vertices[to].x) / 5.0;
				y3 = vertices[to].y + 
					(vertices[vertex].y - vertices[to].y) / 5.0;
				x2 = x1 + x3 - vertices[to].x;
				y2 = y1 + y3 - vertices[to].y;
				setLineWidth(0.5);
				setColor(0.7, 1.0, 0.7);
				drawLine(x1, y1, x2, y2);
				drawLine(x2, y2, x3, y3);
			}
			
		}
		
		/* render scan line and vertex in red */
		
		if (0 <= scanVertex)
		{
			setLineWidth(5.0);
			setColor(1.0, 0.0, 0.0);
			drawLine(COORD_XMIN, vertices[scanVertex].y, 
				COORD_XMAX, vertices[scanVertex].y);
			setPointSize(7.0);		
			setColor(1.0, 0.0, 0.0);
			drawPoint(vertices[scanVertex].x, vertices[scanVertex].y);			
		}		
		
		/* render edges intersected by scan line in green */
		
		setLineWidth(5.0);
		setColor(0., 1.0, 0.);
		for (index = 0; index < scanEdgesCount; index++)
		{
			int from = edges[scanEdges[index]].vertexFrom;
			int to = edges[scanEdges[index]].vertexTo;
			
			drawLine(vertices[from].x, vertices[from].y, 
				vertices[to].x, vertices[to].y);
		}		
		
		/* write text */

		setColor(1.0, 1.0, 1.0);
		write(message);

		/* display new image */
		repaint();
	}
	
	void write(String string)
		/* writes string at the bottom */
	{
		graphicsBuffer.setColor(Color.white);
		graphicsBuffer.drawString(string, 10, getSize().height - 10);
	}

	void setColor(double red, double green, double blue)
	{
		graphicsBuffer.setColor(new Color((float)red, (float)green, (float)blue));
	}

	void clearScreen()
	{
		graphicsBuffer.fillRect(0, 0, getSize().width, getSize().height);
	}
	
	double pointSize = 1.0;
	
	void setPointSize(double size)
	{
		pointSize = size;
	}
	
	void drawPoint(double x, double y)
	{
		double rasterX = (x - COORD_XMIN) / (COORD_XMAX - COORD_XMIN) * 
			getSize().width;
		double rasterY = (COORD_YMAX - y) / (COORD_YMAX - COORD_YMIN) * 
			getSize().height;
		graphicsBuffer.fillOval((int)rasterX - (int)(pointSize / 2.0),
			(int)rasterY - (int)(pointSize / 2.0), 
			(int)pointSize, (int)pointSize);
	}

	double lineWidth = 1.0;
	
	void setLineWidth(double width)
	{
		lineWidth = width;
	}
		
	void drawLine(double x1, double y1, double x2, double y2)
	{
		double rasterX1 = (x1 - COORD_XMIN) / (COORD_XMAX - COORD_XMIN) * 
			getSize().width;
		double rasterY1 = (COORD_YMAX - y1) / (COORD_YMAX - COORD_YMIN) * 
			getSize().height;
		double rasterX2 = (x2 - COORD_XMIN) / (COORD_XMAX - COORD_XMIN) * 
			getSize().width;
		double rasterY2 = (COORD_YMAX - y2) / (COORD_YMAX - COORD_YMIN) * 
			getSize().height;

		if (lineWidth < 1.0)
		{		
			graphicsBuffer.drawLine((int)rasterX1, (int)rasterY1, 
				(int)rasterX2, (int)rasterY2);
		}
		else
		{
			double length = Math.sqrt((rasterX1 - rasterX2) * 
				(rasterX1 - rasterX2) + 
				(rasterY1 - rasterY2) * (rasterY1 - rasterY2));
			if (length > 0.0)
			{
				double perpX = lineWidth * (rasterY2 - rasterY1) / length / 2.0;
				double perpY = lineWidth * (rasterX1 - rasterX2) / length / 2.0;
				int xs[] = new int[4];
				int ys[] = new int[4];
	
				xs[0] = (int)(rasterX1 + perpX);
				ys[0] = (int)(rasterY1 + perpY);
				xs[1] = (int)(rasterX2 + perpX);
				ys[1] = (int)(rasterY2 + perpY);
				xs[2] = (int)(rasterX2 - perpX);
				ys[2] = (int)(rasterY2 - perpY);
				xs[3] = (int)(rasterX1 - perpX);
				ys[3] = (int)(rasterY1 - perpY);
								
				graphicsBuffer.fillPolygon(xs, ys, 4);
			}
		}
	}

	/* event handling (AWT 1.0 style) */

	public boolean keyDown(Event evt, int key)
	{
		switch (key)
		{
			case Event.RIGHT:
				stepsCount++;
				display();
				break;
			case Event.LEFT:
				if (stepsCount > 0)
					stepsCount--;
				else
					stepsCount = 0;
				display();
				break;
			case Event.HOME:
				stepsCount = 0;
				verticesCount = 0;
				linesCount = 0;
				newVertexFrom = -1;
				dragVertex = -1;
				display();
				break;	
			case 'o':
			{
				int index;
				System.out.println("Table of the DCEL:");
				System.out.println("Edge No., V1, V2, F1, F2, P1, P2");
				for (index = 0; index < edgesCount; index++)
				{
					System.out.println(index + ", " + 
						edges[index].vertexFrom + ", " + edges[index].vertexTo + ", " + 
						edges[index].faceLeft + ", " + edges[index].faceRight + ", " + 
						edges[index].edgePrevious + ", " + edges[index].edgeNext);
				}
				break;
			}
		}	
		return true;
	}

	public boolean mouseUp(Event evt, int x, int y)
	{
		dragVertex = -1;
		return true;
	}

	public boolean mouseDown(Event evt, int x, int y)
	{
		int index;
		double coordX;
		double coordY;
		double minimumDistance = 0.0;
		double distance;
		int nearestVertex;

		coordX = COORD_XMIN + (double)x / getSize().width * 
			(COORD_XMAX - COORD_XMIN);
		coordY = COORD_YMAX - (double)y / getSize().height * 
			(COORD_YMAX - COORD_YMIN);

		/* search for nearest point */
		nearestVertex = -1;
		for (index = 0; index < verticesCount; index++)
		{
			distance = Math.abs(vertices[index].x - coordX) + 
				Math.abs(vertices[index].y - coordY);
			if (nearestVertex < 0 || distance < minimumDistance)
			{
				nearestVertex = index;
				minimumDistance = distance;
			}
		}
		if (nearestVertex >= 0 && 
			minimumDistance > (COORD_XMAX - COORD_XMIN) * 20.0 / getSize().width)
		{
			nearestVertex = -1;
		}
	
		if (!evt.metaDown())
		{
			if (nearestVertex >= 0)
			{
				dragVertex = moveVertex(nearestVertex, coordX, coordY);
			}
			else if (verticesCount < VERTICES_MAX_COUNT) /* set new point */
			{
				dragVertex = insertVertex(coordX, coordY);
			}

			/* deal with lines */			
			if (dragVertex < 0 || newVertexFrom == dragVertex)
			{
				newVertexFrom = -1;
			}
			else if (newVertexFrom < 0)
			{
				newVertexFrom = dragVertex;
			}
			else if (linesCount < LINES_MAX_COUNT)
			{
				lines[linesCount].vertexFrom = newVertexFrom;
				lines[linesCount].vertexTo = dragVertex;
				linesCount++;
				newVertexFrom = -1;
			}

			display();
		}
		else if (evt.metaDown())
		{
			newVertexFrom = -1;
			/* delete nearestVertex */
			if (verticesCount > 0)
			{
				deleteVertex(nearestVertex);

				display();
			}
		}
		return true;
	}

	/* insert a new vertex and return the index */
	public int insertVertex(double x, double y)
	{
		int index;
		int index2;

		if (verticesCount >= VERTICES_MAX_COUNT)
		{
			return -1;
		}

		index = 0;
		while (index < verticesCount && (vertices[index].y < y || 
			(vertices[index].y == y && vertices[index].x > x)))
		{
			index++;
		}
		verticesCount++;
		for (index2 = verticesCount - 1; index2 > index; index2--)
		{
			vertices[index2].x = vertices[index2 - 1].x;
			vertices[index2].y = vertices[index2 - 1].y;
		}
		vertices[index].x = x;
		vertices[index].y = y;
		
		for (index2 = 0; index2 < linesCount; index2++)
		{
			if (lines[index2].vertexFrom >= index)
			{
				lines[index2].vertexFrom++;
			}
			if (lines[index2].vertexTo >= index)
			{
				lines[index2].vertexTo++;
			}
		}
		if (newVertexFrom >= index)
		{
			newVertexFrom++;
		}
		return index;		
	}

	/* delete a vertex */
	public void deleteVertex(int index)
	{
		int index2;

		if (index < 0)
		{	
			return;
		}

		for (index2 = index; index2 < verticesCount - 1; index2++)
		{
			vertices[index2].x = vertices[index2 + 1].x;
			vertices[index2].y = vertices[index2 + 1].y;
		}
		verticesCount--;
		if (newVertexFrom > index)
		{
			newVertexFrom--;
		}
		else if (newVertexFrom == index)
		{
			newVertexFrom = -1;
		}
		
		/* delete all lines to or from vertex index and decrement
		 * all indices greater than index 
		 */
		for (index2 = 0; index2 < linesCount; index2++)
		{
			if (lines[index2].vertexFrom == index || 
				lines[index2].vertexTo == index)
			{
				int index3;

				for (index3 = index2; index3 < linesCount - 1; index3++)
				{
					lines[index3].vertexFrom = lines[index3 + 1].vertexFrom;
					lines[index3].vertexTo = lines[index3 + 1].vertexTo;							
				}
				linesCount--;
				index2--;
			}
			else 
			{
				if (lines[index2].vertexFrom > index)
				{
					lines[index2].vertexFrom--;
				}
				if (lines[index2].vertexTo > index)
				{
					lines[index2].vertexTo--;
				}
			}
		}
	}

	public boolean mouseDrag(Event evt, int x, int y)
	{
		if (dragVertex >= 0)
		{
			double new_x = 
				COORD_XMIN + (double)x / getSize().width * (COORD_XMAX - COORD_XMIN);
			double new_y = 
				COORD_YMAX - (double)y / getSize().height * (COORD_YMAX - COORD_YMIN);
			dragVertex = moveVertex(dragVertex, new_x, new_y);
			display();
		}
		return true;
	}

	/* move a vertex and return the new index */
	public int moveVertex(int index, double x, double y)
	{
		int new_index;
		int index2;

		new_index = 0;
		while (new_index < verticesCount && (new_index == index || 
			vertices[new_index].y < y || 
			(vertices[new_index].y == y && vertices[new_index].x > x)))
		{
			new_index++;
		}
		if (new_index < index)
		{
			for (index2 = index; index2 > new_index; index2--)
			{
				vertices[index2].x = vertices[index2 - 1].x;
				vertices[index2].y = vertices[index2 - 1].y;
			}
		}
		else if (new_index > index)
		{
			new_index--;
			for (index2 = index; index2 < new_index; index2++)
			{
				vertices[index2].x = vertices[index2 + 1].x;
				vertices[index2].y = vertices[index2 + 1].y;
			}
		}
		vertices[new_index].x = x;
		vertices[new_index].y = y;

		if (new_index < index)
		{		
			for (index2 = 0; index2 < linesCount; index2++)
			{
				if (lines[index2].vertexFrom == index)
				{
					lines[index2].vertexFrom = new_index;
				}
				else if (lines[index2].vertexFrom >= new_index && 
					lines[index2].vertexFrom < index)
				{
					lines[index2].vertexFrom++;
				}
				if (lines[index2].vertexTo == index)
				{
					lines[index2].vertexTo = new_index;
				}
				else if (lines[index2].vertexTo >= new_index && 
					lines[index2].vertexTo < index)
				{
					lines[index2].vertexTo++;
				}
			}
			if (newVertexFrom == index)
			{
				newVertexFrom = new_index;
			}
			else if (newVertexFrom >= new_index && 
				newVertexFrom < index)
			{
				newVertexFrom++;
			}
		}
		else if (new_index > index)
		{
			for (index2 = 0; index2 < linesCount; index2++)
			{
				if (lines[index2].vertexFrom == index)
				{
					lines[index2].vertexFrom = new_index;
				}
				else if (lines[index2].vertexFrom > index && 
					lines[index2].vertexFrom <= new_index)
				{
					lines[index2].vertexFrom--;
				}
				if (lines[index2].vertexTo == index)
				{
					lines[index2].vertexTo = new_index;
				}
				else if (lines[index2].vertexTo > index && 
					lines[index2].vertexTo <= new_index)
				{
					lines[index2].vertexTo--;
				}
			}
			if (newVertexFrom == index)
			{
				newVertexFrom = new_index;
			}
			else if (newVertexFrom > index && 
				newVertexFrom <= new_index)
			{
				newVertexFrom--;
			}
		}

		return new_index;		
	}

	// implementation of applet methods

	public void init()
	{
		int index;
		verticesCount = 0;
		vertices = new Vertex[VERTICES_MAX_COUNT];
		for (index = 0; index < VERTICES_MAX_COUNT; index++)
		{
			vertices[index] = new Vertex();
		}
		linesCount = 0;
		lines = new Line[LINES_MAX_COUNT];
		for (index = 0; index < VERTICES_MAX_COUNT; index++)
		{
			lines[index] = new Line();
		}
		edgesCount = 0;
		edges = new Edge[EDGES_MAX_COUNT];
		for (index = 0; index < EDGES_MAX_COUNT; index++)
		{
			edges[index] = new Edge();
		}
		scanEdgesCount = 0;
		scanEdges = new int[EDGES_MAX_COUNT];
		minimumVerticesCount = 0;
		minimumVertices = new int[EDGES_MAX_COUNT + 1];
		facesCount = 0;
		faces = new Face[EDGES_MAX_COUNT];
		for (index = 0; index < EDGES_MAX_COUNT; index++)
		{
			faces[index] = new Face();
		}
	}
	
	public void start()
	{
		if (null == imageBuffer)
		{
			imageBuffer = createImage(getSize().width, getSize().height);
			graphicsBuffer = imageBuffer.getGraphics();
			graphicsBuffer.setFont(new Font("Dialog", Font.PLAIN, 16));
			display();
		}
	}
	
	public void stop()
	{
	}
	
	public void destroy()
	{
	}
		
	// variables and methods for double buffering
	
	Image imageBuffer;
	Graphics graphicsBuffer;

	public void update(Graphics g)
	{
		paint(g);
	}

	public void paint(Graphics g)
	{
		if (null != imageBuffer)
		{
			g.drawImage(imageBuffer, 0, 0, this);
		}
	}

	// methods to run the program as an application (not an application)

	public Dimension getPreferredSize()
	{
		return new Dimension(500, 500);
	}
	
	public static void main(String [] args)
	{
		RegularizePSLG application = new RegularizePSLG();
		
		Frame frame = new Frame("Regularize PSLG");
		frame.add(application);
		frame.pack();

		application.init();
		application.start();
		
		frame.setVisible(true);
	}
}