summaryrefslogtreecommitdiffstats
path: root/voronoi/voronoi.java
diff options
context:
space:
mode:
Diffstat (limited to 'voronoi/voronoi.java')
-rw-r--r--voronoi/voronoi.java2228
1 files changed, 2228 insertions, 0 deletions
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);
+}