summaryrefslogblamecommitdiffstats
path: root/voronoi/cVertexList.java
blob: bcd6fe47b8ec2ce7df9a68f4fd535776a699aecb (plain) (tree)








































































































































































































































                                                                                               
package voronoi;

import java.awt.Color;
import java.awt.Graphics;

/**
 * Speichert verteces (Eckpunkte, Knoten, Punkte...)
 * 
 * @author
 * 
 */
class cVertexList {
	int n; // 0 means empty; 1 means one vertex; etc.

	int j;

	cVertex head;

	cVertexList() {
		head = null;
		n = 0;
	}

	public cVertex GetElement(int index) {

		cVertex v = new cVertex();
		if (index <= n) {
			v = head;
			for (int i = 0; i < index; i++)
				v = v.next;

		} else
			// element not found
			v = new cVertex(10000, 10000);

		return v;
	}

	public cVertex MakeNullVertex() {
		cVertex v = new cVertex();
		InsertBeforeHead(v);
		return v;
	}

	public void InitHead(cVertex h) {
		head = new cVertex();
		head = h;
		head.next = head.prev = head;
		n = 1;
	}

	public void ClearVertexList() {
		if (head != null)
			head = null;
		n = 0;
	}

	public void InsertBeforeHead(cVertex ver) {
		if (head == null)
			InitHead(ver);
		else {
			InsertBefore(ver, head);
		}
	}

	public void InsertBefore(cVertex newV, cVertex oldV) {
		if (head == null)
			InitHead(newV);
		else {
			oldV.prev.next = newV;
			newV.prev = oldV.prev;
			newV.next = oldV;
			oldV.prev = newV;
			n++;
		}
	}

	public void SetVertex(int x, int y) {
		cVertex v = new cVertex(x, y);
		InsertBeforeHead(v);
	}

	public void AddVertex(int x, int y) {
		cVertex v = new cVertex(x, y);
		// gets vertex of 1st vertex of the closest edge to the point
		cVertex vNear = GetEdge(x, y);
		if (vNear != null)
			InsertBefore(v, vNear.next);
	}

	public void ResetVertex(cVertex resV, int x, int y) {
		resV.v.x = x;
		resV.v.y = y;
	}

	public void ResetVertex(cVertex resV, int x, int y, int vnum, boolean mark) {
		resV.v.x = x;
		resV.v.y = y;
		resV.vnum = vnum;
		resV.mark = mark;
	}

	public void Delete(cVertex ver) {
		if (head == head.next)
			head = null;
		else if (ver == head)
			head = head.next;

		ver.prev.next = ver.next;
		ver.next.prev = ver.prev;
		n--;
	}

	public void ListPart(cVertexList list, int j) {
		int i = j;
		cVertex temp1 = head, temp2;
		do {
			i--;
			temp2 = new cVertex(); // Create a new vertex cell
			temp2.v = temp1.v; // Fill it with the same cPointi as in list
			temp2.mark = temp1.mark;
			temp2.ear = temp1.ear;
			temp2.duplicate = temp1.duplicate;
			temp2.onhull = temp1.onhull;
			temp2.vnum = temp1.vnum;
			list.InsertBeforeHead(temp2);
			temp1 = temp1.next;
		} while (i >= 0);
	}

	public void ListCopy(cVertexList list) {
		cVertex temp1 = head, temp2;
		do {
			temp2 = new cVertex(); // Create a new vertex cell
			temp2.v = temp1.v; // Fill it with the same cPointi as in list
			temp2.mark = temp1.mark;
			temp2.ear = temp1.ear;
			temp2.duplicate = temp1.duplicate;
			temp2.onhull = temp1.onhull;
			temp2.vnum = temp1.vnum;
			list.InsertBeforeHead(temp2);
			temp1 = temp1.next;
		} while (temp1 != head);
	}

	public cVertex GetNearVertex(int x, int y) {
		cVertex vnear = null, vtemp = head;
		double dist = -1.0, dx, dy, mindist = 0.0;

		if (vtemp == null)
			return vnear;

		do {
			dx = vtemp.v.x - x;
			dy = vtemp.v.y - y;
			dist = dx * dx + dy * dy;

			// Initialize on first pass (when vnear==null);
			// otherwise update if new winner
			if (vnear == null || dist < mindist) {
				mindist = dist;
				vnear = vtemp;
			}
			vtemp = vtemp.next;
		} while (vtemp != head);

		return vnear;
	}

	public cVertex FindVertex(int x, int y, int w, int h) {
		cVertex notfound = null;
		cVertex temp = head;

		if (n > 0) {
			do {
				temp = temp.next;
				if ((temp.v.x <= x + (w / 2)) && (temp.v.x >= x - (w / 2))
						&& (temp.v.y <= y + (h / 2))
						&& (temp.v.y >= y - (h / 2)))
					return temp;
			} while (temp != head);
		}
		return notfound;
	}

	public cVertex GetEdge(int x, int y) {
		cVertex vnear = null, vtemp = head;
		double mindist = 0.0, dist = -1.0;
		cPointi p = new cPointi();

		// input query point
		p.x = x;
		p.y = y;

		if (vtemp == null)
			return vnear;

		do {
			dist = p.DistEdgePoint(vtemp.v, vtemp.next.v, p);
			if (vnear == null || dist < mindist) {
				mindist = dist;
				vnear = vtemp;
			}
			vtemp = vtemp.next;
		} while (vtemp != head);

		return vnear;
	}

	/**
	 * zeichnet die vertices
	 * 
	 * @param g
	 * @param w
	 * @param h
	 */
	public void DrawPoints(Graphics g, int w, int h) {
		// vertex painting loop
		if (n == 0)
			System.out.println("No drawing is possible.");
		else {
			cVertex v = head;

			g.setColor(Color.black);
			do {
				g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h);
				v = v.next;
			} while (v != head.prev);
			g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h);
		}
	}

}