summaryrefslogtreecommitdiffstats
path: root/voronoi
diff options
context:
space:
mode:
authorRichard Zahoransky2011-11-07 16:29:56 +0100
committerRichard Zahoransky2011-11-07 16:29:56 +0100
commit08d5f7b0a0b24c042aa5976f66bf3a1b5b754478 (patch)
treeba5388774100c1b218cb264927c3bb3669fd7e06 /voronoi
parentinit (diff)
downloadlocalization-08d5f7b0a0b24c042aa5976f66bf3a1b5b754478.tar.gz
localization-08d5f7b0a0b24c042aa5976f66bf3a1b5b754478.tar.xz
localization-08d5f7b0a0b24c042aa5976f66bf3a1b5b754478.zip
Localization Code. How-To will follow...
Diffstat (limited to 'voronoi')
-rw-r--r--voronoi/Classtest.java36
-rw-r--r--voronoi/CompGeom.java35
-rw-r--r--voronoi/CompGeomTest.java132
-rw-r--r--voronoi/ConvexHull2D.java233
-rw-r--r--voronoi/DelaunayTri.java612
-rw-r--r--voronoi/GeomCanvas.java297
-rw-r--r--voronoi/cEdge.java23
-rw-r--r--voronoi/cEdgeList.java61
-rw-r--r--voronoi/cFace.java22
-rw-r--r--voronoi/cFaceList.java62
-rw-r--r--voronoi/cPointd.java15
-rw-r--r--voronoi/cPointi.java107
-rw-r--r--voronoi/cVertex.java51
-rw-r--r--voronoi/cVertexList.java233
-rw-r--r--voronoi/erstesVoronoi.pngbin0 -> 120990 bytes
-rw-r--r--voronoi/sweepLineVD.java73
-rw-r--r--voronoi/voronoi.java2228
17 files changed, 4220 insertions, 0 deletions
diff --git a/voronoi/Classtest.java b/voronoi/Classtest.java
new file mode 100644
index 0000000..9f13fde
--- /dev/null
+++ b/voronoi/Classtest.java
@@ -0,0 +1,36 @@
+package voronoi;
+class Parent {
+ public Parent() {
+
+ }
+}
+
+class Child extends Parent {
+ public Child() {
+ super();
+ }
+}
+
+public class Classtest {
+ public static void main(String[] a) {
+ Parent[] test = new Parent[3];
+ test[0] = new Parent();
+ test[1] = new Parent();
+ test[2] = new Child();
+
+ int count = 0;
+ for (Parent parent : test) {
+ System.out.print("Index " + count + " is of type: ");
+ if (parent instanceof Child) {
+ System.out.println("Children");
+ }
+ if (parent instanceof Parent) {
+ System.out.println("Parent");
+ }
+
+ count++;
+
+ }
+
+ }
+}
diff --git a/voronoi/CompGeom.java b/voronoi/CompGeom.java
new file mode 100644
index 0000000..93dcafa
--- /dev/null
+++ b/voronoi/CompGeom.java
@@ -0,0 +1,35 @@
+package voronoi;
+import java.applet.Applet;
+import java.awt.Button;
+import java.awt.Color;
+import java.awt.Event;
+import java.awt.FlowLayout;
+
+public class CompGeom extends Applet {
+ private static final long serialVersionUID = 1L;
+
+ private Button start;
+
+ private CompGeomTest test;
+
+ private int w, h;
+
+ public void init() {
+ start = new Button("Voronoi/Delaunay Applet...");
+ w = 900;
+ h = 550;
+ setLayout(new FlowLayout(FlowLayout.CENTER));
+ setBackground(Color.lightGray);
+ add(start);
+ }
+
+ public boolean action(Event e, Object o) {
+ if (e.target == start) {
+ test = new CompGeomTest(this);
+ test.setSize(w, h);
+ test.setResizable(false);
+ test.setVisible(true);
+ }
+ return true;
+ }
+}
diff --git a/voronoi/CompGeomTest.java b/voronoi/CompGeomTest.java
new file mode 100644
index 0000000..ebad8a9
--- /dev/null
+++ b/voronoi/CompGeomTest.java
@@ -0,0 +1,132 @@
+package voronoi;
+import java.applet.Applet;
+import java.awt.AWTEvent;
+import java.awt.BorderLayout;
+import java.awt.Button;
+import java.awt.Checkbox;
+import java.awt.Color;
+import java.awt.Event;
+import java.awt.Font;
+import java.awt.Frame;
+import java.awt.Panel;
+
+public class CompGeomTest extends Frame {
+ private static final long serialVersionUID = 1L;
+
+ private Button clear, close, simde, simvo;
+ private Checkbox hull, deltri, voronoi;
+
+ private Panel subp1, subp022, subp2, subp3, p,canvasp;
+ private GeomCanvas c;
+
+ private int cw, ch; // width and height for info frame and canvas
+
+ private Font f;
+
+ public CompGeomTest(Applet a) {
+ super("COSC 6114 Computational Geometry - Zhenyu Pan");
+ setBackground(Color.lightGray);
+
+ // cw = Integer.parseInt(a.getParameter("canvas width"));
+ cw = 750;
+ // ch = Integer.parseInt(a.getParameter("canvas height"));
+ ch = 550;
+
+ clear = new Button("Clear Screen");
+ close = new Button("Close Window");
+ simde = new Button("Simulation Delaunay");
+ simvo = new Button("Simulation Voronoi");
+ hull = new Checkbox("Show Convex Hull");
+ deltri = new Checkbox("Show Delaunay");
+ voronoi = new Checkbox("Show Voronoi");
+
+ subp1 = new Panel();
+ subp1.setLayout(new BorderLayout());
+ subp1.add("Center",clear);
+ subp1.add("South",close);
+
+ subp022 = new Panel();
+ subp022.setLayout(new BorderLayout());
+ subp022.add("Center",simde);
+ subp022.add("South",simvo);
+
+ subp3 = new Panel();
+ subp3.setLayout(new BorderLayout());
+ subp3.add("North",hull);
+ subp3.add("Center",deltri);
+ subp3.add("South",voronoi);
+
+ subp2 = new Panel();
+ subp2.setLayout(new BorderLayout());
+ subp2.add("North", subp1);
+ subp2.add("Center", subp022);
+ subp2.add("South", subp3);
+
+ p = new Panel();
+ p.setBackground(Color.lightGray);
+ p.setLayout(new BorderLayout());
+ p.add("North", subp2);
+
+ c = new GeomCanvas(cw, ch, this);
+ c.SetRegime("point");
+
+ canvasp = new Panel();
+ canvasp.setLayout(new BorderLayout());
+ canvasp.add("Center", c);
+
+ setLayout(new BorderLayout());
+ add("Center", canvasp);
+ add("East", p);
+
+ }
+
+ public boolean action(Event e, Object o) {
+ if (e.target instanceof Checkbox) {
+ Checkbox checkbox = (Checkbox) e.target;
+ if (e.target == hull)
+ c.ToCH(checkbox.getState());
+
+ if (e.target == deltri) {
+ c.ToDelTri(checkbox.getState());
+ }
+ if (e.target == voronoi){
+ c.ToVoronoi(checkbox.getState());
+ }
+ } // end of instanceof Checkbox
+
+ if (e.target instanceof Button) {
+ if (e.target == clear) {
+ c.ToBeCleared();// boolean variable
+ c.CoorClear();
+ c.SetPaint();
+ }
+ if (e.target == close) {
+ setVisible(false);
+ c.CoorClear();
+ c.animator=null;
+ }
+ if (e.target == simde) {
+ c.SimDe();// boolean variabble
+ }
+
+ if (e.target == simvo) {
+ c.SimVo();
+ }
+ }
+ return true;
+ }
+
+ public void processevent(AWTEvent e) {
+ if (e.getID() == Event.WINDOW_DESTROY) {
+ setVisible(false);
+ dispose();
+ return;
+ }
+ super.processEvent(e);
+ }
+
+ public void resetBLabel(Button bprev) {
+ bprev.setFont(f);
+ }
+
+}
diff --git a/voronoi/ConvexHull2D.java b/voronoi/ConvexHull2D.java
new file mode 100644
index 0000000..05cc07d
--- /dev/null
+++ b/voronoi/ConvexHull2D.java
@@ -0,0 +1,233 @@
+package voronoi;
+import java.awt.Graphics;
+
+class ConvexHull2D {
+
+ private cVertexList list, top;
+
+ private int ndelete = 0;
+
+ private int i = 0;
+
+ public ConvexHull2D(cVertexList list) {
+ if (list == null)
+ return;
+ if (list.head == null)
+ return;
+ this.list = new cVertexList();
+ cVertex v1 = new cVertex(list.head.v.x, list.head.v.y);
+ v1.vnum = list.head.vnum;
+ v1.mark = list.head.mark;
+
+ while (i < list.n) {
+ cVertex v3 = new cVertex(list.GetElement(i).v.x,
+ list.GetElement(i).v.y);
+ v3.mark = list.GetElement(i).mark;
+ v3.vnum = list.GetElement(i).vnum;
+
+ Push(v3, this.list);
+ i++;
+ }
+ }
+
+ public void ClearHull() {
+ top = new cVertexList();
+
+ }
+
+ public void RunHull() {
+
+ // initialization:
+ cVertex v = list.head;
+ for (i = 0; i < list.n; i++) {
+ v.vnum = i;
+ v = v.next;
+ }
+ //
+ FindLowest();
+ qsort(list);
+ if (ndelete > 0)
+ Squash();
+ top = Graham();
+ // top.PrintVertices();
+ }
+
+ private cVertexList Graham() {
+ cVertexList top;
+ int i;
+ top = new cVertexList();
+ cVertex v1 = new cVertex(list.head.v.x, list.head.v.y);
+ v1.vnum = list.head.vnum;
+ v1.mark = list.head.mark;
+
+ cVertex v2 = new cVertex(list.head.next.v.x, list.head.next.v.y);
+ v2.vnum = list.head.next.vnum;
+ v2.mark = list.head.next.mark;
+
+ Push(v1, top);
+ Push(v2, top);
+
+ // Bottom two elements will never be removed.
+ i = 2;
+
+ while (i < list.n) {
+ cVertex v3 = new cVertex(list.GetElement(i).v.x,
+ list.GetElement(i).v.y);
+ v3.mark = list.GetElement(i).mark;
+ v3.vnum = list.GetElement(i).vnum;
+
+ if (v1.v.Left(top.head.prev.v, top.head.prev.prev.v, v3.v)) {
+ Push(v3, top);
+ i++;
+ } else {
+ if (top.n > 2) {
+ Pop(top);
+ }
+ }
+
+ }
+
+ return top;
+
+ }
+
+ private void Squash() {
+ cVertex v = new cVertex();
+ v = list.head;
+ for (i = 0; i < list.n; i++) {
+ if (v.mark)
+ list.Delete(v);
+ v = v.next;
+ }
+ }
+
+ private void Sort(cVertexList a, int lo0, int hi0) {
+ if (lo0 >= hi0) {
+ return;
+ }
+ cVertex mid = new cVertex();
+ mid = a.GetElement(hi0);
+ int lo = lo0;
+ int hi = hi0 - 1;
+ while (lo <= hi) {
+ while (lo <= hi
+ && ((Compare(a.GetElement(lo), mid) == 1) || (Compare(a
+ .GetElement(lo), mid) == 0))) {
+ lo++;
+ }
+
+ while (lo <= hi
+ && ((Compare(a.GetElement(hi), mid) == -1) || (Compare(a
+ .GetElement(hi), mid) == 0))) {
+ hi--;
+ }
+
+ if (lo < hi) {
+ Swap(a.GetElement(lo), a.GetElement(hi));
+ }
+
+ }
+ Swap(a.GetElement(lo), a.GetElement(hi0));
+ Sort(a, lo0, lo - 1);
+ Sort(a, lo + 1, hi0);
+ }
+
+ private void qsort(cVertexList a) {
+ Sort(a, 1, a.n - 1);
+ }
+
+ private int Compare(cVertex tpi, cVertex tpj) {
+ int a; // area
+ int x, y; // projections of ri & rj in 1st quadrant
+ cVertex pi, pj;
+ pi = tpi;
+ pj = tpj;
+ cVertex myhead = new cVertex();
+ myhead = list.head;
+ a = myhead.v.AreaSign(myhead.v, pi.v, pj.v);
+ if (a > 0)
+ return -1;
+ else if (a < 0)
+ return 1;
+ else { // Collinear with list.head
+ x = Math.abs(pi.v.x - list.head.v.x)
+ - Math.abs(pj.v.x - list.head.v.x);
+ y = Math.abs(pi.v.y - list.head.v.y)
+ - Math.abs(pj.v.y - list.head.v.y);
+ ndelete++;
+
+ if ((x < 0) || (y < 0)) {
+ pi.mark = true;
+ return -1;
+ } else if ((x > 0) || (y > 0)) {
+ pj.mark = true;
+ return 1;
+ } else { // points are coincident
+
+ if (pi.vnum > pj.vnum)
+ pj.mark = true;
+ else
+ pi.mark = true;
+ return 0;
+
+ }
+ }
+ }
+
+ private void FindLowest() {
+ int i;
+ cVertex v1 = list.head.next;
+
+ for (i = 1; i < list.n; i++) {
+ if ((list.head.v.y < v1.v.y)
+ || ((v1.v.y == list.head.v.y) && (v1.v.x > list.head.v.x))) {
+ Swap(list.head, v1);
+ }
+ v1 = v1.next;
+
+ }
+ }
+
+ private void Swap(cVertex first, cVertex second) {
+ cVertex temp = new cVertex();
+
+ temp = new cVertex(first.v.x, first.v.y);
+ temp.vnum = first.vnum;
+ temp.mark = first.mark;
+
+ list.ResetVertex(first, second.v.x, second.v.y, second.vnum,
+ second.mark);
+ list.ResetVertex(second, temp.v.x, temp.v.y, temp.vnum, temp.mark);
+
+ }
+
+ private void Push(cVertex p, cVertexList top) {
+ // simulating a stack behavior for cVertexList list
+ top.InsertBeforeHead(p);
+ }
+
+ private void Pop(cVertexList top) {
+ top.Delete(top.head.prev);
+ }
+
+ public void DrawHull(Graphics gContext, int w, int h) {
+
+ if (top.n == 0 || top.head == null)
+ System.out.println("No drawing is possible.");
+ else {
+ cVertex v1 = top.head;
+
+ if (top.n > 2) {
+ do {
+ gContext.drawLine(v1.v.x, v1.v.y, v1.next.v.x, v1.next.v.y);
+ v1 = v1.next;
+ } while (v1 != top.head);
+
+ }
+
+ }
+ if (list.head != null)
+ list.DrawPoints(gContext, w, h);
+ }
+
+}
diff --git a/voronoi/DelaunayTri.java b/voronoi/DelaunayTri.java
new file mode 100644
index 0000000..cc30f47
--- /dev/null
+++ b/voronoi/DelaunayTri.java
@@ -0,0 +1,612 @@
+package voronoi;
+import java.awt.Canvas;
+import java.awt.Color;
+import java.awt.Graphics;
+
+public class DelaunayTri {
+
+ private static final boolean ONHULL = true;
+
+ private static final boolean REMOVED = true;
+
+ private static final boolean VISIBLE = true;
+
+ private static final boolean PROCESSED = true;
+
+ private static final int SAFE = 1000000;
+
+ boolean toDraw;
+
+ // for simulation
+ boolean DeSim;
+
+ Graphics g;
+
+ Canvas c;
+
+ int w;
+
+ int h;
+
+ private cVertexList list;
+
+ private cEdgeList elist;
+
+ private cFaceList flist;
+
+ DelaunayTri(cVertexList list) {
+ this.list = list;
+ elist = new cEdgeList();
+ flist = new cFaceList();
+ toDraw = DeSim = false;
+ g = null;
+ c = null;
+ w = 0;
+ h = 0;
+ }
+
+ public void DeSim(boolean desim, Graphics Deg, int Dew, int Deh, Canvas Can) {
+ DeSim = desim;
+ c = Can;
+ g = Deg;
+ w = Dew;
+ h = Deh;
+ }
+
+ public void Start(cVertexList listOld) {
+ this.list = new cVertexList();
+ listOld.ListCopy(this.list);
+ ReadVertices();
+ if (DoubleTriangle()) {
+ toDraw = true;
+ ConstructHull();
+ LowerFaces();
+ }
+ }
+
+ public void ClearDelaunay() {
+ elist.ClearEdgeList();
+ flist.ClearFaceList();
+ toDraw = false;
+ }
+
+ public void ReadVertices() {
+ int vnum = 0;
+ cVertex v = list.head;
+ do {
+ v.ResetVertex3D();
+ v.vnum = vnum++;
+ if ((Math.abs(v.v.x) > SAFE) || (Math.abs(v.v.y) > SAFE)
+ || (Math.abs(v.v.z) > SAFE)) {
+ System.out
+ .println("Coordinate of vertex below might be too large...");
+ }
+ v = v.next;
+ } while (v != list.head);
+ }
+
+ private void LowerFaces() {
+ cFace f = flist.head;
+ int Flower = 0;
+
+ do {
+ if (Normz(f) < 0) {
+ Flower++;
+ f.lower = true;
+ } else {
+ if (DeSim) {
+ g.setColor(Color.lightGray);
+ DrawDelaunayTri(g, w, h);
+ c.repaint();
+ }
+ f.lower = false;
+ if (DeSim) {
+ g.setColor(Color.blue);
+ DrawDelaunayTri(g, w, h);
+ c.repaint();
+ try {
+ Thread.sleep(1000);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ }
+ }
+ f = f.next;
+ } while (f != flist.head);
+ }
+
+ private boolean DoubleTriangle() {
+ cVertex v0, v1, v2, v3;
+ cFace f0, f1 = null;
+ int vol;
+
+ v0 = list.head;
+ while (Collinear(v0, v0.next, v0.next.next))
+ if ((v0 = v0.next) == list.head) {
+ System.out
+ .println("DoubleTriangle: All points are Collinear!");
+ return false;
+ }
+ v1 = v0.next;
+ v2 = v1.next;
+
+ v0.mark = PROCESSED;
+ v1.mark = PROCESSED;
+ v2.mark = PROCESSED;
+
+ f0 = MakeFace(v0, v1, v2, f1);
+ f1 = MakeFace(v2, v1, v0, f0);
+
+ f0.edge[0].adjface[1] = f1;
+ f0.edge[1].adjface[1] = f1;
+ f0.edge[2].adjface[1] = f1;
+ f1.edge[0].adjface[1] = f0;
+ f1.edge[1].adjface[1] = f0;
+ f1.edge[2].adjface[1] = f0;
+
+ v3 = v2.next;
+ vol = VolumeSign(f0, v3);
+ while (vol == 0) {
+ if ((v3 = v3.next) == v0) {
+ System.out.println("DoubleTriangle: All points are coplanar!");
+ return false;
+ }
+ vol = VolumeSign(f0, v3);
+ }
+
+ list.head = v3;
+ return true;
+ }
+
+ private void ConstructHull() {
+ cVertex v, vnext;
+
+ v = list.head;
+ do {
+ vnext = v.next;
+ if (!v.mark) {
+ v.mark = PROCESSED;
+ if (DeSim) {
+ g.setColor(Color.lightGray);
+ DrawRest(g, w, h);
+ c.repaint();
+ }
+ AddOne(v);
+ if (DeSim) {
+ g.setColor(Color.blue);
+ DrawRest(g, w, h);
+ c.repaint();
+ try {
+ Thread.sleep(1000);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ }
+ if (DeSim) {
+ g.setColor(Color.lightGray);
+ DrawRest(g, w, h);
+ c.repaint();
+ }
+ CleanUp();
+ if (DeSim) {
+ g.setColor(Color.blue);
+ DrawRest(g, w, h);
+ c.repaint();
+ try {
+ Thread.sleep(1000);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ }
+ }
+ v = vnext;
+ } while (v != list.head);
+ }
+
+ private boolean AddOne(cVertex p) {
+ cFace f;
+ cEdge e;
+ int vol;
+ boolean vis = false;
+
+ f = flist.head;
+ do {
+ vol = VolumeSign(f, p);
+ if (vol < 0) {
+ f.visible = VISIBLE;
+ vis = true;
+ }
+ f = f.next;
+ } while (f != flist.head);
+
+ if (!vis) {
+ p.onhull = !ONHULL;
+ return false;
+ }
+
+ e = elist.head;
+ do {
+ cEdge temp;
+ temp = e.next;
+ if (e.adjface[0].visible && e.adjface[1].visible) {
+ e.delete = REMOVED;
+ } else if (e.adjface[0].visible || e.adjface[1].visible) {
+ e.newface = MakeConeFace(e, p);
+ }
+ e = temp;
+ } while (e != elist.head);
+ return true;
+ }
+
+ private int VolumeSign(cFace f, cVertex p) {
+ double vol;
+ double ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
+ double bxdx, bydy, bzdz, cxdx, cydy, czdz;
+
+ ax = f.vertex[0].v.x;
+ ay = f.vertex[0].v.y;
+ az = f.vertex[0].v.z;
+ bx = f.vertex[1].v.x;
+ by = f.vertex[1].v.y;
+ bz = f.vertex[1].v.z;
+ cx = f.vertex[2].v.x;
+ cy = f.vertex[2].v.y;
+ cz = f.vertex[2].v.z;
+ dx = p.v.x;
+ dy = p.v.y;
+ dz = p.v.z;
+
+ bxdx = bx - dx;
+ bydy = by - dy;
+ bzdz = bz - dz;
+ cxdx = cx - dx;
+ cydy = cy - dy;
+ czdz = cz - dz;
+ vol = (az - dz) * (bxdx * cydy - bydy * cxdx) + (ay - dy)
+ * (bzdz * cxdx - bxdx * czdz) + (ax - dx)
+ * (bydy * czdz - bzdz * cydy);
+
+ if (vol > 0.5)
+ return 1;
+ else if (vol < -0.5)
+ return -1;
+ else
+ return 0;
+ }
+
+ private cFace MakeConeFace(cEdge e, cVertex p) {
+ cEdge new_edge[] = new cEdge[2];
+ cFace new_face;
+ int i, j;
+
+ for (i = 0; i < 2; ++i) {
+ new_edge[i] = e.endpts[i].duplicate;
+ if (new_edge[i] == null) {
+ new_edge[i] = elist.MakeNullEdge();
+ new_edge[i].endpts[0] = e.endpts[i];
+ new_edge[i].endpts[1] = p;
+ e.endpts[i].duplicate = new_edge[i];
+ }
+ }
+
+ new_face = flist.MakeNullFace();
+ new_face.edge[0] = e;
+ new_face.edge[1] = new_edge[0];
+ new_face.edge[2] = new_edge[1];
+ MakeCcw(new_face, e, p);
+
+ for (i = 0; i < 2; ++i)
+ for (j = 0; j < 2; ++j)
+ if (new_edge[i].adjface[j] == null) {
+ new_edge[i].adjface[j] = new_face;
+ break;
+ }
+
+ return new_face;
+ }
+
+ private void MakeCcw(cFace f, cEdge e, cVertex p) {
+ cFace fv;
+ int i;
+ cEdge s = new cEdge();
+
+ if (e.adjface[0].visible)
+ fv = e.adjface[0];
+ else
+ fv = e.adjface[1];
+
+ for (i = 0; fv.vertex[i] != e.endpts[0]; ++i)
+ ;
+ if (fv.vertex[(i + 1) % 3] != e.endpts[1]) {
+ f.vertex[0] = e.endpts[1];
+ f.vertex[1] = e.endpts[0];
+ } else {
+ f.vertex[0] = e.endpts[0];
+ f.vertex[1] = e.endpts[1];
+ Swap(s, f.edge[1], f.edge[2]);
+ }
+
+ f.vertex[2] = p;
+ }
+
+ private cFace MakeFace(cVertex v0, cVertex v1, cVertex v2, cFace fold) {
+ cFace f;
+ cEdge e0, e1, e2;
+
+ if (fold == null) {
+ e0 = elist.MakeNullEdge();
+ e1 = elist.MakeNullEdge();
+ e2 = elist.MakeNullEdge();
+ } else {
+ e0 = fold.edge[2];
+ e1 = fold.edge[1];
+ e2 = fold.edge[0];
+ }
+ e0.endpts[0] = v0;
+ e0.endpts[1] = v1;
+ e1.endpts[0] = v1;
+ e1.endpts[1] = v2;
+ e2.endpts[0] = v2;
+ e2.endpts[1] = v0;
+
+ f = flist.MakeNullFace();
+ f.edge[0] = e0;
+ f.edge[1] = e1;
+ f.edge[2] = e2;
+ f.vertex[0] = v0;
+ f.vertex[1] = v1;
+ f.vertex[2] = v2;
+
+ e0.adjface[0] = e1.adjface[0] = e2.adjface[0] = f;
+
+ return f;
+ }
+
+ private void CleanUp() {
+ CleanEdges();
+ CleanFaces();
+ CleanVertices();
+ }
+
+ private void CleanEdges() {
+ cEdge e;
+ cEdge t;
+
+ e = elist.head;
+ do {
+ if (e.newface != null) {
+ if (e.adjface[0].visible)
+ e.adjface[0] = e.newface;
+ else
+ e.adjface[1] = e.newface;
+ e.newface = null;
+ }
+ e = e.next;
+ } while (e != elist.head);
+
+ while (elist.head != null && elist.head.delete) {
+ e = elist.head;
+ elist.Delete(e);
+ }
+ e = elist.head.next;
+ do {
+ if (e.delete) {
+ t = e;
+ e = e.next;
+ elist.Delete(t);
+
+ } else
+ e = e.next;
+ } while (e != elist.head);
+ }
+
+ private void CleanFaces() {
+ cFace f;
+ cFace t;
+
+ while (flist.head != null && flist.head.visible) {
+ f = flist.head;
+ flist.Delete(f);
+ }
+ f = flist.head.next;
+ do {
+ if (f.visible) {
+ t = f;
+ f = f.next;
+ flist.Delete(t);
+ } else
+ f = f.next;
+ } while (f != flist.head);
+ }
+
+ private void CleanVertices() {
+ cEdge e;
+ cVertex v, t;
+
+ e = elist.head;
+ do {
+ e.endpts[0].onhull = e.endpts[1].onhull = ONHULL;
+ e = e.next;
+ } while (e != elist.head);
+
+ while (list.head != null && list.head.mark && !list.head.onhull) {
+ v = list.head;
+ list.Delete(v);
+ }
+ v = list.head.next;
+ do {
+ if (v.mark && !v.onhull) {
+ t = v;
+ v = v.next;
+ list.Delete(t);
+ } else
+ v = v.next;
+ } while (v != list.head);
+
+ v = list.head;
+ do {
+ v.duplicate = null;
+ v.onhull = !ONHULL;
+ v = v.next;
+ } while (v != list.head);
+ }
+
+ private boolean Collinear(cVertex a, cVertex b, cVertex c) {
+ return (c.v.z - a.v.z) * (b.v.y - a.v.y) - (b.v.z - a.v.z)
+ * (c.v.y - a.v.y) == 0
+ && (b.v.z - a.v.z) * (c.v.x - a.v.x) - (b.v.x - a.v.x)
+ * (c.v.z - a.v.z) == 0
+ && (b.v.x - a.v.x) * (c.v.y - a.v.y) - (b.v.y - a.v.y)
+ * (c.v.x - a.v.x) == 0;
+ }
+
+ private int Normz(cFace f) {
+ cVertex a, b, c;
+
+ a = f.vertex[0];
+ b = f.vertex[1];
+ c = f.vertex[2];
+
+ return (b.v.x - a.v.x) * (c.v.y - a.v.y) - (b.v.y - a.v.y)
+ * (c.v.x - a.v.x);
+ }
+
+ private void Swap(cEdge t, cEdge x, cEdge y) {
+ t = x;
+ x = y;
+ y = t;
+ }
+
+ public void DrawDelaunayTri(Graphics g, int w, int h) {
+ cVertex v;
+ cFace f;
+ int V = 0, F = 0;
+
+ v = list.head;
+ do {
+ if (v.mark)
+ V++;
+ v = v.next;
+ } while (v != list.head);
+
+ f = flist.head;
+ do {
+ ++F;
+ f = f.next;
+ } while (f != flist.head);
+ do {
+ if (f.lower) {
+ if (flist.n >= 2) {
+ g.drawLine(f.vertex[0].v.x, f.vertex[0].v.y,
+ f.vertex[1].v.x, f.vertex[1].v.y);
+ g.drawLine(f.vertex[1].v.x, f.vertex[1].v.y,
+ f.vertex[2].v.x, f.vertex[2].v.y);
+ g.drawLine(f.vertex[2].v.x, f.vertex[2].v.y,
+ f.vertex[0].v.x, f.vertex[0].v.y);
+ }
+ }
+ f = f.next;
+ } while (f != flist.head);
+ do {
+ g.setColor(Color.black);
+ g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h);
+ v = v.next;
+ } while (v != list.head);
+
+ }
+
+ void out_triple(Graphics g, cVertex s1, cVertex s2, cVertex s3) {
+
+ double P1X = s1.v.x;
+ double P1Y = s1.v.y;
+ double P2X = s2.v.x;
+ double P2Y = s2.v.y;
+ double P3X = s3.v.x;
+ double P3Y = s3.v.y;
+
+ double l1a = P2X - P1X;
+ double l1b = P2Y - P1Y;
+ double l1c = (P1Y * P1Y - P2Y * P2Y + P1X * P1X - P2X * P2X) * 0.5000;
+ double l2a = P2X - P3X;
+ double l2b = P2Y - P3Y;
+ double l2c = (P3Y * P3Y - P2Y * P2Y + P3X * P3X - P2X * P2X) * 0.5000;
+
+ if (l1a * l2b == l1b * l2a)
+ return;
+ double x = (l1c * l2b - l1b * l2c) / (l1b * l2a - l1a * l2b);
+ double y = (l1a * l2c - l1c * l2a) / (l1b * l2a - l1a * l2b);
+
+ double d = Math.sqrt(Math.pow(s1.v.x - x, 2)
+ + Math.pow(s1.v.y - y, 2));
+
+ g.setColor(Color.blue);
+ g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P2X - (int) (w / 2), (int) P2Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P3X - (int) (w / 2), (int) P3Y - (int) (h / 2), w,
+ h);
+ g.setColor(Color.red);
+ g.drawOval((int) (x - d), (int) (y - d), (int) (2 * d),
+ (int) (2 * d));
+ }
+
+ public void DrawCircle(Graphics g, int w, int h) {
+ cVertex v;
+ cFace f;
+ int V = 0, F = 0;
+
+ v = list.head;
+ do {
+ if (v.mark)
+ V++;
+ v = v.next;
+ } while (v != list.head);
+
+ f = flist.head;
+ do {
+ if(f.lower)
+ out_triple( g, f.vertex[0],f.vertex[1],f.vertex[2]);
+ ++F;
+ f = f.next;
+ } while (f != flist.head);
+ }
+
+
+ public void DrawRest(Graphics g, int w, int h) {
+ cVertex v;
+ cFace f;
+ int V = 0, F = 0;
+
+ v = list.head;
+ do {
+ if (v.mark)
+ V++;
+ v = v.next;
+ } while (v != list.head);
+
+ f = flist.head;
+ do {
+ ++F;
+ f = f.next;
+ } while (f != flist.head);
+ do {
+ if (flist.n >= 2) {
+ g.drawLine(f.vertex[0].v.x, f.vertex[0].v.y, f.vertex[1].v.x,
+ f.vertex[1].v.y);
+ g.drawLine(f.vertex[1].v.x, f.vertex[1].v.y, f.vertex[2].v.x,
+ f.vertex[2].v.y);
+ g.drawLine(f.vertex[2].v.x, f.vertex[2].v.y, f.vertex[0].v.x,
+ f.vertex[0].v.y);
+ }
+ f = f.next;
+ } while (f != flist.head);
+
+ do {
+ g.setColor(Color.black);
+ g.fillOval(v.v.x - (int) (w / 2), v.v.y - (int) (h / 2), w, h);
+ v = v.next;
+ } while (v != list.head);
+ }
+
+}
diff --git a/voronoi/GeomCanvas.java b/voronoi/GeomCanvas.java
new file mode 100644
index 0000000..33dc431
--- /dev/null
+++ b/voronoi/GeomCanvas.java
@@ -0,0 +1,297 @@
+package voronoi;
+import java.awt.AWTEvent;
+import java.awt.Canvas;
+import java.awt.Color;
+import java.awt.Graphics;
+import java.awt.Image;
+import java.awt.event.MouseEvent;
+
+
+public class GeomCanvas extends Canvas implements Runnable {
+
+ private static final long serialVersionUID = 1L;
+
+ static final int VSIZE = 6;
+
+ private cVertexList list;
+
+ private DelaunayTri delTri;
+
+ private ConvexHull2D myCH;
+
+ private voronoi myVor;
+
+ private boolean toClear, simde, simvo, toPaint, toDelTri, toCH, toVoronoi;
+
+ private cVertex movingV;
+
+ private Graphics gContext; // variables for double buffering
+
+ private Image buffer;
+
+ private int CanW, CanH; // width and height of the drawing canvas
+
+ private int w = VSIZE, h = VSIZE; // w. and h. of vertices
+
+ Thread animator;
+
+ GeomCanvas(int cw, int ch, CompGeomTest frame) {
+ setSize(cw, ch);
+ CanW = cw;
+ CanH = ch;
+ setBackground(Color.lightGray);
+ toClear = simde = simvo = false;
+ toPaint = toDelTri = toCH = false;
+ list = new cVertexList();
+ myCH = new ConvexHull2D(list);
+ delTri = new DelaunayTri(list);
+ myVor = new voronoi();
+ enableEvents(AWTEvent.MOUSE_EVENT_MASK);
+ enableEvents(AWTEvent.MOUSE_MOTION_EVENT_MASK);
+ start();
+ }
+
+ public void SetRegime(String state) {
+ }
+
+ public void ToBeCleared() {
+ toClear = true;
+ repaint();
+ }
+
+ public void ToDelTri(boolean iftrue) {
+ toPaint = true;
+ toDelTri = iftrue;
+ repaint();
+ }
+
+ public void ToVoronoi(boolean iftrue) {
+ toPaint = true;
+ toVoronoi = iftrue;
+ repaint();
+ }
+
+ public void ToCH(boolean iftrue) {
+ toPaint = true;
+ toCH = iftrue;
+ repaint();
+ }
+
+ public void CoorClear() {
+ list.ClearVertexList();
+ myCH.ClearHull();
+ delTri.ClearDelaunay();
+ simde = false;
+ simvo = false;
+ toPaint = false;
+ repaint();
+ }
+
+ public void SimDe() {
+ simde = true;
+ toPaint = true;
+ repaint();
+ }
+
+ public void SimVo() {
+ simvo = true;
+ toPaint = true;
+ repaint();
+ }
+
+ public int GetCount() {
+ return list.n;
+ }
+
+ public void paint(Graphics g) {
+ if (toClear) {
+ g.setColor(Color.lightGray);
+ g.fillRect(0, 0, CanW, CanH);
+ CoorClear();
+ toClear = false;
+ }
+
+ if (toPaint) {
+ if (list == null)
+ return;
+ if (list.head == null)
+ return;
+ if (simde) {
+ g.drawImage(buffer, 0, 0, this);
+ return;
+ }
+ if(simvo){
+ g.drawImage(buffer, 0, 0, this);
+ return;
+ }
+ buffer = createImage(CanW, CanH);
+ gContext = buffer.getGraphics();
+
+ if (toDelTri) {
+ delTri.Start(list);
+ if (delTri.toDraw) {
+ gContext.setColor(Color.blue);
+ delTri.DrawDelaunayTri(gContext, w, h);
+ }
+ }
+ if (toVoronoi) {
+ myVor = new voronoi();
+ gContext.setColor(Color.red);
+ myVor.Sort(list);
+ myVor.DrawVor(gContext);
+ }
+ if (toCH) {
+ myCH = new ConvexHull2D(list);
+ myCH.RunHull();
+ gContext.setColor(Color.green);
+ myCH.DrawHull(gContext, w, h);
+ }
+ list.DrawPoints(gContext, w, h);
+
+ g.drawImage(buffer, 0, 0, this);
+ myCH.ClearHull();
+ delTri.ClearDelaunay();
+ myVor.dVoronoiDiagramGenerator();
+ toPaint = false;
+
+ }
+ }
+
+ public void update(Graphics g) {
+ paint(g);
+ }
+
+ public void SetPaint() // needed for the applet
+ {
+ repaint();
+ }
+
+ public void processMouseMotionEvent(MouseEvent e) {
+ int xset = 0, yset = 0;
+ cVertexList listCur = list;
+ if (e.getID() != MouseEvent.MOUSE_DRAGGED)
+ return;
+ xset = e.getX();
+ yset = e.getY();
+ if (movingV == null) {
+ movingV = listCur.FindVertex(xset, yset, w, h);
+ if (movingV == null) {
+ System.out.println("There is no vertex to be moved");
+ return;
+ }
+ }
+ listCur.ResetVertex(movingV, xset, yset);
+ toPaint = true;
+ repaint();
+
+ }
+
+ public void processMouseEvent(MouseEvent e) {
+ int xset = 0, yset = 0;
+ cVertex vNear = new cVertex();
+ cVertexList listCur = list;
+
+ if (e.getID() != MouseEvent.MOUSE_CLICKED
+ && e.getID() != MouseEvent.MOUSE_RELEASED)
+ return;
+ if (e.getID() == MouseEvent.MOUSE_RELEASED)
+ movingV = null;
+
+ xset = e.getX();
+ yset = e.getY();
+ if (e.getID() == MouseEvent.MOUSE_CLICKED
+ && e.getButton() == MouseEvent.BUTTON1) {
+ listCur.SetVertex(xset, yset);
+ toPaint = true;
+ // list.PrintVertices();
+ repaint();
+ }
+ if (e.getID() == MouseEvent.MOUSE_CLICKED
+ && e.getButton() == MouseEvent.BUTTON3) {
+ vNear = listCur.GetNearVertex(xset, yset);
+ if (vNear != null) {
+ listCur.Delete(vNear);
+ if (listCur.n == 0) {
+ toClear = true;
+ CoorClear();
+ }
+ } else
+ System.out.println("No vertex can be deleted.");
+ toPaint = true;
+ repaint();
+ }
+ }
+
+ public void run() {
+ while (Thread.currentThread() == animator) {
+ if (simde) {
+ gContext.setColor(Color.lightGray);
+ gContext.fillRect(0, 0, CanW, CanH);
+ list.DrawPoints(gContext, w, h);
+ delTri.DeSim(true, gContext, w, h,this);
+ toPaint = true;
+ delTri.Start(list);
+ delTri.DeSim(false, null, 0, 0,null);
+ if (delTri.toDraw) {
+ gContext.setColor(Color.blue);
+ delTri.DrawDelaunayTri(gContext, w, h);
+ delTri.DrawCircle(gContext, w, h);
+ toPaint = true;
+ list.DrawPoints(gContext, w, h);
+ repaint();
+ try {
+ Thread.sleep(1200);
+ }
+ catch (InterruptedException e) {
+ break;
+ }
+ }
+ simde = false;
+ buffer = createImage(CanW, CanH);
+ gContext = buffer.getGraphics();
+ delTri.ClearDelaunay();
+ toPaint = false;
+ }
+ else if (simvo) {
+ gContext.setColor(Color.lightGray);
+ gContext.fillRect(0, 0, CanW, CanH);
+ list.DrawPoints(gContext, w, h);
+ myVor = new voronoi();
+ myVor.VorSim(true, gContext, w, h,this);
+ myVor.Sort(list);
+ gContext.setColor(Color.red);
+ myVor.DrawVor(gContext);
+ list.DrawPoints(gContext, w, h);
+ toPaint = true;
+ repaint();
+ try {
+
+ Thread.sleep(1200);
+ } catch (InterruptedException e) {
+ break;
+ }
+ simvo = false;
+ buffer = createImage(CanW, CanH);
+ gContext = buffer.getGraphics();
+ toPaint = false;
+ }
+ try {
+
+ Thread.sleep(100);
+ } catch (InterruptedException e) {
+ break;
+ }
+
+ }
+ }
+
+ public void start() {
+ animator = new Thread(this);
+ animator.start();
+ }
+
+ public void stop() {
+ animator = null;
+ CoorClear();
+ }
+} \ No newline at end of file
diff --git a/voronoi/cEdge.java b/voronoi/cEdge.java
new file mode 100644
index 0000000..1b7e6d8
--- /dev/null
+++ b/voronoi/cEdge.java
@@ -0,0 +1,23 @@
+package voronoi;
+public class cEdge {
+
+ cFace adjface[];
+
+ cVertex endpts[];
+
+ cFace newface;
+
+ boolean delete;
+
+ cEdge next, prev;
+
+ cEdge() {
+ adjface = new cFace[2];
+ adjface[0] = adjface[1] = null;
+ endpts = new cVertex[2];
+ endpts[0] = endpts[1] = null;
+ newface = null;
+ delete = false;
+ next = prev = null;
+ }
+}
diff --git a/voronoi/cEdgeList.java b/voronoi/cEdgeList.java
new file mode 100644
index 0000000..ad75511
--- /dev/null
+++ b/voronoi/cEdgeList.java
@@ -0,0 +1,61 @@
+package voronoi;
+class cEdgeList {
+ int n;
+ cEdge head;
+
+ cEdgeList() {
+ head = null;
+ n = 0;
+ }
+
+ public void InitHead(cEdge h) {
+ head = new cEdge();
+ head = h;
+ head.next = head.prev = head;
+ n = 1;
+ }
+
+ public void InsertBefore(cEdge newE, cEdge oldE) {
+ if (head == null)
+ InitHead(newE);
+ else {
+ oldE.prev.next = newE;
+ newE.prev = oldE.prev;
+ newE.next = oldE;
+ oldE.prev = newE;
+ n++;
+ }
+ }
+
+ public void InsertBeforeHead(cEdge e) {
+ if (head == null)
+ InitHead(e);
+ else {
+ InsertBefore(e, head);
+ }
+ }
+
+ public cEdge MakeNullEdge() {
+ cEdge e = new cEdge();
+ InsertBeforeHead(e);
+ return e;
+ }
+
+ public void Delete(cEdge e) {
+
+ if (head == head.next)
+ head = null;
+ else if (e == head)
+ head = head.next;
+
+ e.prev.next = e.next;
+ e.next.prev = e.prev;
+ n--;
+ }
+
+ public void ClearEdgeList() {
+ if (head != null)
+ head = null;
+ n = 0;
+ }
+}
diff --git a/voronoi/cFace.java b/voronoi/cFace.java
new file mode 100644
index 0000000..034fd9e
--- /dev/null
+++ b/voronoi/cFace.java
@@ -0,0 +1,22 @@
+package voronoi;
+public class cFace {
+
+ cEdge edge[];
+
+ cVertex vertex[];
+
+ boolean visible;
+ boolean lower;
+
+ cFace next, prev;
+
+ cFace() {
+ edge = new cEdge[3];
+ edge[0] = edge[1] = edge[2] = null;
+ vertex = new cVertex[3];
+ vertex[0] = vertex[1] = vertex[2] = null;
+ visible =false;
+ lower = true;
+ next = prev = null;
+ }
+}
diff --git a/voronoi/cFaceList.java b/voronoi/cFaceList.java
new file mode 100644
index 0000000..a80bc4b
--- /dev/null
+++ b/voronoi/cFaceList.java
@@ -0,0 +1,62 @@
+package voronoi;
+class cFaceList {
+ int n;
+
+ cFace head;
+
+ cFaceList() {
+ head = null;
+ n = 0;
+ }
+
+ public void InitHead(cFace h) {
+ head = new cFace();
+ head = h;
+ head.next = head.prev = head;
+ n = 1;
+ }
+
+ public void InsertBefore(cFace newF, cFace oldF) {
+ if (head == null)
+ InitHead(newF);
+ else {
+ oldF.prev.next = newF;
+ newF.prev = oldF.prev;
+ newF.next = oldF;
+ oldF.prev = newF;
+ n++;
+ }
+ }
+
+ public void InsertBeforeHead(cFace e) {
+ if (head == null)
+ InitHead(e);
+ else {
+ InsertBefore(e, head);
+ }
+ }
+
+ public cFace MakeNullFace() {
+ cFace f = new cFace();
+ InsertBeforeHead(f);
+ return f;
+ }
+
+ public void Delete(cFace e) {
+
+ if (head == head.next)
+ head = null;
+ else if (e == head)
+ head = head.next;
+
+ e.prev.next = e.next;
+ e.next.prev = e.prev;
+ n--;
+ }
+
+ public void ClearFaceList() {
+ if (head != null)
+ head = null;
+ n = 0;
+ }
+}
diff --git a/voronoi/cPointd.java b/voronoi/cPointd.java
new file mode 100644
index 0000000..1254b36
--- /dev/null
+++ b/voronoi/cPointd.java
@@ -0,0 +1,15 @@
+package voronoi;
+class cPointd {
+ double x;
+
+ double y;
+
+ cPointd() {
+ x = y = 0;
+ }
+
+ cPointd(int x, int y) {
+ this.x = x;
+ this.y = y;
+ }
+}
diff --git a/voronoi/cPointi.java b/voronoi/cPointi.java
new file mode 100644
index 0000000..c538c28
--- /dev/null
+++ b/voronoi/cPointi.java
@@ -0,0 +1,107 @@
+package voronoi;
+class cPointi {
+ int x;
+
+ int y;
+
+ int z;
+
+ cPointi() {
+ x = y = z = 0;
+ }
+
+ cPointi(int x, int y) {
+ this.x = x;
+ this.y = y;
+ this.z = 0;
+ }
+
+ cPointi(int x, int y, int z) {
+ this.x = x;
+ this.y = y;
+ this.z = z;
+ }
+
+ public int Area2(cPointi a, cPointi b, cPointi c) {
+ int area = ((c.x - b.x) * (a.y - b.y)) - ((a.x - b.x) * (c.y - b.y));
+ return area;
+ }
+
+ public int AreaSign(cPointi a, cPointi b, cPointi c) {
+ double area2;
+
+ area2 = (b.x - a.x) * (double) (c.y - a.y) - (c.x - a.x)
+ * (double) (b.y - a.y);
+
+ if (area2 > 0.5)
+ return 1;
+ else if (area2 < -0.5)
+ return -1;
+ else
+ return 0;
+ }
+
+ public boolean Left(cPointi a, cPointi b, cPointi c) {
+ return AreaSign(a, b, c) > 0;
+ }
+
+ public boolean LeftOn(cPointi a, cPointi b, cPointi c) {
+ return AreaSign(a, b, c) >= 0;
+ }
+
+ /*
+ * returns the distance of two points
+ */
+ public double Dist(cPointi p, cPointi p1) {
+ double l = Math.sqrt(Math.pow((p.x - p1.x), 2)
+ + Math.pow((p.y - p1.y), 2));
+ return l;
+ }
+
+ public boolean Collinear(cPointi a, cPointi b, cPointi c) {
+ return AreaSign(a, b, c) == 0;
+ }
+
+ public boolean Between(cPointi a, cPointi b, cPointi c) {
+ if (!Collinear(a, b, c))
+ return false;
+
+ if (a.x != b.x)
+ return ((a.x <= c.x) && (c.x <= b.x))
+ || ((a.x >= c.x) && (c.x >= b.x));
+ else
+ return ((a.y <= c.y) && (c.y <= b.y))
+ || ((a.y >= c.y) && (c.y >= b.y));
+ }
+
+ /*
+ * Returns the distance of the input point from its perp. proj. to the e1
+ * edge. Uses method detailed in comp.graphics.algorithms FAQ
+ */
+ double DistEdgePoint(cPointi a, cPointi b, cPointi c) {
+ double r, s;
+ double length;
+ double dproj = 0.0;
+ length = Math.sqrt(Math.pow((b.x - a.x), 2) + Math.pow((b.y - a.y), 2));
+
+ if (length == 0.0) {
+ System.out.println("DistEdgePoint: Length = 0");
+ }
+ r = (((a.y - c.y) * (a.y - b.y)) - ((a.x - c.x) * (b.x - a.x)))
+ / (length * length);
+ s = (((a.y - c.y) * (b.x - a.x)) - ((a.x - c.x) * (b.y - a.y)))
+ / (length * length);
+
+ dproj = Math.abs(s * length);
+
+ if ((s != 0.0) && ((0.0 <= r) && (r <= 1.0)))
+ return dproj;
+ if ((s == 0.0) && Between(a, b, c))
+ return 0.0;
+ else {
+ double ca = Dist(a, c);
+ double cb = Dist(b, c);
+ return Math.min(ca, cb);
+ }
+ }
+}
diff --git a/voronoi/cVertex.java b/voronoi/cVertex.java
new file mode 100644
index 0000000..1704141
--- /dev/null
+++ b/voronoi/cVertex.java
@@ -0,0 +1,51 @@
+package voronoi;
+class cVertex {
+
+ cVertex prev, next;
+ cPointi v;
+ boolean ear = false;
+ int vnum;
+ cEdge duplicate;
+ boolean onhull;
+ boolean mark;
+
+ cVertex() {
+ prev = next = null;
+ v = new cPointi();
+ vnum = 0;
+ duplicate = null;
+ onhull = false;
+ mark = false;
+ }
+
+ cVertex(int i, int j) {
+ v = new cPointi();
+ v.x = i;
+ v.y = j;
+ v.z = i * i + j* j;
+ prev = next = null;
+ }
+
+ cVertex(int x, int y, int z) {
+ v = new cPointi();
+ v.x = x;
+ v.y = y;
+ v.z = z;
+ prev = next = null;
+ }
+
+ public void ResetVertex3D()
+ {
+ v.z = v.x * v.x + v.y * v.y;
+ }
+
+}
+
+
+
+
+
+
+
+
+
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);
+ }
+ }
+
+}
diff --git a/voronoi/erstesVoronoi.png b/voronoi/erstesVoronoi.png
new file mode 100644
index 0000000..40e9745
--- /dev/null
+++ b/voronoi/erstesVoronoi.png
Binary files differ
diff --git a/voronoi/sweepLineVD.java b/voronoi/sweepLineVD.java
new file mode 100644
index 0000000..214b7c3
--- /dev/null
+++ b/voronoi/sweepLineVD.java
@@ -0,0 +1,73 @@
+package voronoi;
+
+import helper.ListBTS;
+
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.List;
+
+import DataStructure.GSMMap;
+import DataStructure.SingleBTS;
+
+public class sweepLineVD {
+ private GSMMap map;
+
+ // private ArrayList<point> pointmap = new ArrayList<point>();
+
+ /**
+ * @param args
+ */
+ public static void main(String[] args) {
+ // TODO Auto-generated method stub
+
+ }
+
+ public sweepLineVD(GSMMap map) {
+ this.map = map;
+ }
+
+ public void interpolate() {
+ SingleBTS[] btscontent = map.content();
+ for (SingleBTS extrapolateThis : btscontent) {
+ doVoronoi(extrapolateThis);
+ }
+ }
+
+ private void doVoronoi(SingleBTS extrapolateThis) {
+ // extract only x/y points out of gsmmap with this arfcn
+ List<Point2D> pointmap = getPointMap(extrapolateThis);
+ // start voronoi sweep now and build voronoi diagram
+ voronoisweep(pointmap);
+
+ }
+
+ @SuppressWarnings("unused")
+ private void voronoisweep(List<Point2D> pointmap) {
+ // sweepline from y=0 to max(y)
+ double sweepline = 0;
+
+ }
+
+ private List<Point2D> getPointMap(SingleBTS extrapolateThis) {
+ // have mappoint sorted for x-coordinates
+ ArrayList<Point2D> pointmap = new ArrayList<Point2D>();
+ for (int x = 0; x < map.Xcoords.length; x++) {
+ for (int y = 0; y < map.Ycoords.length; y++) {
+ if (ListBTS.contains(map.map[x][y], extrapolateThis)) {
+ pointmap.add(new Point2D.Double(x, y));
+ }
+ }
+
+ }
+ return pointmap;
+
+ }
+}
+
+/*
+ * class Point { public double x; public double y;
+ *
+ * public Point(double x, double y) { this.x = x; this.y = y; } } class Line {
+ *
+ * }
+ */ \ No newline at end of file
diff --git a/voronoi/voronoi.java b/voronoi/voronoi.java
new file mode 100644
index 0000000..f699e73
--- /dev/null
+++ b/voronoi/voronoi.java
@@ -0,0 +1,2228 @@
+package voronoi;
+
+//code kommt von http://shaneosullivan.wordpress.com/2007/04/05/fortunes-sweep-line-voronoi-algorithm-implemented-in-java/
+
+/*
+ * The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T
+ * Bell Laboratories.
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose without fee is hereby granted, provided that this entire notice
+ * is included in all copies of any software which is or includes a copy
+ * or modification of this software and in all copies of the supporting
+ * documentation for such software.
+ * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
+ * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
+ * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
+ */
+
+/*
+ * This code was originally written by Stephan Fortune in C code. I, Shane O'Sullivan,
+ * have since modified it, encapsulating it in a C++ class and, fixing memory leaks and
+ * adding accessors to the Voronoi Edges.
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose without fee is hereby granted, provided that this entire notice
+ * is included in all copies of any software which is or includes a copy
+ * or modification of this software and in all copies of the supporting
+ * documentation for such software.
+ * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
+ * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
+ * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
+ */
+
+/*
+ * Java Version by Zhenyu Pan
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose without fee is hereby granted, provided that this entire notice
+ * is included in all copies of any software which is or includes a copy
+ * or modification of this software and in all copies of the supporting
+ * documentation for such software.
+ * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
+ * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
+ * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
+ */
+
+import helper.ListBTS;
+
+import java.awt.Canvas;
+import java.awt.Color;
+import java.awt.Graphics;
+import java.awt.Graphics2D;
+import java.awt.geom.Line2D;
+import java.awt.geom.Path2D;
+import java.awt.geom.PathIterator;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import DataStructure.GSMMap;
+
+class Freenode {
+ Freenode nextfree;
+
+ Freenode getnext() {
+ return nextfree;
+ }
+
+ public void setnext(Freenode newf) {
+ nextfree = new Freenode();
+ nextfree = newf;
+ }
+}
+
+class Freelist {
+ public Freenode head;
+
+ Freelist() {
+ head = null;
+ }
+
+ public void free() {
+ while (head != null) {
+ head = head.nextfree;
+ }
+ }
+}
+
+/**
+ * Punkt im Raum (double)
+ *
+ *
+ */
+class Point {
+ double x, y;
+
+ public Point() {
+ }
+
+ public Point(int x, int y) {
+ this.x = x;
+ this.y = y;
+ }
+
+ public Point(double x, double y) {
+ this.x = x;
+ this.y = y;
+ }
+
+ public void setPoint(double x, double y) {
+ this.x = x;
+ this.y = y;
+ }
+}
+
+/**
+ * used both for sites and for vertices. its a point: Site.Point Vertices auf
+ * deutsch: Eckpunkt, Ecke, Knoten
+ *
+ *
+ */
+
+class Site {
+ Point coord;
+
+ int sitenumbr;
+
+ public Site() {
+ coord = new Point();
+ }
+
+ /**
+ * Richy. True if s matches current Site
+ *
+ * @param s
+ * @return
+ */
+ public boolean equals(Site s) {
+ return ((int) s.coord.x == (int) this.coord.x && (int) s.coord.y == (int) this.coord.y);
+ }
+}
+
+/**
+ * Stores 4 points in 2 arrays. EP: Endpoints: Lines reg: the two points this
+ * line bisects! The two points this line belongs to
+ *
+ */
+class Edge {
+ public double a = 0, b = 0, c = 0;
+
+ Site[] ep;
+
+ Site[] reg;
+
+ int edgenumbr;
+
+ Edge() {
+ ep = new Site[2];
+ reg = new Site[2];
+ }
+}
+
+/**
+ * Two points in 2d space make a line WATCHPOINT here!
+ */
+class GraphEdge {
+ public double x1, y1, x2, y2;
+ public Site correspondingPt;
+
+ GraphEdge next;
+}
+
+/**
+ * Speichert zu jeder HalfEdge weitere HalfEdges für Links und Rechts. Speichert
+ * zusätzlich eine Edge:ELedge Speichert auch ein vertex: vertex
+ *
+ * @author richy
+ *
+ */
+class Halfedge {
+ Halfedge ELleft, ELright;
+
+ Edge ELedge;
+
+ boolean deleted;
+
+ int ELpm;
+
+ Site vertex;
+
+ double ystar;
+
+ Halfedge PQnext;
+
+ Halfedge() {
+ PQnext = null;
+ }
+}
+
+class Hfreelist extends Freelist {
+ Halfedge hfl;
+
+ Hfreelist() {
+ hfl = new Halfedge();
+ }
+}
+
+class Sfreelist extends Freelist {
+ Site sfl;
+
+ Sfreelist() {
+ sfl = new Site();
+ }
+}
+
+class Efreelist extends Freelist {
+ Edge efl;
+
+ Efreelist() {
+ efl = new Edge();
+ }
+}
+
+public class voronoi {
+
+ double borderMinX, borderMaxX, borderMinY, borderMaxY;
+
+ int siteidx;
+ // ArrayList<PointAndLines> corresponding = new ArrayList<PointAndLines>();
+ // // richy
+ // ArrayList<PointAndVertices> polygon = new ArrayList<PointAndVertices>();
+ // // richy
+ ArrayList<Edge> edges = new ArrayList<Edge>(); // edges sortieren!!!
+
+ int zoomfactor; // richy
+
+ boolean isGenerated = false;
+
+ double xmin, xmax, ymin, ymax, deltax, deltay;
+
+ int nvertices;
+
+ int nedges;
+
+ int nsites;
+
+ Hfreelist hfl;
+
+ Efreelist efl;
+
+ Sfreelist sfl;
+
+ Site[] sites; // watchpoint here!
+
+ Site bottomsite;
+
+ int sqrt_nsites;
+
+ double minDistanceBetweenSites;
+
+ int PQcount;
+
+ int PQmin;
+
+ int PQhashsize;
+
+ Halfedge PQhash[];
+
+ public static int le = 0;
+
+ public static int re = 1;
+
+ int ELhashsize;
+
+ Halfedge ELhash[];
+
+ Halfedge ELleftend, ELrightend;
+
+ GraphEdge allEdges;
+
+ GraphEdge iteratorEdges;
+
+ Boolean VorSim;
+
+ Graphics g;
+
+ Canvas c;
+
+ int w;
+
+ int h;
+
+ double lasty;
+
+ public voronoi() {
+ siteidx = 0;
+ sites = null;
+
+ allEdges = null;
+ iteratorEdges = null;
+ minDistanceBetweenSites = 0;
+
+ VorSim = false;
+ g = null;
+ c = null;
+ w = h = 0;
+ lasty = 0;
+ }
+
+ public Point2D getNearestPoint(int x, int y) {
+ if (!isGenerated) {
+ generateVoronoi(0, 2000, 0, 2000);
+ }
+ double dist = Double.MAX_VALUE;
+ double temp_dist = Double.MAX_VALUE;
+ double distX = 0;
+ double distY = 0;
+ int index = 0;
+ for (int i = sites.length - 1; i >= 0; i--) {
+ distX = x - sites[i].coord.x;
+ distY = y - sites[i].coord.y;
+ temp_dist = Math.sqrt(Math.pow(distX, 2) + Math.pow(distY, 2));
+ if (temp_dist < dist) {
+ dist = temp_dist;
+ index = i;
+ }
+ }
+ Point2D result = new Point2D.Double();
+ result.setLocation(sites[index].coord.x, sites[index].coord.y);
+ return result;
+ }
+
+ /**
+ * Calculates the area of the given polygon
+ *
+ * @param poly
+ * @return area of poly
+ */
+ public double area(Path2D poly) {
+ try {
+ double area = 0;
+ ArrayList<Point> points = new ArrayList<Point>(20);
+ PathIterator itr = poly.getPathIterator(null);
+ // make list out of polygon. see
+ // http://anklick-bar.de/matheprojekt/kurbel-gauss.pdf
+ double[] itrresult = new double[6];
+ while (!itr.isDone()) {
+
+ itr.currentSegment(itrresult);
+ points.add(new Point(itrresult[0], itrresult[1]));
+ itr.next();
+ }
+ Point[] list = new Point[points.size() + 2];
+
+ for (int i = 0; i < points.size(); i++) {
+ list[i] = points.get(i);
+ }
+ list[points.size()] = points.get(0);
+ list[points.size() + 1] = points.get(1);
+ for (int i = 1; i <= points.size(); i++) {
+ // area of polygon is left to the line
+ // area = area + (list[i + 1].y - list[i - 1].y) * list[i].x;
+ area = area + (list[i + 1].x - list[i - 1].x) * list[i].y;
+ }
+
+ // testing: count number of pixel that are in the polygon
+ // boolean[][] containing = new boolean[poly.getBounds().width][poly
+ // .getBounds().height];
+ // int x = poly.getBounds().x;
+ // int y = poly.getBounds().y;
+ // int xlimit = poly.getBounds().width;
+ // int ylimit = poly.getBounds().height;
+ // int area2 = 0;
+ // for (int xi = 0; xi <= xlimit; xi++) {
+ // for (int yi = 0; yi <= ylimit; yi++) {
+ // if (poly.contains(xi + x, yi + y)) {
+ // area2++;
+ // }
+ // }
+ // }
+ // System.out.println("Fläche mit Pixeln: " + area2);
+ // System.out.flush();
+
+ return area / 2;
+ } catch (Exception e) {
+ return 0;
+ }
+
+ }
+
+ /*
+ * public Polygon crossSection(Polygon poly1, Polygon poly2) { // always
+ * check two points. if both are within the first polygon, take // them into
+ * the new polygon. If one is inside, the other is // outside,take inside
+ * point+intersection point.
+ *
+ * for (int i = 0; i < poly2.npoints - 1; i++) { Point pt1 = new
+ * Point(poly2.xpoints[i], poly2.ypoints[i]); Point pt2 = new
+ * Point(poly2.xpoints[i + 1], poly2.ypoints[i + 1]); ArrayList<Point>
+ * output = new ArrayList<Point>(); if (poly1.contains(pt1.x, pt1.y)) { if
+ * (poly1.contains(pt2.x, pt2.y)) { // both points in poly1:add
+ * output.add(pt1); output.add(pt2); } else { // pt1 is in polygon, pt2
+ * not.add pt1 and intersection with // poly1 // poly1. } } }
+ *
+ * // check points on poly2 that are within poly1 ArrayList<Point>
+ * containingPTs = new ArrayList<Point>(poly2.npoints); for (int i = 0; i <
+ * poly2.npoints; i++) { if (poly1.contains(poly2.xpoints[i],
+ * poly2.ypoints[i])) { containingPTs .add(new Point(poly2.xpoints[i],
+ * poly2.ypoints[i])); } } return null; }
+ */
+
+ public double intersectArea(Path2D poly1, Path2D poly2) {
+ // check the bounding box!
+ Rectangle2D box = getBox(poly1, poly2);
+ if (box.isEmpty())
+ return 0;
+ if (box.getWidth() < 0.00001 || box.getHeight() < 0.00001) {
+ return box.getHeight() * box.getWidth();
+ }
+ double area = 0;
+ // double maxX = box.getMaxX();
+ // double minX = box.getMinX();
+ // double maxY = box.getMaxY();
+ // double minY = box.getMinY();
+ double stepX = (box.getMaxX() - box.getMinX()) / 42; // accuracy
+ double stepY = (box.getMaxY() - box.getMinY()) / 42; // accuracy
+
+ for (double x = box.getMinX(); x <= box.getMaxX(); x += stepX) {
+ for (double y = box.getMinY(); y <= box.getMaxY(); y += stepY) {
+ if (poly1.contains(x, y) && poly2.contains(x, y)) {
+ area += stepX * stepY;
+ }
+ }
+ }
+ // for (int x = box.x; x <= box.width + box.x; x++) {
+ // for (int y = box.y; y <= box.height + box.y; y++) {
+ // if (poly1.contains(x, y) && poly2.contains(x, y))
+ // area++;
+ // hier darf doch kein int drüberlaufen.klar, dass die fläche
+ // dann nicht gemessen werden kann!
+ // System.
+ // }
+ // }
+ return area;
+ }
+
+ public double drawIntersectArea(Path2D poly1, Path2D poly2, Graphics2D g) {
+ // check the bounding box!
+ Rectangle2D box = getBox(poly1, poly2);
+ if (box.isEmpty())
+ return 0;
+ if (box.getWidth() < 0.00001 || box.getHeight() < 0.00001) {
+ return box.getHeight() * box.getWidth();
+ }
+ double area = 0;
+ // double maxX = box.getMaxX();
+ // double minX = box.getMinX();
+ // double maxY = box.getMaxY();
+ // double minY = box.getMinY();
+ double stepX = (box.getMaxX() - box.getMinX()) / 50;
+ double stepY = (box.getMaxY() - box.getMinY()) / 50;
+ stepX = 1;
+ stepY = 1;
+ Random r = new Random();
+ g.setColor(new Color(r.nextInt(255), r.nextInt(255), r.nextInt(255)));
+ for (double x = box.getMinX(); x <= box.getMaxX(); x += stepX) {
+ for (double y = box.getMinY(); y <= box.getMaxY(); y += stepY) {
+ if (poly1.contains(x, y) && poly2.contains(x, y)) {
+ area += stepX * stepY;
+ g.fillRect((int) x, (int) y, 1, 1);
+ }
+ }
+ }
+ // for (int x = box.x; x <= box.width + box.x; x++) {
+ // for (int y = box.y; y <= box.height + box.y; y++) {
+ // if (poly1.contains(x, y) && poly2.contains(x, y))
+ // area++;
+ // hier darf doch kein int drüberlaufen.klar, dass die fläche
+ // dann nicht gemessen werden kann!
+ // System.
+ // }
+ // }
+ return area;
+ }
+
+ private Rectangle2D getBox(Path2D poly1, Path2D poly2) {
+
+ // TODO Auto-generated method stub
+ Rectangle2D rect1 = poly1.getBounds2D();
+ Rectangle2D rect2 = poly2.getBounds2D();
+ Rectangle2D box = new Rectangle2D.Double();
+ Rectangle2D.intersect(rect1, rect2, box);
+ // maximum x
+ // int x = Math.max(rect1.x, rect2.x);
+ // int y = Math.max(rect1.y, rect2.y);
+ // int width = Math.min(rect1.width, rect2.width);
+ // int height = Math.min(rect1.height, rect2.height);
+ // Rectangle result = new Rectangle(x, y, width, height);
+ // return result;
+ return box;
+
+ }
+
+ /**
+ * Gets a list of lines. Sorts the lines so that a polygon can be formed out
+ * of it! list gets cleared during this process!!!
+ *
+ * @param list
+ * @return
+ */
+ private Path2D sortLineList(List<Line2D> list) {
+ if (list.isEmpty()) {
+ return null;
+ }
+
+ // during the voronoi process, lines may be created where start and
+ // endpoint are the same. remove them! Careful, rounding errors appear!
+ for (int i = 0; i < list.size(); i++) {
+ Line2D check = list.get(i);
+ if (Math.abs(check.getP1().getX() - check.getP2().getX()) < 0.0001d
+ && Math.abs(check.getP1().getY() - check.getP2().getY()) < 0.0001d) {
+ list.remove(i);
+ i--;
+ }
+ }
+
+ // now, we traverse the list and sesarch the points
+ // Polygon result = new Polygon();
+ Path2D path = new Path2D.Double();
+ /*
+ * Line2D current = list.remove(0); result.addPoint((int)
+ * current.getX1(), (int) current.getY1()); result.addPoint((int)
+ * current.getX2(), (int) current.getY2()); current.setLine(0, 0,
+ * current.getX2(), current.getY2());
+ *
+ *
+ * while (!list.isEmpty()) { // formerly: !list.isEmpty() for (int i =
+ * 0; i < list.size(); i++) { if (commonConnectionPT(current,
+ * list.get(i))) { Point now = getCommonPT(current, list.get(i));
+ * result.addPoint((int) now.x, (int) now.y); current = list.remove(i);
+ * break; } } }
+ */
+ try {
+ // initialize. Take first point
+ Point currPT = new Point();
+ currPT.x = list.get(0).getX1();
+ currPT.y = list.get(0).getY1();
+ // path.moveTo(currPT.x, currPT.y);
+ boolean firstloop = true;
+ while (!list.isEmpty()) {
+
+ // traverse all points, look for a match
+ for (int i = list.size() - 1; i >= 0; i--) {
+ if (LineContainsPT(currPT, list.get(i))) {
+ // a line containing the current point is found. Add
+ // this
+ // point to the polygon.
+ // result.addPoint((int) currPT.x, (int) currPT.y);
+ if (firstloop) {
+ // cannot do this otherwise: Taking the first
+ // element from list would result in wrong Paths,
+ // because then also the next endpoint would be gone
+ // away
+ firstloop = false;
+ path.moveTo(currPT.x, currPT.y);
+ } else {
+ path.lineTo(currPT.x, currPT.y);
+ }
+ // path.moveTo(currPT.x, currPT.y);
+ // get the neighbor point of the current line
+ // in next iteration, search a line that contains the
+ // new point
+ currPT = theOtherPoint(currPT, list.get(i));
+ // remove the line that contained the point
+ list.remove(i);
+ break;
+ // TODO: if list contains a line with negativ x or y
+ // value, change it to zero maybe?
+ }
+ // HACK:if only one line is left, add the points
+ // this part is only reached if all lines were traversed but
+ // nothing was found!
+ if (list.size() == 1) {
+ // result.addPoint((int) list.get(0).getX1(), (int) list
+ // .get(0).getY1());
+ // result.addPoint((int) list.get(0).getX2(), (int) list
+ // .get(0).getY2());
+ list.remove(0);
+ }
+ }
+ }
+ // result.npoints = list.size();
+ path.closePath();
+ return path;
+ } catch (Exception e) {
+ // System.out.println("kann polygon nicht bauen");
+ return null;
+ }
+ }
+
+ private Point theOtherPoint(Point currPT, Line2D line2d) {
+ Point result = new Point();
+ // take in count rounding errors by doubles! Do Math.abs(x1-x2)<0.001
+ if (Math.abs(currPT.x - line2d.getX1()) < 0.0001
+ && Math.abs(currPT.y - line2d.getY1()) < 0.0001) {
+ result.x = line2d.getX2();
+ result.y = line2d.getY2();
+ return result;
+ } else if (Math.abs(currPT.x - line2d.getX2()) < 0.0001
+ && Math.abs(currPT.y - line2d.getY2()) < 0.0001) {
+ result.x = line2d.getX1();
+ result.y = line2d.getY1();
+ return result;
+ }
+ return null;
+ }
+
+ private boolean LineContainsPT(Point currPT, Line2D line2d) {
+ // tolerance of 0.001
+ if (Math.abs(currPT.x - line2d.getX1()) < 0.001
+ && Math.abs(currPT.y - line2d.getY1()) < 0.001) {
+ return true;
+ }
+ if (Math.abs(currPT.x - line2d.getX2()) < 0.001
+ && Math.abs(currPT.y - line2d.getY2()) < 0.001) {
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Gets the point where both lines are connected to each other!
+ *
+ * @param current
+ * @param line2d
+ * @return
+ */
+ @SuppressWarnings("unused")
+ private Point getCommonPT(Line2D line1, Line2D line2) {
+ // TODO Auto-generated method stub
+ Point point = new Point();
+ if (line1.getX1() == line2.getX1() && line1.getY1() == line2.getY1()) {
+ point.x = line1.getX1();
+ point.y = line1.getY1();
+ } else if (line1.getX2() == line2.getX2()
+ && line1.getY2() == line2.getY2()) {
+ point.x = line1.getX1();
+ point.y = line1.getY1();
+ } else if (line1.getX2() == line2.getX1()
+ && line1.getY2() == line2.getY1()) {
+ point.x = line1.getX1();
+ point.y = line1.getY1();
+ } else if (line1.getX1() == line2.getX2()
+ && line1.getY1() == line2.getY2()) {
+ point.x = line1.getX1();
+ point.y = line1.getY1();
+ } else {
+ return null;
+ }
+ return point;
+ }
+
+ /**
+ * Checks if the two lines have a common starting point! (Only check left
+ * part?!)
+ *
+ * @param line1
+ * @param line2
+ * @return
+ */
+ @SuppressWarnings("unused")
+ private boolean commonConnectionPT(Line2D line1, Line2D line2) {
+ if (line1.getX1() == line2.getX1() && line1.getY1() == line2.getY1()) {
+ return true;
+ }
+ if (line1.getX2() == line2.getX2() && line1.getY2() == line2.getY2()) {
+ return true;
+ }
+ if (line1.getX2() == line2.getX1() && line1.getY2() == line2.getY1()) {
+ return true;
+ }
+ if (line1.getX1() == line2.getX2() && line1.getY1() == line2.getY2()) {
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Returns the polygon for the point in x,y. Point x,y must be a
+ * Measurement. The Point must exist.
+ *
+ * @param x
+ * @param y
+ * @return
+ */
+ public Path2D getPoly(int x, int y) {
+ if (!isGenerated) {
+ // todo:change the parameters according to GSMmap-size!
+ // Edge.reg[] gibt an, zu welchen Punkten die Linie gehört!
+ generateVoronoi(0, 2000, 0, 2000);
+ }
+ Edge currEdge;
+ Site s = new Site();
+ ArrayList<Line2D> lines = new ArrayList<Line2D>();
+ s.coord = new Point(x, y);
+
+ // TODO: check lines for null-values. if so, clip it to the max value of
+ // the voronoi
+
+ for (int i = 0; i < edges.size(); i++) {
+ try {
+ currEdge = edges.get(i);
+ // see if x/y matches the lines in edges
+ if (s.equals(currEdge.reg[0])) {
+
+ double x1 = currEdge.ep[0].coord.x;
+ double y1 = currEdge.ep[0].coord.y;
+ double x2 = currEdge.ep[1].coord.x;
+ double y2 = currEdge.ep[1].coord.y;
+ lines.add(new Line2D.Double(x1, y1, x2, y2));
+
+ // lines.add(makeToLine(currEdge));
+ }
+ // lines.add(new Line2D.Double(x1,y1,);
+ // vielleicht gut, wenn man prüft, ob currEdge[0]oder[1] die
+ // Kante
+ // beinhaltet... eigentlich unnötig. kann in ein test eingebaut
+ // werden
+ else if (s.equals(currEdge.reg[1])) {
+
+ double x1 = currEdge.ep[0].coord.x;
+ double y1 = currEdge.ep[0].coord.y;
+ double x2 = currEdge.ep[1].coord.x;
+ double y2 = currEdge.ep[1].coord.y;
+ lines.add(new Line2D.Double(x1, y1, x2, y2));
+
+ // lines.add(makeToLine(currEdge));
+ }
+
+ // linien zu polygon verschmelzen
+ } catch (Exception e) {
+ // System.out.println("Mindetens eine Linie ist null");
+ return null;
+ }
+ }
+ // System.out.println("anzahl der Linien: " + lines.size());
+
+ // Polygon result = new Polygon();
+ Path2D result = sortLineList(lines);
+
+ return result;
+ }
+
+ @SuppressWarnings("unused")
+ private Line2D makeToLine(Edge currEdge) {
+ // TODO Auto-generated method stub
+ // check for null references. if so, set it to a max value;
+ /*
+ * double middle_of_x = (xmax - xmin) / 2; double middle_of_y = (ymax -
+ * ymin) / 2; if (currEdge.ep[0] == null) { // first endpoint is null.
+ * Check where the other endpoint is[1]. // clip // accordingly
+ * currEdge.ep[0] = new Site(); currEdge.ep[0].coord = new Point(); //
+ * check for x if (currEdge.ep[1].coord.x < middle_of_x) {
+ * currEdge.ep[0].coord.x = 0; } else { currEdge.ep[0].coord.x = xmax; }
+ * // check for y if (currEdge.ep[1].coord.y < middle_of_y) {
+ * currEdge.ep[0].coord.y = 0; } else { currEdge.ep[0].coord.y = ymax; }
+ *
+ * } else if (currEdge.ep[1] == null) { currEdge.ep[1] = new Site();
+ * currEdge.ep[1].coord = new Point(); if (currEdge.ep[0].coord.x <
+ * middle_of_x) { currEdge.ep[1].coord.x = 0; } else {
+ * currEdge.ep[1].coord.x = xmax; } // check for y if
+ * (currEdge.ep[0].coord.y < middle_of_y) { currEdge.ep[1].coord.y = 0;
+ * } else { currEdge.ep[1].coord.y = ymax; } }
+ */
+ // now, build line
+ double x1 = currEdge.ep[0].coord.x;
+ double x2 = currEdge.ep[1].coord.x;
+ double y1 = currEdge.ep[0].coord.y;
+ double y2 = currEdge.ep[1].coord.y;
+ Line2D result = new Line2D.Double();
+ result.setLine(x1, y1, x2, y2);
+ return result;
+
+ }
+
+ /**
+ * Get the neighbors of a point. Only these neighbors are in relationship
+ * with the given point. Lets say you insert a point for interpolation, than
+ * you would check for his neihgbors in order to see which polygons you need
+ * for calculation
+ *
+ * @param x
+ * @param y
+ * @return
+ */
+ public ArrayList<Point2D> getDirectNeighbors(double x, double y) {
+ Site s = new Site();
+ s.coord.x = x;
+ s.coord.y = y;
+ Edge currEdge;
+ ArrayList<Point2D> result = new ArrayList<Point2D>();
+
+ for (int i = edges.size() - 1; i >= 0; i--) {
+ Point2D currPT = new Point2D.Double();
+ currEdge = edges.get(i);
+ // check if this edge has something to do with the coordinate x,y
+ if (s.equals(currEdge.reg[0])) {
+ currPT.setLocation(currEdge.reg[1].coord.x,
+ currEdge.reg[1].coord.y);
+ result.add(currPT);
+ } else if (s.equals(currEdge.reg[1])) {
+ currPT.setLocation(currEdge.reg[0].coord.x,
+ currEdge.reg[0].coord.y);
+ result.add(currPT);
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Returns the size of the area of the voronoi region at x,y
+ *
+ * @param x
+ * @param y
+ * @return
+ */
+ public double areaOf(int x, int y) {
+ return area(getPoly(x, y));
+ }
+
+ public void VorSim(boolean vorsim, Graphics vorg, int vorw, int vorh,
+ Canvas Can) {
+ VorSim = vorsim;
+ c = Can;
+ g = vorg;
+ w = vorw;
+ h = vorh;
+ }
+
+ void cleanupSites() {
+ if (sites != null)
+ for (int i = 0; i < sites.length; i++)
+ sites[i] = null;
+ sites = null;
+ }
+
+ void cleanupEdges() {
+ GraphEdge geCurrent = allEdges;
+
+ while (geCurrent != null && geCurrent.next != null) {
+ @SuppressWarnings("unused")
+ GraphEdge freeCurrent = geCurrent;
+ geCurrent = geCurrent.next;
+ freeCurrent = null;
+ }
+ allEdges = null;
+ }
+
+ /**
+ * löscht wohl das diagram
+ */
+ void dVoronoiDiagramGenerator() {
+ cleanupSites();
+ cleanupEdges();
+ sfl = null;
+ efl = null;
+ }
+
+ /**
+ * Site compare. Liefert -1,1 zurück, je nachdem welcher x oder y Wert
+ * größer ist
+ *
+ * @param p1
+ * @param p2
+ * @return
+ */
+ int scomp(Site p1, Site p2) {
+ Point s1 = p1.coord, s2 = p2.coord;
+ if (s1.y < s2.y)
+ return (-1);
+ if (s1.y > s2.y)
+ return (1);
+ if (s1.x < s2.x)
+ return (-1);
+ if (s1.x > s2.x)
+ return (1);
+ return (0);
+ }
+
+ /**
+ * sortiert von sites die ersten n einträge
+ *
+ * @param sites
+ * @param n
+ */
+ void qsort(Site[] sites, int n) {
+ Site tmp;
+ if (n == 1)
+ return;
+ for (int i = 0; i < n; i++) {
+ for (int j = i + 1; j < n; j++) {
+ if (scomp(sites[i], sites[j]) > 0) {
+ tmp = sites[i];
+ sites[i] = sites[j];
+ sites[j] = tmp;
+ }
+ }
+ }
+ }
+
+ /**
+ * fügt Punkte hinzu? Sortiert automatisch
+ *
+ * @param xValues
+ * @param yValues
+ * @param numPoints
+ */
+ public void sortNode(double xValues[], double yValues[], int numPoints) {
+ // richy start
+ dVoronoiDiagramGenerator();
+ // richy end
+ int i;
+ nsites = numPoints;
+ sites = new Site[nsites];
+ // richy start
+ double sn = (double) nsites + 4;
+ sqrt_nsites = (int) Math.sqrt(sn);
+ minDistanceBetweenSites = 3;
+ nvertices = 0;
+ sfl = new Sfreelist();
+ nedges = 0;
+ efl = new Efreelist();
+ // richy end
+ xmin = xValues[0];
+ ymin = yValues[0];
+ xmax = xValues[0];
+ ymax = yValues[0];
+ // for all x and y values given
+ for (i = 0; i < nsites; i++) {
+ // generate new site with x,y values
+ sites[i] = new Site();
+ sites[i].coord.setPoint(xValues[i], yValues[i]);
+ sites[i].sitenumbr = i;
+
+ // update min and max
+ if (xValues[i] < xmin)
+ xmin = xValues[i];
+ else if (xValues[i] > xmax)
+ xmax = xValues[i];
+
+ if (yValues[i] < ymin)
+ ymin = yValues[i];
+ else if (yValues[i] > ymax)
+ ymax = yValues[i];
+ }
+ // sort the recently added sites
+ qsort(sites, nsites);
+ deltay = ymax - ymin;
+ deltax = xmax - xmin;
+ }
+
+ /**
+ * Inserts point into Voronoi. Uses a gsmmap and a ARFCN.
+ *
+ * @param map
+ * @param resize
+ * multiplied to each coordinate to have a larger distance
+ * between points. 1 if not wanted!
+ */
+ public void sortNode(GSMMap map, int arfcn, int resize) {
+ double x = Double.NaN;
+ double y = Double.NaN;
+ sortNode(map, arfcn, resize, x, y);
+ }
+
+ /**
+ * Inserts point into Voronoi. Uses a gsmmap and a ARFCN. Adds one
+ * additional point: x,y
+ *
+ * @param map
+ * @param resize
+ * multiplied to each coordinate to have a larger distance
+ * between points. 1 if not wanted!
+ */
+ public void sortNode(GSMMap map, int arfcn, int resize, double xcoord,
+ double ycoord) {
+ ArrayList<Double> xVal = new ArrayList<Double>();
+ ArrayList<Double> yVal = new ArrayList<Double>();
+ if (!Double.isNaN(xcoord) && !Double.isNaN(ycoord)) {
+ xVal.add(xcoord);
+ yVal.add(ycoord);
+ }
+ edges = new ArrayList<Edge>(map.numberOfCoordinates);
+ zoomfactor = resize;
+ // get xValues
+ for (int x = 0; x < map.Xcoords.length; x++) {
+ for (int y = 0; y < map.Ycoords.length; y++) {
+ if (ListBTS.contains(map.map[x][y], arfcn)) {
+ xVal.add((double) x);
+ yVal.add((double) y);
+ }
+ }
+ }
+ double xArray[] = new double[xVal.size()];
+ for (int x = 0; x < xArray.length; x++) {
+ xArray[x] = xVal.get(x) * resize;
+ }
+
+ double yArray[] = new double[yVal.size()];
+ for (int y = 0; y < yArray.length; y++) {
+ yArray[y] = yVal.get(y) * resize;
+ }
+
+ sortNode(xArray, yArray, xVal.size());
+ }
+
+ /**
+ * return a single in-storage site from array sites. A site is a point
+ *
+ * @return the next site in the storage
+ */
+ Site nextone() {
+ Site s;
+ if (siteidx < nsites) {
+ s = sites[siteidx];
+ siteidx += 1;
+ return (s);
+ } else
+ return (null);
+ }
+
+ /**
+ * to bisect: halbieren.
+ *
+ * @param s1
+ * @param s2
+ * @return
+ */
+ Edge bisect(Site s1, Site s2) {
+ double dx, dy, adx, ady;
+ Edge newedge;
+
+ newedge = new Edge();
+ // RICHY: hier ist der ganze geile scheiß, den ich suche!!!!!!!!!!
+
+ // store the sites that this edge is bisecting: reg
+ // Jede edge speichern und dann anzeigen!
+ newedge.reg[0] = s1;
+ newedge.reg[1] = s2;
+
+ // to begin with, there are no endpoints on the bisector - it goes to
+ // infinity: ep: Endpoints of Line
+ newedge.ep[0] = null;
+ newedge.ep[1] = null;
+
+ // get the difference in x dist between the sites
+ dx = s2.coord.x - s1.coord.x;
+ dy = s2.coord.y - s1.coord.y;
+ // make sure that the difference in positive. Ternary operator
+ adx = dx > 0 ? dx : -dx;
+ ady = dy > 0 ? dy : -dy;
+ newedge.c = (double) (s1.coord.x * dx + s1.coord.y * dy + (dx * dx + dy
+ * dy) * 0.5);// get the slope of the line
+
+ if (adx > ady) {
+ newedge.a = 1.0f;
+ newedge.b = dy / dx;
+ newedge.c /= dx;// set formula of line, with x fixed to 1
+ } else {
+ newedge.b = 1.0f;
+ newedge.a = dx / dy;
+ newedge.c /= dy;// set formula of line, with y fixed to 1
+ }
+
+ // sets a number to that edge
+ newedge.edgenumbr = nedges;
+
+ // increses the edge counter for the next call
+ nedges += 1;
+ // RICHY: diese Änderung wars. Beim einfügen ist newedge noch quasi
+ // leer, aber das ändert sich während voronoi_bd() läuft, weil ja nur
+ // die Referenz in der ArrayList steht und nicht eine Kopie des Objektes
+ // prüfe, ob newedge nicht schon drin ist!
+ edges.add(newedge); // TODO: das wieder einkommentieren zur not
+ return (newedge);
+ }
+
+ void resetIterator() {
+ iteratorEdges = allEdges;
+ }
+
+ /**
+ *
+ * @return
+ */
+ GraphEdge getNext() {
+ if (iteratorEdges != null) {
+ GraphEdge temp = iteratorEdges;
+ iteratorEdges = iteratorEdges.next;
+ return temp;
+ }
+ return null;
+ }
+
+ /**
+ * Fügt Punkte zum Voronoi Diagram hinzu? Vertex: Knoten, Eckpunkt
+ *
+ * @param list
+ */
+ void Sort(cVertexList list) {
+ double xValues[];
+ double yValues[];
+ int count;
+
+ dVoronoiDiagramGenerator();
+
+ nsites = list.n;
+ minDistanceBetweenSites = 3;
+
+ nvertices = 0;
+ sfl = new Sfreelist();
+
+ nedges = 0;
+ efl = new Efreelist();
+
+ double sn = (double) nsites + 4;
+ sqrt_nsites = (int) Math.sqrt(sn);
+
+ count = list.n;
+ xValues = new double[count];
+ yValues = new double[count];
+ for (int i = 0; i < count; i++) {
+ xValues[i] = list.GetElement(i).v.x;
+ yValues[i] = list.GetElement(i).v.y;
+ }
+ sortNode(xValues, yValues, count);
+ }
+
+ /**
+ * gives the Site v a vertice number. Increses the number then for the next
+ * call
+ *
+ * @param v
+ */
+ void makevertex(Site v) {
+ v.sitenumbr = nvertices;
+ nvertices += 1;
+ }
+
+ boolean PQinitialize() {
+ PQcount = 0;
+ PQmin = 0;
+ PQhashsize = 4 * sqrt_nsites;
+ PQhash = new Halfedge[PQhashsize];
+
+ for (int i = 0; i < PQhashsize; i += 1)
+ PQhash[i] = new Halfedge();
+ return true;
+ }
+
+ int PQbucket(Halfedge he) {
+ int bucket;
+
+ bucket = (int) ((he.ystar - ymin) / deltay * PQhashsize);
+ if (bucket < 0)
+ bucket = 0;
+ if (bucket >= PQhashsize)
+ bucket = PQhashsize - 1;
+ if (bucket < PQmin)
+ PQmin = bucket;
+ return (bucket);
+ }
+
+ /**
+ * push the HalfEdge into the ordered linked list of vertices. vertices:
+ * Ecke
+ *
+ * @param he
+ * @param v
+ * @param offset
+ */
+ void PQinsert(Halfedge he, Site v, double offset, Site s) {
+ // Site s hab ich eingefügt
+ Halfedge last, next;
+
+ he.vertex = v;
+ he.ystar = (double) (v.coord.y + offset);
+ last = PQhash[PQbucket(he)];
+ while ((next = last.PQnext) != null
+ && (he.ystar > next.ystar || (he.ystar == next.ystar && v.coord.x > next.vertex.coord.x))) {
+ last = next;
+ }
+ he.PQnext = last.PQnext;
+ last.PQnext = he;
+ PQcount += 1;
+ }
+
+ // remove the HalfEdge from the list of vertices
+ void PQdelete(Halfedge he) {
+ Halfedge last;
+
+ if (he.vertex != null) {
+ last = PQhash[PQbucket(he)];
+ while (last.PQnext != he)
+ last = last.PQnext;
+
+ last.PQnext = he.PQnext;
+ PQcount -= 1;
+ he.vertex = null;
+ }
+ }
+
+ boolean PQempty() {
+ return (PQcount == 0);
+ }
+
+ Point PQ_min() {
+ Point answer = new Point();
+
+ while (PQhash[PQmin].PQnext == null) {
+ PQmin += 1;
+ }
+ answer.x = PQhash[PQmin].PQnext.vertex.coord.x;
+ answer.y = PQhash[PQmin].PQnext.ystar;
+ return (answer);
+ }
+
+ Halfedge PQextractmin() {
+ Halfedge curr;
+
+ curr = PQhash[PQmin].PQnext;
+ PQhash[PQmin].PQnext = curr.PQnext;
+ PQcount -= 1;
+ return (curr);
+ }
+
+ Halfedge HEcreate(Edge e, int pm) {
+ Halfedge answer;
+ answer = new Halfedge();
+ answer.ELedge = e;
+ answer.ELpm = pm;
+ answer.PQnext = null;
+ answer.vertex = null;
+ return (answer);
+ }
+
+ boolean ELinitialize() {
+ int i;
+ ELhashsize = 2 * sqrt_nsites;
+ ELhash = new Halfedge[ELhashsize];
+
+ for (i = 0; i < ELhashsize; i += 1)
+ ELhash[i] = null;
+ ELleftend = HEcreate(null, 0);
+ ELrightend = HEcreate(null, 0);
+ ELleftend.ELleft = null;
+ ELleftend.ELright = ELrightend;
+ ELrightend.ELleft = ELleftend;
+ ELrightend.ELright = null;
+ ELhash[0] = ELleftend;
+ ELhash[ELhashsize - 1] = ELrightend;
+
+ return true;
+ }
+
+ /**
+ * returns right edge of halfedge???
+ *
+ * @param he
+ * @return
+ */
+ Halfedge ELright(Halfedge he) {
+ return (he.ELright);
+ }
+
+ Halfedge ELleft(Halfedge he) {
+ return (he.ELleft);
+ }
+
+ Site leftreg(Halfedge he) {
+ if (he.ELedge == null)
+ return (bottomsite);
+ return (he.ELpm == le ? he.ELedge.reg[le] : he.ELedge.reg[re]);
+ }
+
+ /**
+ * makes both Halfedges to neighbors
+ *
+ * @param lb
+ * @param newHe
+ */
+ void ELinsert(Halfedge lb, Halfedge newHe) {
+ newHe.ELleft = lb;
+ newHe.ELright = lb.ELright;
+ (lb.ELright).ELleft = newHe;
+ lb.ELright = newHe;
+ }
+
+ /*
+ * This delete routine can't reclaim node, since pointers from hash table
+ * may be present.
+ */
+ void ELdelete(Halfedge he) {
+ (he.ELleft).ELright = he.ELright;
+ (he.ELright).ELleft = he.ELleft;
+ he.deleted = true;
+ }
+
+ /* Get entry from hash table, pruning any deleted nodes */
+ Halfedge ELgethash(int b) {
+ Halfedge he;
+
+ if (b < 0 || b >= ELhashsize)
+ return (null);
+ he = ELhash[b];
+ if (he == null || !he.deleted)
+ return (he);
+
+ /* Hash table points to deleted half edge. Patch as necessary. */
+ ELhash[b] = null;
+ return (null);
+ }
+
+ /**
+ * gets left Edge of Point p
+ *
+ * @param p
+ * @return
+ */
+ Halfedge ELleftbnd(Point p) {
+ int i, bucket;
+ Halfedge he;
+
+ /* Use hash table to get close to desired halfedge */
+ // use the hash function to find the place in the hash map that this
+ // HalfEdge should be
+ bucket = (int) ((p.x - xmin) / deltax * ELhashsize);
+
+ // make sure that the bucket position in within the range of the hash
+ // array
+ if (bucket < 0)
+ bucket = 0;
+ if (bucket >= ELhashsize)
+ bucket = ELhashsize - 1;
+
+ he = ELgethash(bucket);
+ if (he == null)
+ // if the HE isn't found, search backwards and forwards in the hash map
+ // for the first non-null entry
+ {
+ for (i = 1; i < ELhashsize; i += 1) {
+ if ((he = ELgethash(bucket - i)) != null)
+ break;
+ if ((he = ELgethash(bucket + i)) != null)
+ break;
+ }
+ }
+ /* Now search linear list of halfedges for the correct one */
+ if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
+ // keep going right on the list until either the end is reached, or
+ // you find the 1st edge which the point isn't to the right of
+ do {
+ he = he.ELright;
+ } while (he != ELrightend && right_of(he, p));
+ he = he.ELleft;
+ } else
+ // if the point is to the left of the HalfEdge, then search left for
+ // the HE just to the left of the point
+ do {
+ he = he.ELleft;
+ } while (he != ELleftend && !right_of(he, p));
+
+ /* Update hash table and reference counts */
+ if (bucket > 0 && bucket < ELhashsize - 1) {
+ ELhash[bucket] = he;
+ }
+ return (he);
+ }
+
+ GraphEdge pushGraphEdge(double x1, double y1, double x2, double y2, Site v) {
+ GraphEdge newEdge = new GraphEdge();
+ newEdge.next = allEdges;
+ allEdges = newEdge;
+ newEdge.x1 = x1;
+ newEdge.y1 = y1;
+ newEdge.x2 = x2;
+ newEdge.y2 = y2;
+ newEdge.correspondingPt = v;
+ return newEdge;
+ }
+
+ GraphEdge line(double x1, double y1, double x2, double y2, Site v) {
+ GraphEdge result = pushGraphEdge(x1, y1, x2, y2, v);
+ if (VorSim) {
+ g.setColor(Color.red);
+ g.drawLine((int) x1, (int) y1, (int) x2, (int) y2);
+ c.repaint();
+ try {
+ Thread.sleep(500);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ }
+ return result;
+ }
+
+ GraphEdge clip_line(Edge e, Site v) {
+ double pxmin, pxmax, pymin, pymax;
+ Site s1, s2;
+ double x1 = 0, x2 = 0, y1 = 0, y2 = 0;
+
+ x1 = e.reg[0].coord.x;
+ x2 = e.reg[1].coord.x;
+ y1 = e.reg[0].coord.y;
+ y2 = e.reg[1].coord.y;
+
+ // if the distance between the two points this line was created from is
+ // less than the square root of 2, then ignore it
+ if (Math.sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1))) < minDistanceBetweenSites) {
+ return null;
+ }
+ pxmin = borderMinX;
+ pxmax = borderMaxX;
+ pymin = borderMinY;
+ pymax = borderMaxY;
+
+ if (e.a == 1.0 && e.b >= 0.0) {
+ s1 = e.ep[1];
+ s2 = e.ep[0];
+ } else {
+ s1 = e.ep[0];
+ s2 = e.ep[1];
+ }
+
+ if (e.a == 1.0) {
+ y1 = pymin;
+ if (s1 != null && s1.coord.y > pymin) {
+ y1 = s1.coord.y;
+ }
+ if (y1 > pymax) {
+ y1 = pymax;
+ }
+ x1 = e.c - e.b * y1;
+ y2 = pymax;
+ if (s2 != null && s2.coord.y < pymax)
+ y2 = s2.coord.y;
+
+ if (y2 < pymin) {
+ y2 = pymin;
+ }
+ x2 = (e.c) - (e.b) * y2;
+ if (((x1 > pxmax) & (x2 > pxmax)) | ((x1 < pxmin) & (x2 < pxmin))) {
+ return null;
+ }
+ if (x1 > pxmax) {
+ x1 = pxmax;
+ y1 = (e.c - x1) / e.b;
+ }
+ if (x1 < pxmin) {
+ x1 = pxmin;
+ y1 = (e.c - x1) / e.b;
+ }
+ if (x2 > pxmax) {
+ x2 = pxmax;
+ y2 = (e.c - x2) / e.b;
+ }
+ if (x2 < pxmin) {
+ x2 = pxmin;
+ y2 = (e.c - x2) / e.b;
+ }
+ } else {
+ x1 = pxmin;
+ if (s1 != null && s1.coord.x > pxmin)
+ x1 = s1.coord.x;
+ if (x1 > pxmax) {
+ x1 = pxmax;
+ }
+ y1 = e.c - e.a * x1;
+ x2 = pxmax;
+ if (s2 != null && s2.coord.x < pxmax)
+ x2 = s2.coord.x;
+ if (x2 < pxmin) {
+ x2 = pxmin;
+ }
+ y2 = e.c - e.a * x2;
+ if (((y1 > pymax) & (y2 > pymax)) | ((y1 < pymin) & (y2 < pymin))) {
+ return null;
+ }
+ if (y1 > pymax) {
+ y1 = pymax;
+ x1 = (e.c - y1) / e.a;
+ }
+ if (y1 < pymin) {
+ y1 = pymin;
+ x1 = (e.c - y1) / e.a;
+ }
+ if (y2 > pymax) {
+ y2 = pymax;
+ x2 = (e.c - y2) / e.a;
+ }
+ if (y2 < pymin) {
+ y2 = pymin;
+ x2 = (e.c - y2) / e.a;
+ }
+ }
+
+ return line(x1, y1, x2, y2, v);
+ }
+
+ GraphEdge endpoint(Edge e, int lr, Site s) {
+ e.ep[lr] = s;
+ if (e.ep[re - lr] == null)
+ return null;
+ return clip_line(e, s);
+ }
+
+ /* returns 1 if p is to right of halfedge e */
+ boolean right_of(Halfedge el, Point p) {
+ Edge e;
+ Site topsite;
+ boolean right_of_site;
+ boolean above, fast;
+ double dxp, dyp, dxs, t1, t2, t3, yl;
+
+ e = el.ELedge;
+ topsite = e.reg[1];
+ if (p.x > topsite.coord.x)
+ right_of_site = true;
+ else
+ right_of_site = false;
+ if (right_of_site && el.ELpm == le)
+ return (true);
+ if (!right_of_site && el.ELpm == re)
+ return (false);
+
+ if (e.a == 1.0) {
+ dyp = p.y - topsite.coord.y;
+ dxp = p.x - topsite.coord.x;
+ fast = false;
+ if ((!right_of_site & (e.b < 0.0)) | (right_of_site & (e.b >= 0.0))) {
+ above = dyp >= e.b * dxp;
+ fast = above;
+ } else {
+ above = p.x + p.y * e.b > e.c;
+ if (e.b < 0.0)
+ above = !above;
+ if (!above)
+ fast = true;
+ }
+ if (!fast) {
+ dxs = topsite.coord.x - (e.reg[0]).coord.x;
+ above = e.b * (dxp * dxp - dyp * dyp) < dxs * dyp
+ * (1.0 + 2.0 * dxp / dxs + e.b * e.b);
+ if (e.b < 0.0)
+ above = !above;
+ }
+ } else /* e.b==1.0 */
+ {
+ yl = e.c - e.a * p.x;
+ t1 = p.y - yl;
+ t2 = p.x - topsite.coord.x;
+ t3 = yl - topsite.coord.y;
+ above = t1 * t1 > t2 * t2 + t3 * t3;
+ }
+ return (el.ELpm == le ? above : !above);
+ }
+
+ /**
+ * Bringt rechte (oder Linke?) Site von he zurück. Falls es das nicht gibt,
+ * wird bottomsite zurückgeliefert
+ *
+ * @param he
+ * @return
+ */
+ Site rightreg(Halfedge he) {
+ if (he.ELedge == (Edge) null)
+ // if this halfedge has no edge, return the bottom site (whatever
+ // that is)
+ return (bottomsite);
+
+ // if the ELpm field is zero, return the site 0 that this edge bisects,
+ // otherwise return site number 1
+ return (he.ELpm == le ? he.ELedge.reg[re] : he.ELedge.reg[le]);
+ }
+
+ /**
+ * Distance between two points
+ */
+ double dist(Site s, Site t) {
+ double dx, dy;
+ dx = s.coord.x - t.coord.x;
+ dy = s.coord.y - t.coord.y;
+ return (double) (Math.sqrt(dx * dx + dy * dy));
+ }
+
+ /**
+ * create a new site where the HalfEdges el1 and el2 intersect - note that
+ * the Point in the argument list is not used, don't know why it's there
+ *
+ * @param el1
+ * @param el2
+ * @return
+ */
+ Site intersect(Halfedge el1, Halfedge el2) {
+ Edge e1, e2, e;
+ Halfedge el;
+ double d, xint, yint;
+ boolean right_of_site;
+ Site v;
+
+ e1 = el1.ELedge;
+ e2 = el2.ELedge;
+ if (e1 == null || e2 == null)
+ return null;
+
+ // if the two edges bisect the same parent, return null
+ if (e1.reg[1] == e2.reg[1])
+ return null;
+
+ d = e1.a * e2.b - e1.b * e2.a;
+ if (-1.0e-10 < d && d < 1.0e-10)
+ return null;
+
+ xint = (e1.c * e2.b - e2.c * e1.b) / d;
+ yint = (e2.c * e1.a - e1.c * e2.a) / d;
+
+ if ((e1.reg[1].coord.y < e2.reg[1].coord.y)
+ || (e1.reg[1].coord.y == e2.reg[1].coord.y && e1.reg[1].coord.x < e2.reg[1].coord.x)) {
+ el = el1;
+ e = e1;
+ } else {
+ el = el2;
+ e = e2;
+ }
+
+ right_of_site = xint >= e.reg[1].coord.x;
+ if ((right_of_site && el.ELpm == le)
+ || (!right_of_site && el.ELpm == re))
+ return null;
+
+ // create a new site at the point of intersection - this is a new vector
+ // event waiting to happen
+ v = new Site();
+ v.coord.x = xint;
+ v.coord.y = yint;
+ return (v);
+ }
+
+ /**
+ * Zeigt sachen an, wenn VorSim = 1. Sonst tut es nichts
+ *
+ * @param s1
+ * @param s2
+ * @param s3
+ */
+ void out_triple(Site s1, Site s2, Site s3) {
+
+ if (VorSim) {
+ double P1X = s1.coord.x;
+ double P1Y = s1.coord.y;
+ double P2X = s2.coord.x;
+ double P2Y = s2.coord.y;
+ double P3X = s3.coord.x;
+ double P3Y = s3.coord.y;
+
+ double l1a = P2X - P1X;
+ double l1b = P2Y - P1Y;
+ double l1c = (P1Y * P1Y - P2Y * P2Y + P1X * P1X - P2X * P2X) * 0.5000;
+ double l2a = P2X - P3X;
+ double l2b = P2Y - P3Y;
+ double l2c = (P3Y * P3Y - P2Y * P2Y + P3X * P3X - P2X * P2X) * 0.5000;
+
+ if (l1a * l2b == l1b * l2a)
+ return;
+ double x = (l1c * l2b - l1b * l2c) / (l1b * l2a - l1a * l2b);
+ double y = (l1a * l2c - l1c * l2a) / (l1b * l2a - l1a * l2b);
+
+ double d = Math.sqrt(Math.pow(s1.coord.x - x, 2)
+ + Math.pow(s1.coord.y - y, 2));
+
+ g.setColor(Color.red);
+ g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P2X - (int) (w / 2), (int) P2Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P3X - (int) (w / 2), (int) P3Y - (int) (h / 2), w,
+ h);
+ g.setColor(Color.blue);
+ g.drawOval((int) (x - d), (int) (y - d), (int) (2 * d),
+ (int) (2 * d));
+ c.repaint();
+ try {
+ Thread.sleep(300);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ g.setColor(Color.lightGray);
+ g.drawOval((int) (x - d), (int) (y - d), (int) (2 * d),
+ (int) (2 * d));
+ g.setColor(Color.black);
+ g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P2X - (int) (w / 2), (int) P2Y - (int) (h / 2), w,
+ h);
+ g.fillOval((int) P3X - (int) (w / 2), (int) P3Y - (int) (h / 2), w,
+ h);
+ c.repaint();
+ }
+ }
+
+ int beachline_bake[] = null;
+
+ /**
+ * tut nichts wenn VorSim == false
+ */
+ void out_beachline() {
+ if (VorSim) {
+ if (beachline_bake == null) {
+ beachline_bake = new int[(int) (borderMaxX - borderMinX)];
+ for (int x = (int) borderMinX; x < (int) borderMaxX; x++) {
+ beachline_bake[x] = 0;
+ }
+ }
+ for (int x = (int) borderMinX; x < (int) borderMaxX; x++) {
+ g.setColor(Color.lightGray);
+ g.fillOval(x, beachline_bake[x], 1, 1);
+
+ Site s = sites[siteidx - 1];
+ double y0 = s.coord.y;
+ Halfedge he = ELleftend;
+ int y = (int) 0;
+ do {
+ Site v = rightreg(he);
+ double x1 = v.coord.x;
+ double y1 = v.coord.y;
+ int y2 = (int) ((y0 * y0 - (x1 - x) * (x1 - x) - y1 * y1) / (2 * y0 - 2 * y1));
+ if (y2 > y)
+ y = y2;
+ he = he.ELright;
+ } while (he.ELright != null);
+ if (y != 0) {
+ g.setColor(Color.red);
+ g.fillOval(x, y, 1, 1);
+ c.repaint();
+ beachline_bake[x] = y;
+ }
+ }
+ try {
+ Thread.sleep(1000);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ }
+ }
+
+ /**
+ * Does nothing when VorSim isn't enabled
+ *
+ * @param s1
+ */
+ void out_site(Site s1) {
+
+ if (VorSim) {
+ if (s1 == null)
+ return;
+ double P1X = s1.coord.x;
+ double P1Y = s1.coord.y;
+ g.setColor(Color.lightGray);
+ g.drawLine((int) borderMinX, (int) lasty, (int) borderMaxX,
+ (int) lasty);
+ g.setColor(Color.black);
+ g.drawLine((int) borderMinX, (int) P1Y, (int) borderMaxX, (int) P1Y);
+ g.setColor(Color.red);
+ g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w,
+ h);
+ c.repaint();
+ try {
+ Thread.sleep(1000);
+ } catch (InterruptedException ee) {
+ ;
+ }
+ g.setColor(Color.black);
+ g.drawLine((int) borderMinX, (int) P1Y, (int) borderMaxX, (int) P1Y);
+ g.fillOval((int) P1X - (int) (w / 2), (int) P1Y - (int) (h / 2), w,
+ h);
+ c.repaint();
+ lasty = P1Y;
+ }
+ }
+
+ /*
+ * implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax, deltax,
+ * deltay (can all be estimates). Performance suffers if they are wrong;
+ * better to make nsites, deltax, and deltay too big than too small. (?)
+ */
+
+ /**
+ * der eigentliche algorithmus
+ */
+ boolean voronoi_bd() {
+ isGenerated = true;
+ // clear edges
+ edges.clear();
+ edges = new ArrayList<Edge>(200);
+ // clear other lists
+ // corresponding.clear();
+ Site newsite, bottom, top, temp, p;
+ Site v;
+ Point newintstar = null;
+ int pm;
+ Halfedge lbnd, rbnd, llbnd, rrbnd, bisector;
+ Edge e;
+
+ PQinitialize();
+ ELinitialize();
+
+ bottomsite = nextone();
+ out_site(bottomsite);
+ newsite = nextone();
+ while (true) {
+ if (!PQempty())
+ newintstar = PQ_min();
+ // if the lowest site has a smaller y value than the lowest vector
+ // intersection,
+ // process the site otherwise process the vector intersection
+
+ if (newsite != null
+ && (PQempty() || newsite.coord.y < newintstar.y || (newsite.coord.y == newintstar.y && newsite.coord.x < newintstar.x))) {
+ out_site(newsite);
+ /* new site is smallest -this is a site event */
+ // get the first HalfEdge to the LEFT of the new site
+ // richy: left bound
+ lbnd = ELleftbnd((newsite.coord));
+ // get the first HalfEdge to the RIGHT of the new site
+ // richy: right bound
+ rbnd = ELright(lbnd);
+ // if this halfedge has no edge,bot =bottom site (whatever that
+ // is)
+ bottom = rightreg(lbnd);
+ // create a new edge that bisects. Baue Halbierende
+ e = bisect(bottom, newsite); // richy: e gehört zu bottom,
+ // newsite
+
+ // create a new HalfEdge, setting its ELpm field to 0
+ bisector = HEcreate(e, le); // richy: e in HalfEdge wandeln?
+ // insert this new bisector (Halbierende) edge between the left
+ // and right
+ // vectors in a linked list
+ ELinsert(lbnd, bisector);
+
+ // if the new bisector intersects with the left edge,
+ // remove the left edge's vertex, and put in the new one
+ // p wird hier zugewiesen. p scheint aber "nur" ein Schnittpunkt
+ // zweier Kanten zu sein
+ if ((p = intersect(lbnd, bisector)) != null) {
+ PQdelete(lbnd);
+ PQinsert(lbnd, p, dist(p, newsite), newsite);
+ }
+ lbnd = bisector;
+ // create a new HalfEdge, setting its ELpm field to 1
+ bisector = HEcreate(e, re);
+ // insert the new HE to the right of the original bisector
+ // earlier in the IF stmt
+ ELinsert(lbnd, bisector);
+
+ // if this new bisector intersects with the new HalfEdge
+ if ((p = intersect(bisector, rbnd)) != null) {
+ // push the HE into the ordered linked list of vertices
+ PQinsert(bisector, p, dist(p, newsite), newsite); // PQinsert
+ // ändern
+ // Richy:hier werden die Kanten tatsächlich eingefügt.
+ // Vielleicht
+ // das isert hier machen!!!!!!!
+ // edges.add(e);
+ }
+ out_beachline();
+ newsite = nextone(); // (nur) hier wird eine neue Site geholt!
+ } else if (!PQempty())
+ /* intersection is smallest - this is a vector event */
+ // richy: vertices are created here
+ {
+ // pop the HalfEdge with the lowest vector off the ordered list
+ // of vectors
+ lbnd = PQextractmin(); // lbnd: left bound?
+ // get the HalfEdge to the left of the above HE
+ llbnd = ELleft(lbnd); // richy: left of left bound
+ // get the HalfEdge to the right of the above HE
+ rbnd = ELright(lbnd);
+ // get the HalfEdge to the right of the HE to the right of the
+ // lowest HE
+ rrbnd = ELright(rbnd);
+ // get the Site to the left of the left HE which it bisects
+ bottom = leftreg(lbnd);
+ // get the Site to the right of the right HE which it bisects
+ top = rightreg(rbnd);
+
+ // output the triple of sites, stating that a circle goes
+ // through them
+ out_triple(bottom, top, rightreg(lbnd));
+
+ v = lbnd.vertex; // get the vertex that caused this event
+ makevertex(v); // set the vertex number - couldn't do this
+ // earlier since we didn't know when it would be processed
+ // GraphEdge one = endpoint(lbnd.ELedge, lbnd.ELpm, v); //
+ // richy:
+ // bottom
+ // and
+ // top maybe?
+ // diese zwei endpoints könnten eine zu bottom und top
+ // zugehörige kante sein!
+
+ // set the endpoint of
+ // the left HalfEdge to be this vector
+ // GraphEdge two = endpoint(rbnd.ELedge, rbnd.ELpm, v);
+ // set the endpoint of the right HalfEdge to
+ // be this vector
+ // richy linien zeugs: die Kanten one und two gehören zu punkte
+ // top&bottom
+ /*
+ * PointAndLines tempP2D1 = new PointAndLines(); tempP2D1.coord
+ * = bottom.coord; Line2D line1 = new Line2D.Double(); if (one
+ * != null) line1.setLine(one.x1, one.y1, one.x2, one.y2);
+ * Line2D line2 = new Line2D.Double(); if (two != null)
+ * line2.setLine(two.x1, two.y1, two.x2, two.y2);
+ * tempP2D1.corrLines.add(line1); tempP2D1.corrLines.add(line2);
+ * corresponding.add(tempP2D1);
+ */
+ PointAndLines tempP2D1 = new PointAndLines();
+ tempP2D1.coord = bottom.coord;
+ Line2D line1 = new Line2D.Double();
+ line1.setLine(bottom.coord.x, bottom.coord.y, v.coord.x,
+ v.coord.y);
+ if (line1 != null) {
+ tempP2D1.corrLines.add(line1);
+ }
+ // corresponding.add(tempP2D1);
+
+ ELdelete(lbnd); // mark the lowest HE for
+ // deletion - can't delete yet because there might be pointers
+ // to it in Hash Map
+ PQdelete(rbnd);
+ // remove all vertex events to do with the right HE
+ ELdelete(rbnd); // mark the right HE for
+ // deletion - can't delete yet because there might be pointers
+ // to it in Hash Map
+ pm = le; // set the pm variable to zero
+
+ // richy: v and newsite seem to be the points that are involved
+ // in this line.
+ // or bottom and top?
+
+ if (bottom.coord.y > top.coord.y)
+ // if the site to the left of the event is higher than the
+ // Site
+ { // to the right of it, then swap them and set the 'pm'
+ // variable to 1
+ temp = bottom;
+ bottom = top;
+ top = temp;
+ pm = re;
+ }
+ e = bisect(bottom, top); // create an Edge (or line)
+ // that is between the two Sites. This creates the formula of
+ // the line, and assigns a line number to it
+ bisector = HEcreate(e, pm); // create a HE from the Edge 'e',
+ // and make it point to that edge
+ // with its ELedge field
+ ELinsert(llbnd, bisector); // insert the new bisector to the
+ // right of the left HE
+ endpoint(e, re - pm, v); // set one endpoint to the new edge
+ // to be the vector point 'v'.
+ // If the site to the left of this bisector is higher than the
+ // right Site, then this endpoint
+ // is put in position 0; otherwise in pos 1
+
+ // if left HE and the new bisector intersect, then delete
+ // the left HE, and reinsert it
+ if ((p = intersect(llbnd, bisector)) != null) {
+ PQdelete(llbnd);
+ PQinsert(llbnd, p, dist(p, bottom), p);
+ }
+
+ // if right HE and the new bisector intersect, then
+ // reinsert it
+ if ((p = intersect(bisector, rrbnd)) != null) {
+ PQinsert(bisector, p, dist(p, bottom), p);
+ }
+
+ // hier startet eine neue Ieration
+ // PointAndVertices verts = new PointAndVertices();
+ // if (bottom != null) {
+ // verts.Punkt.x = bottom.coord.x;
+ // verts.Punkt.y = bottom.coord.y;
+ // }
+ // nun an den Punkt die äußeren Kanten anfügen
+ Point point = null;
+ if (lbnd != null && lbnd.vertex != null) {
+ point = new Point();
+ point.x = (int) lbnd.vertex.coord.x;
+ point.y = (int) lbnd.vertex.coord.y;
+ // verts.polygon.add(point);
+ }
+ if (llbnd != null && llbnd.vertex != null) {
+ point = new Point();
+ point.x = (int) llbnd.vertex.coord.x;
+ point.y = (int) llbnd.vertex.coord.y;
+ // verts.polygon.add(point);
+ }
+ if (rbnd != null && rbnd.vertex != null) {
+ point = new Point();
+ point.x = (int) rbnd.vertex.coord.x;
+ point.y = (int) rbnd.vertex.coord.y;
+ // verts.polygon.add(point);
+ }
+
+ // polygon.add(verts);
+
+ // richy: schaue mal e, lbnd, rbdn und llbnd an
+
+ } else
+ break;
+ } // hier ist die while (true) Schleife zu ende
+
+ for (lbnd = ELright(ELleftend); lbnd != ELrightend; lbnd = ELright(lbnd)) {
+ e = lbnd.ELedge;
+ clip_line(e, null);
+ }
+ endsim();
+ return true;
+ }
+
+ /**
+ * Generates Voronoi
+ *
+ * @param minX
+ * @param maxX
+ * maximum x size of diagram
+ * @param minY
+ * @param maxY
+ * maximum y size of diagram
+ * @return
+ */
+ public boolean generateVoronoi(double minX, double maxX, double minY,
+ double maxY) {
+ edges = new ArrayList<Edge>(1000);
+ double temp = 0;
+ if (minX > maxX) {
+ temp = minX;
+ minX = maxX;
+ maxX = temp;
+ }
+ if (minY > maxY) {
+ temp = minY;
+ minY = maxY;
+ maxY = temp;
+ }
+ borderMinX = minX;
+ borderMinY = minY;
+ borderMaxX = maxX;
+ borderMaxY = maxY;
+
+ siteidx = 0;
+ voronoi_bd();
+ isGenerated = true;
+
+ // clean edges
+ // cleanEdgeList();
+
+ return true;
+ }
+
+ @SuppressWarnings("unused")
+ private void cleanEdgeList() {
+ ArrayList<Edge> result = new ArrayList<Edge>();
+ Edge temp;
+ for (int i = 0; i < edges.size(); i++) {
+ temp = edges.get(i);
+ // search if temp is only once in edges. if so, go on. else, delete
+ // the others
+ for (int j = i; j < edges.size(); j++) {
+ // if (temp.ep[0].equals(edges.get(j).ep[0]))
+ }
+ }
+
+ }
+
+ void endsim() {
+ if (VorSim) {
+ g.setColor(Color.lightGray);
+ g.drawLine((int) borderMinX, (int) lasty, (int) borderMaxX,
+ (int) lasty);
+ if (beachline_bake != null) {
+ for (int x = (int) borderMinX; x < (int) borderMaxX; x++) {
+ g.setColor(Color.lightGray);
+ g.fillOval(x, beachline_bake[x], 1, 1);
+
+ }
+ }
+ c.repaint();
+ }
+
+ }
+
+ /**
+ * Zeichnet das Diagramm in Graphics g
+ *
+ * @param g
+ */
+ public void DrawVor(Graphics g) {
+ double minX, maxX, minY, maxY;
+ minX = 0;
+ minY = 0;
+ maxX = 1500;
+ maxY = 1500;
+
+ generateVoronoi(minX, maxX, minY, maxY);
+
+ resetIterator();
+ GraphEdge temp = null;
+ g.setColor(Color.black);
+
+ // vom Entwickler gemachte Schleife
+ while ((temp = getNext()) != null) {
+ g.drawLine((int) temp.x1, (int) temp.y1, (int) temp.x2,
+ (int) temp.y2);
+ if (temp.correspondingPt != null) {
+ g.drawRect((int) temp.correspondingPt.coord.x - 1,
+ (int) temp.correspondingPt.coord.y - 1, 2, 2);// Eckpunkte
+ }
+
+ }
+
+ /*
+ * g.setColor(Color.black); Random r = new Random(); // corresponding
+ * malen g.setColor(Color.green); for (PointAndLines points :
+ * corresponding) { if (points == null || points.coord.y != 224 ||
+ * points.coord.x != 344) continue; // g.setColor(new
+ * Color(r.nextInt(256), r.nextInt(256), // r.nextInt(256)));
+ * g.setColor(Color.blue); g.drawRect((int) points.coord.x - 1, (int)
+ * points.coord.y - 1, 2, 2); for (Line2D line : points.corrLines) {
+ * g.drawLine((int) line.getX1(), (int) line.getY1(), (int)
+ * line.getX2(), (int) line.getY2()); } }
+ *
+ * // Points and Vertices zeichnen! g.setColor(Color.red); for
+ * (PointAndVertices current : polygon) { if (current.Punkt.x != 344 ||
+ * current.Punkt.y != 224) continue; g.drawRect((int) current.Punkt.x,
+ * (int) current.Punkt.y, 2, 2); for (Point points : current.polygon) {
+ * if (points != null) g.drawRect((int) points.x, (int) points.y, 2, 2);
+ *
+ * } } /*
+ *
+ * // start richy // draw the points? // halfedges malen
+ * resetIterator(); Halfedge bla; g.setColor(Color.yellow); /* while
+ * ((bla = ELleftend.PQnext) != null) { g.drawRect((int)
+ * bla.vertex.coord.x, (int) bla.vertex.coord.y, 2, 2); if
+ * ((bla.ELedge.ep[0].coord.x == 344 || bla.ELedge.ep[1].coord.x == 344)
+ * && (bla.ELedge.ep[0].coord.y == 224 || bla.ELedge.ep[1].coord.y ==
+ * 224)) { g.drawRect((int) bla.ELedge.ep[0].coord.x, (int)
+ * bla.ELedge.ep[1].coord.y, 2, 2); g.drawLine((int)
+ * bla.ELedge.reg[0].coord.x, (int) bla.ELedge.reg[0].coord.y, (int)
+ * bla.ELedge.reg[1].coord.x, (int) bla.ELedge.reg[1].coord.y); } }
+ */
+
+ // <so geht das!!!!!!!!!!!!!!!!!!!!!!!> Siehe edges!
+ /*
+ * g.setColor(Color.yellow); for (Edge tempedge : edges) { if
+ * ((tempedge.reg[0].coord.x == 272 && tempedge.reg[0].coord.y == 136)
+ * || (tempedge.reg[1].coord.x == 272 && tempedge.reg[1].coord.y ==
+ * 136)) { try { g.drawRect((int) tempedge.reg[0].coord.x - 1, (int)
+ * tempedge.reg[0].coord.y - 1, 3, 3); g.drawLine((int)
+ * tempedge.ep[0].coord.x, (int) tempedge.ep[0].coord.y, (int)
+ * tempedge.ep[1].coord.x, (int) tempedge.ep[1].coord.y); } catch
+ * (Exception e) { System.out.println("Hat nicht geklappt"); } } }/*
+ * //</so geht das>
+ *
+ * // end richy return; }
+ */
+ }
+ /*
+ * public Weight[] getWeights(int x, int y, voronoi original) { Polygon
+ * interpolator = getPoly(x, y); // get the neighbors of this x,y
+ * ArrayList<Point2D> neighbors = getDirectNeighbors(x, y); // get the
+ * polygons for each neighbor out of original
+ *
+ * return null; }
+ */
+
+}
+
+class PointAndLines {
+ Point coord;
+ ArrayList<Line2D> corrLines = new ArrayList<Line2D>();
+
+ // constructor not needed!
+
+ public void removeDuplicates() {
+ // ArrayList<Line2D> resultList = new ArrayList<Line2D>(10);
+ // Line2D result;
+ for (int i = 0; i < corrLines.size(); i++) {
+
+ }
+ }
+
+ public boolean contains(Line2D line) {
+ for (int i = 0; i < corrLines.size(); i++) {
+ Line2D current = corrLines.get(i);
+ if (current.getX1() == line.getX1()
+ && current.getX2() == line.getX2()
+ && current.getY1() == line.getY1()
+ && current.getY2() == line.getY2())
+ return true;
+ }
+ return false;
+ }
+}
+
+/**
+ * Should store a Point and the corresponding intersections of the voronoi
+ *
+ * @author richy
+ *
+ */
+class PointAndVertices {
+ Point Punkt = new Point();
+ ArrayList<Point> polygon = new ArrayList<Point>(10);
+}