summaryrefslogtreecommitdiffstats
path: root/voronoi/cVertexList.java
diff options
context:
space:
mode:
Diffstat (limited to 'voronoi/cVertexList.java')
-rw-r--r--voronoi/cVertexList.java233
1 files changed, 233 insertions, 0 deletions
diff --git a/voronoi/cVertexList.java b/voronoi/cVertexList.java
new file mode 100644
index 0000000..bcd6fe4
--- /dev/null
+++ b/voronoi/cVertexList.java
@@ -0,0 +1,233 @@
+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);
+ }
+ }
+
+}