/* 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 edge;
	public boolean faceIsRight;
	
	public Face()
	{
		edge = -1;
		faceIsRight = true;
		
	}
}

/* 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;

	int up_left_edge = -1; /* the leftmost edge going up */
	int up_right_edge = -1; /* the rightmost edge going up */
	int down_left_edge = -1; /* the leftmost edge going down */
	int down_right_edge = -1; /* the rightmost edge going down */


	/* 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 = "inserting lines into the DCEL";

		{
			int index;
			
			for (index = 0; index < linesCount; index++)
			{
				insertAscendingEdge(lines[index].vertexFrom, 
					lines[index].vertexTo);
					
				if (--stepsCount < 0) 
				{
					return;
				}				
			}
		}

		for (scanVertex = verticesCount - 1; scanVertex >= 0; scanVertex--)
		{
			int scan_vertex = scanVertex;
			double scan_y;
			double scan_x;
			
			message = "moving scan line top to bottom";
		
			scan_x = vertices[scan_vertex].x;
			scan_y = vertices[scan_vertex].y;

			/* update scan line */
			
			/* determine kind of scan vertex */

			up_left_edge = -1;
			up_right_edge = -1;
			down_left_edge = -1;
			down_right_edge = -1;
			if (0 <= vertices[scan_vertex].edge)
			{
				int current_edge;
				int current_vertex;
				double current_x;
				double current_y;
				int current_quadrant; /* 0: top, right; 1,2,3: counter clock wise */
				int last_edge;
				int last_vertex;
				double last_x;
				double last_y;
				int last_quadrant;
				boolean is_obstuse_angle;

				current_edge = -1;
				current_vertex = -1;
				current_x = 0.0;
				current_y = 0.0;
				current_quadrant = -1;
				do
				{
					last_edge = current_edge;
					last_vertex = current_vertex;
					last_x = current_x;
					last_y = current_y;
					last_quadrant = current_quadrant;
					
					if (0 > current_edge)
					{
						current_edge = vertices[scan_vertex].edge;
					}
					else
					{
						current_edge = getNextEdgeCounterClockWise(scan_vertex, 
							current_edge);
					}
					if (edges[current_edge].vertexFrom == scan_vertex)
					{
						current_vertex = edges[current_edge].vertexTo;
					}
					else if (edges[current_edge].vertexTo == scan_vertex)
					{
						current_vertex = edges[current_edge].vertexFrom;
					}
					else
					{
						System.out.println("error in computeData(...): " +
							"inconsistent edge");
						return;
					}
					current_x = vertices[current_vertex].x;
					current_y = vertices[current_vertex].y;
					if (current_y > scan_y || 
						(current_y == scan_y && current_x < scan_x))
					{
						/* top */
						if (current_x > scan_x ||
							(current_x == scan_x && current_y > scan_y))
						{
							/* top right */
							current_quadrant = 0;
						}
						else
						{
							/* top left */
							current_quadrant = 1;
						}
					}
					else
					{
						/* bottom */
						if (current_x < scan_x ||
							(current_x == scan_x && current_y < scan_y))
						{
							/* bottom left */
							current_quadrant = 2;
						}
						else
						{
							/* bottom right */
							current_quadrant = 3;
						}
					}
					if ((current_x - scan_x) * (last_y - scan_y) - 
						(current_y - scan_y) * (last_x - scan_x) < 0.0)
					{
						is_obstuse_angle = false;
					}
					else
					{
						is_obstuse_angle = true;
					}
					if (0 <= current_edge && 0 <= last_edge)
					{
						if (0 == current_quadrant && 
							(current_quadrant != last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							up_right_edge = current_edge;
						}
						if (1 == current_quadrant && 
							(3 == last_quadrant || 
							2 == last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							up_right_edge = current_edge;
						}
						if (1 == last_quadrant && 
							(current_quadrant != last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							up_left_edge = last_edge;
						}
						if (0 == last_quadrant && 
							(2 == current_quadrant || 
							3 == current_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							up_left_edge = last_edge;
						}
						if (2 == current_quadrant && 
							(current_quadrant != last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							down_left_edge = current_edge;
						}
						if (3 == current_quadrant && 
							(1 == last_quadrant || 
							0 == last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							down_left_edge = current_edge;
						}
						if (3 == last_quadrant && 
							(current_quadrant != last_quadrant || 
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							down_right_edge = last_edge;
						}
						if (2 == last_quadrant && 
							(0 == current_quadrant || 
							1 == current_quadrant ||
							current_edge == last_edge ||
							is_obstuse_angle))
						{
							down_right_edge = last_edge;
						}
					}
				}
				while ((current_edge != vertices[scan_vertex].edge || 0 > last_edge));
				
			}			
			if ((0 <= up_left_edge && 0 > up_right_edge) ||
				(0 > up_left_edge && 0 <= up_right_edge) ||
				(0 <= down_left_edge && 0 > down_right_edge) ||
				(0 > down_left_edge && 0 <= down_right_edge))
			{
				System.out.println("error in computeData(...): " +
					"this should not happen.");
				return;
			}

			/* locate scan vertex on scan line */
			int scan_edge = 0;
			int scan_position = 0; 
				/* index of the up_left_edge or the new down_left_edge */
			int scan_second_position = 0;
				/* index of up_right_edge + 1 or of the new down_left_edge */
			if (0 > up_left_edge && 0 > up_right_edge)
			{
				/* scan vertex is a maximum, we have to calculate intersection 
				 * points in order to find our position in scanEdges.
				 * this should be done with a binary search.
				 */
				int current_edge;
				double x1;
				double y1;
				double x2;
				double y2;
				double cut_x;
				for (scan_edge = 0; scan_edge < scanEdgesCount; scan_edge++)
				{
					current_edge = scanEdges[scan_edge];
					x1 = vertices[edges[current_edge].vertexFrom].x;
					y1 = vertices[edges[current_edge].vertexFrom].y;
					x2 = vertices[edges[current_edge].vertexTo].x;
					y2 = vertices[edges[current_edge].vertexTo].y;
					if (y2 == y1)
					{
						cut_x = x1;
					}
					else
					{
						cut_x = x1 + (x2 - x1) * (scan_y - y1) / (y2 - y1);
					}
					if (cut_x > scan_x)
					{
						break;
							/* scan edge is now "right" of our position */
					}
				}
				scan_position = scan_edge;
				scan_second_position = scan_edge;
			}
			else
			{
				/* find the position of the up_left_edge */
				for (scan_edge = 0; scan_edge < scanEdgesCount; scan_edge++)
				{
					if (up_left_edge == scanEdges[scan_edge])
					{
						break;
					}
				}
				scan_position = scan_edge;
				/* and the position of the up_right_edge plus 1 */
				for (scan_edge = 0; scan_edge < scanEdgesCount; scan_edge++)
				{
					if (up_right_edge == scanEdges[scan_edge])
					{
						break;
					}
				}
				scan_second_position = scan_edge + 1;
			}
			
			/* update scanEdges and minimumVertices */
			
			if (0 <= up_left_edge && 0 <= up_right_edge)
			{
				/* delete all edges going upwards, i.e.
				 * delete all edges between scan_position (inclusive)
				 * and scan_second_position (exclusive)
				 * from scanEdges.
				 */
				for (scan_edge = scan_position; scan_edge < scanEdgesCount -
					(scan_second_position - scan_position); scan_edge++)
				{
					scanEdges[scan_edge] = scanEdges[scan_edge + 
						scan_second_position - scan_position];
				}
				scanEdgesCount = scanEdgesCount - (scan_second_position - 
					scan_position);
				if (scanEdgesCount < scan_position)
				{
					System.out.println("error in computeData(...): " +
						"this should not happen (too few scan edges)");
					return;
				}
				
				/* join minimumVertices between the deleted edges and left 
				 * and right of them with the scan vertex, 
				 * i.e. from scan_position (inclusive) 
				 * to scan_second_position (inclusive).
				 */
				for (scan_edge = scan_position; scan_edge < minimumVerticesCount;
					scan_edge++)
				{
					if (scan_edge <= scan_second_position && 
						0 <= minimumVertices[scan_edge])
					{
						message = "Joined scanned vertex with minimum.";

						/* join minimumVertices[scan_edge] with the scan vertex */

						insertAscendingEdge(minimumVertices[scan_edge], scan_vertex);

						if (scan_edge == scan_second_position)
						{
							/* this minimumVertex has been copied to scan_edge!,
							 * we have to delete it there. 
							 */
							minimumVertices[scan_position] = -1;
						}
					}
					
					if (scan_edge + (scan_second_position - scan_position) <
						minimumVerticesCount)
					{
						minimumVertices[scan_edge] = minimumVertices[scan_edge + 
							scan_second_position - scan_position];
					}
					else
					{
						minimumVertices[scan_edge] = -1;
					}
				}
				minimumVerticesCount = minimumVerticesCount - (scan_second_position - 
					scan_position);
				if (minimumVerticesCount < scan_position)
				{
					System.out.println("error in computeData(...): " +
						"this should not happen (too few minimum vertices)");
					return;
				}				
			}
			else
			{
				/* the scan vertex is a maximum or an isolated vertex */
				
				if (scan_position < minimumVerticesCount && 
					0 <= minimumVertices[scan_position])
				{
					message = "Joined scanned vertex (maximum) with minimum.";
					
					/* join this minimum with the scan vertex */
					
					insertAscendingEdge(minimumVertices[scan_position], scan_vertex);
					
					minimumVertices[scan_position] = -1;					
				}
				else
				{
					if (0 < scanEdgesCount && 0 == scan_position)
					{
						message = "Joined scanned vertex with leftmost edge.";

						insertAscendingEdge(edges[scanEdges[scan_position]].vertexTo, 
							scan_vertex);
					}
					else if (0 < scanEdgesCount && 
						scan_position == scanEdgesCount)
					{
						message = "Joined scanned vertex with rightmost edge.";

						insertAscendingEdge(edges[scanEdges[scan_position - 1]].vertexTo, 
							scan_vertex);
					}
					else if (1 < scanEdgesCount && 0 < scan_position &&
						scan_position < scanEdgesCount)
					{
						int first_edge_vertex;
						int second_edge_vertex;
						int lower_edge_vertex;
					
						message = "Joined scanned vertex with lower edge vertex.";

						first_edge_vertex = edges[scanEdges[scan_position - 1]].vertexTo;
						second_edge_vertex = edges[scanEdges[scan_position]].vertexTo;
						if (vertices[first_edge_vertex].y < 
							vertices[second_edge_vertex].y || 
							(vertices[first_edge_vertex].y ==
							vertices[second_edge_vertex].y &&
							vertices[first_edge_vertex].x >
							vertices[second_edge_vertex].x))
						{
							lower_edge_vertex = first_edge_vertex;
						}
						else
						{
							lower_edge_vertex = second_edge_vertex;
						}
						insertAscendingEdge(lower_edge_vertex, 
							scan_vertex);
					}
				}
			}
			scan_second_position = scan_position;
			
			if (0 <= down_left_edge && 0 <= down_right_edge)
			{			
				int current_edge;
				int last_edge;
			
				/* insert down edges */

				scan_edge = scan_position;
				current_edge = down_left_edge;
				do
				{
					int index;
					
					/* move everything to the right */
					scanEdgesCount++;
					minimumVerticesCount++;
					for (index = scanEdgesCount - 1; index > scan_edge; index--)
					{
						scanEdges[index] = scanEdges[index - 1];
					}
					for (index = minimumVerticesCount - 1; index > scan_edge; index--)
					{
						minimumVertices[index] = minimumVertices[index - 1];
					}
					
					/* insert edge */
					scanEdges[scan_edge] = current_edge;
					minimumVertices[scan_edge] = -1;
					
					/* go to next edge */
					last_edge = current_edge;
					current_edge = getNextEdgeCounterClockWise(scan_vertex,
						current_edge);
					scan_edge++;
				}
				while (last_edge != down_right_edge);	
			}
			else
			{
				/* the scan vertex is a minimum, we have to insert it */
				
				if (scan_position == minimumVerticesCount)
				{
					minimumVertices[minimumVerticesCount] = -1;
					minimumVerticesCount++;
				}
				if (scan_position < minimumVerticesCount)
				{
					if (0 <= minimumVertices[scan_position])
					{
						/* join the two minima */
						
						message = "Joined scanned vertex (new minimum) with minimum.";
						
						insertAscendingEdge(minimumVertices[scan_position], 
							scan_vertex);
					}
					minimumVertices[scan_position] = scan_vertex;
				}
				else 
				{
					System.out.println("error in computeData(...): " +
						"this should not happen (scan_position too high");
					return;
				}
			}

			if (--stepsCount < 0) 
			{
				return;
			}				

			/* next scan vertex */
		}

		message = "inserting faces";
		if (--stepsCount < 0) 
		{
			return;
		}				

		facesCount = 0;
		for (scanVertex = 0; scanVertex < verticesCount; scanVertex++)
		{
			int current_edge;
			
			message = "moving scan line bottom to top";
			if (--stepsCount < 0) 
			{
				return;
			}				

			if (vertices[scanVertex].edge < 0)
			{
				System.out.println("error in error in computeData(...): " +
					"vertex has no edge (incomplete regularization)");
				return;
			}
			
			current_edge = vertices[scanVertex].edge;
			if (0 == scanVertex)
			{
				/* find the "rightmost" edge in order to first find the unbounded
				 * polygon.
				 */
				int lowest_edge = -1;
				double lowest_angle = 0.0;
				int current_vertex;
				double current_angle;
				 
				do
				{
					if (scanVertex == edges[current_edge].vertexTo)
					{
						/* well, this should not happen, but anyways... */
						current_vertex = edges[current_edge].vertexFrom;
					}
					else
					{
						current_vertex = edges[current_edge].vertexTo;
					}
					current_angle = 
						Math.atan2(vertices[current_vertex].y - 
						vertices[scanVertex].y,
						vertices[current_vertex].x - 
						vertices[scanVertex].x);

					if (lowest_edge < 0 || current_angle < lowest_angle)
					{
						lowest_edge = current_edge;
						lowest_angle = current_angle;
					}
					current_edge = getNextEdgeCounterClockWise(scanVertex, 
						current_edge);				 	
				}
				while (current_edge != vertices[scanVertex].edge);
					current_edge = lowest_edge;
			}

			do
			{	
				/* for 0 == scanVertex, it is important that we first ask
				 * for faceRight, otherwise we would not find the unbounded
				 * polygon first.
				 */			
				if (edges[current_edge].faceRight < 0)
				{
					addNewFace(current_edge, true);

					message = "added new face";
					if (--stepsCount < 0) 
					{
						return;
					}				
				}
				if (edges[current_edge].faceLeft < 0)
				{
					addNewFace(current_edge, false);

					message = "added new face";
					if (--stepsCount < 0) 
					{
						return;
					}				
				}
				current_edge = getNextEdgeCounterClockWise(scanVertex, 
					current_edge);
			}
			while (current_edge != vertices[scanVertex].edge);			
		}
		scanVertex = -1;		
		
		/* end of algorithm */

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

		return;
	}

	int getNextEdgeCounterClockWise(int vertex, int edge)
	{
		if (vertex < 0 || edge < 0)
		{
			System.out.println("error in getNextEdgeCounterClockWise(" + vertex +
				", " + edge + "): invalid arguments");
			return -1;
		}
		
		if (edges[edge].vertexTo == vertex)
		{
			return edges[edge].edgeNext;
		}
		else if (edges[edge].vertexFrom == vertex)
		{
			return edges[edge].edgePrevious;
		}
		System.out.println("error in getNextEdgeCounterClockWise(" + vertex +
			", " + edge + "): vertex not found");
		return -1;
	}
	
	int getNextEdgeClockWise(int vertex, int edge)
	{
		int next_edge;
		int last_edge;
		
		next_edge = edge;
		do
		{
			last_edge = next_edge;
			next_edge = getNextEdgeCounterClockWise(vertex, next_edge);
		}
		while (next_edge != -1 && next_edge != edge);
		if (next_edge == edge)
		{
			return last_edge;
		}
		return -1;
	}
	
	void insertAscendingEdge(int vertex1, int vertex2)
	{
		if (vertices[vertex1].y < vertices[vertex2].y ||
			(vertices[vertex1].y == vertices[vertex2].y && 
			vertices[vertex1].x > vertices[vertex2].x))
		{
			insertEdge(vertex1, vertex2);
		}
		else
		{
			insertEdge(vertex2, vertex1);
		}
	}

	void insertEdge(int vertexFrom, int vertexTo)
	{	
		double new_angle;
		int current_edge;
		double current_angle;
		int last_edge;
		double last_angle;
		
		if (edgesCount >= EDGES_MAX_COUNT)
		{
			System.out.println("error in insertEdge(" + vertexFrom +
				", " + vertexTo + "): too many edges");
			return;
		}
		edges[edgesCount].vertexFrom = vertexFrom;
		edges[edgesCount].vertexTo = vertexTo;
		edges[edgesCount].faceLeft = -1;
		edges[edgesCount].faceRight = -1;
		
		/* sort edge into edges incident on vertexFrom */
	
		if (0 > vertices[vertexFrom].edge)
		{
			vertices[vertexFrom].edge = edgesCount;
			edges[edgesCount].edgePrevious = edgesCount;
		}
		else
		{
			new_angle = Math.atan2(vertices[vertexTo].y - vertices[vertexFrom].y,
				vertices[vertexTo].x - vertices[vertexFrom].x);

			current_edge = -1;
			current_angle = 0.;
			do
			{
				last_edge = current_edge;
				last_angle = current_angle;
				if (-1 == current_edge)
				{
					current_edge = vertices[vertexFrom].edge;			
				}
				else
				{
					current_edge = 
						getNextEdgeCounterClockWise(vertexFrom, current_edge);
				}
				if (edges[current_edge].vertexFrom == vertexFrom)
				{
					current_angle = 
						Math.atan2(vertices[edges[current_edge].vertexTo].y - 
						vertices[vertexFrom].y,
						vertices[edges[current_edge].vertexTo].x - 
						vertices[vertexFrom].x);
				}
				else
				{
					current_angle = 
						Math.atan2(vertices[edges[current_edge].vertexFrom].y - 
						vertices[vertexFrom].y,
						vertices[edges[current_edge].vertexFrom].x - 
						vertices[vertexFrom].x);
				}
			}
			while (-1 != current_edge && (-1 == last_edge || 
				(current_angle > last_angle && last_angle > new_angle) ||
				(current_angle > last_angle && current_angle < new_angle) ||
				(current_angle < last_angle && current_angle < new_angle &&
				last_angle > new_angle)));
			if (-1 == current_edge || -1 == last_edge)
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): failed at first vertex");
				return;
			}
			if (current_angle == new_angle || last_angle == new_angle)
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): degenerate edge (at first vertex)");
				return;
			}
			edges[edgesCount].edgePrevious = current_edge;
			if (edges[last_edge].vertexFrom == vertexFrom)
			{
				if (edges[last_edge].edgePrevious != current_edge)
				{
					System.out.println("error in insertEdge(" + vertexFrom +
						", " + vertexTo + "): inconsistent edges at first vertex");
					return;				
				}
				edges[last_edge].edgePrevious = edgesCount;
			}
			else if (edges[last_edge].vertexTo == vertexFrom)
			{
				edges[last_edge].edgeNext = edgesCount;
			}
			else
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): inconsistent vertices at first vertex");
				return;				
			}
		}		
		
		/* sort edge into edges incident on vertexTo */
	
		if (0 > vertices[vertexTo].edge)
		{
			vertices[vertexTo].edge = edgesCount;
			edges[edgesCount].edgeNext = edgesCount;
		}
		else
		{
			new_angle = Math.atan2(vertices[vertexFrom].y - vertices[vertexTo].y,
				vertices[vertexFrom].x - vertices[vertexTo].x);

			current_edge = -1;
			current_angle = 0.;
			do
			{
				last_edge = current_edge;
				last_angle = current_angle;
				if (-1 == current_edge)
				{
					current_edge = vertices[vertexTo].edge;			
				}
				else
				{
					current_edge = 
						getNextEdgeCounterClockWise(vertexTo, current_edge);
				}
				if (edges[current_edge].vertexFrom == vertexTo)
				{
					current_angle = 
						Math.atan2(vertices[edges[current_edge].vertexTo].y - 
						vertices[vertexTo].y,
						vertices[edges[current_edge].vertexTo].x - 
						vertices[vertexTo].x);
				}
				else
				{
					current_angle = 
						Math.atan2(vertices[edges[current_edge].vertexFrom].y - 
						vertices[vertexTo].y,
						vertices[edges[current_edge].vertexFrom].x - 
						vertices[vertexTo].x);
				}
			}
			while (-1 != current_edge && (-1 == last_edge || 
				(current_angle > last_angle && last_angle > new_angle) ||
				(current_angle > last_angle && current_angle < new_angle) ||
				(current_angle < last_angle && current_angle < new_angle &&
				last_angle > new_angle)));
			if (-1 == current_edge || -1 == last_edge)
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): failed at second vertex");
				return;
			}
			if (current_angle == new_angle || last_angle == new_angle)
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): degenerate edge (at second vertex)");
				return;
			}
			edges[edgesCount].edgeNext = current_edge;
			if (edges[last_edge].vertexFrom == vertexTo)
			{
				if (edges[last_edge].edgePrevious != current_edge)
				{
					System.out.println("error in insertEdge(" + vertexFrom +
						", " + vertexTo + "): inconsistent edges at second vertex");
					return;				
				}
				edges[last_edge].edgePrevious = edgesCount;
			}
			else if (edges[last_edge].vertexTo == vertexTo)
			{
				edges[last_edge].edgeNext = edgesCount;
			}
			else
			{
				System.out.println("error in insertEdge(" + vertexFrom +
					", " + vertexTo + "): inconsistent vertices at second vertex");
				return;				
			}
		}		
		
		edgesCount++;
	}

	void addNewFace(int edge, boolean is_right)
	{
		int vertex;
		int current_vertex;
		int current_edge = edge;
		
		faces[facesCount].edge = edge;
		faces[facesCount].faceIsRight = is_right;
		
		if (is_right)
		{
			vertex = edges[edge].vertexTo;
				/* we go clockwise around the face right of this edge */
		}
		else
		{
			vertex = edges[edge].vertexFrom;
				/* we go clockwise around the face left of this edge */
		}
		current_vertex = vertex;
		do
		{
			if (edges[current_edge].vertexTo == current_vertex)
			{
				edges[current_edge].faceRight = facesCount;
				current_edge = getNextEdgeCounterClockWise(current_vertex, 
					current_edge);	
			}
			else if (edges[current_edge].vertexFrom == current_vertex)
			{
				edges[current_edge].faceLeft = facesCount;
				current_edge = getNextEdgeCounterClockWise(current_vertex, 
					current_edge);	
			}
			else 
			{
				System.out.println("error in addNewFaceRight(...)");
			}
			if (current_vertex == edges[current_edge].vertexFrom)
			{
				current_vertex = edges[current_edge].vertexTo;
			}
			else if (current_vertex == edges[current_edge].vertexTo)
			{
				current_vertex = edges[current_edge].vertexFrom;
			}
			else
			{
				System.out.println("error in addNewFaceRight(...)");
			}
		}
		while (current_edge != edge || current_vertex != vertex);
		
		facesCount++;
	}
	
	/* 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 neighbors of scan vertex */
			
			setLineWidth(3.0);
			if (0 <= up_right_edge)
			{
				setColor(1.0, 0.5, 0.5);
				drawLine(vertices[edges[up_right_edge].vertexFrom].x,
					vertices[edges[up_right_edge].vertexFrom].y,
					vertices[edges[up_right_edge].vertexTo].x,
					vertices[edges[up_right_edge].vertexTo].y);
			}
			if (0 <= up_left_edge)
			{
				setColor(0.5, 1.0, 0.5);
				drawLine(vertices[edges[up_left_edge].vertexFrom].x,
					vertices[edges[up_left_edge].vertexFrom].y,
					vertices[edges[up_left_edge].vertexTo].x,
					vertices[edges[up_left_edge].vertexTo].y);
			}
			if (0 <= down_right_edge)
			{
				setColor(0.5, 0.5, 0.5);
				drawLine(vertices[edges[down_right_edge].vertexFrom].x,
					vertices[edges[down_right_edge].vertexFrom].y,
					vertices[edges[down_right_edge].vertexTo].x,
					vertices[edges[down_right_edge].vertexTo].y);
			}
			if (0 <= down_left_edge)
			{
				setColor(0.5, 0.5, 1.0);
				drawLine(vertices[edges[down_left_edge].vertexFrom].x,
					vertices[edges[down_left_edge].vertexFrom].y,
					vertices[edges[down_left_edge].vertexTo].x,
					vertices[edges[down_left_edge].vertexTo].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);
		}		
		
		/* render minimumVertices in yellow */

		for (index = 0; index < minimumVerticesCount; index++)
		{
			if (0 <= minimumVertices[index])
			{
				setPointSize(7.0);		
				setColor(1.0, 1.0, 0.0);
				drawPoint(vertices[minimumVertices[index]].x, 
					vertices[minimumVertices[index]].y);
			}
		}
		
		/* render faces in green */
		
		for (index = 0; index < facesCount; index++)
		{
			int current_edge = faces[index].edge;
			int first_vertex;
			int current_vertex;
			
			setColor(0.0, 1.0, 0.0);
			if (faces[index].faceIsRight)
			{
				first_vertex = edges[current_edge].vertexTo;
			}
			else
			{
				first_vertex = edges[current_edge].vertexFrom;
			}
			current_vertex = first_vertex;
			do
			{
				if (current_edge >= 0)
				{
					drawLine(vertices[edges[current_edge].vertexFrom].x,
						vertices[edges[current_edge].vertexFrom].y,
						vertices[edges[current_edge].vertexTo].x,
						vertices[edges[current_edge].vertexTo].y);
				}

				if (edges[current_edge].vertexTo == current_vertex)
				{
					current_edge = getNextEdgeCounterClockWise(current_vertex, 
						current_edge);	
				}
				else if (edges[current_edge].vertexFrom == current_vertex)
				{
					current_edge = getNextEdgeCounterClockWise(current_vertex, 
						current_edge);	
				}
				else 
				{
					System.out.println("error in display(...)");
				}
				if (current_vertex == edges[current_edge].vertexFrom)
				{
					current_vertex = edges[current_edge].vertexTo;
				}
				else if (current_vertex == edges[current_edge].vertexTo)
				{
					current_vertex = edges[current_edge].vertexFrom;
				}
				else
				{
					System.out.println("error in display(...)");
				}
			}
			while (current_edge != faces[index].edge || 
				current_vertex != first_vertex);		
		}
		
		/* 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);
	}
}