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 corresponding = new ArrayList(); // // richy // ArrayList polygon = new ArrayList(); // // richy ArrayList edges = new ArrayList(); // 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 points = new ArrayList(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 * output = new ArrayList(); 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 * containingPTs = new ArrayList(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 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 lines = new ArrayList(); 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 getDirectNeighbors(double x, double y) { Site s = new Site(); s.coord.x = x; s.coord.y = y; Edge currEdge; ArrayList result = new ArrayList(); 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 xVal = new ArrayList(); ArrayList yVal = new ArrayList(); if (!Double.isNaN(xcoord) && !Double.isNaN(ycoord)) { xVal.add(xcoord); yVal.add(ycoord); } edges = new ArrayList(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(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(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 result = new ArrayList(); 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); } } */ // 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"); } } }/* * // * * // 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 neighbors = getDirectNeighbors(x, y); // get the * polygons for each neighbor out of original * * return null; } */ } class PointAndLines { Point coord; ArrayList corrLines = new ArrayList(); // constructor not needed! public void removeDuplicates() { // ArrayList resultList = new ArrayList(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 polygon = new ArrayList(10); }