001: /***********************************************
002: * created on 12.06.2006
003: * last modified:
004: *
005: * author: sstein
006: *
007: * description:
008: *
009: *
010: ***********************************************/package org.openjump.core.graph.delauneySimplexInsert;
011:
012: import java.util.ArrayList;
013: import java.util.Collection;
014: import java.util.Iterator;
015: import java.util.Set;
016:
017: import com.vividsolutions.jts.geom.Coordinate;
018: import com.vividsolutions.jts.geom.Geometry;
019: import com.vividsolutions.jts.geom.GeometryFactory;
020: import com.vividsolutions.jts.geom.LineString;
021: import com.vividsolutions.jts.geom.LinearRing;
022: import com.vividsolutions.jts.geom.Point;
023: import com.vividsolutions.jts.operation.polygonize.Polygonizer;
024:
025: /**
026: * @author sstein
027: *
028: * Use the class to access the delauney trinagulation by L. Paul Chew
029: * Methods of the class are modified versions from DelaunayPanel.java in DelaunayAp.java.
030: */
031: public class DTriangulationForJTS {
032: private DelaunayTriangulation dt; // The Delaunay triangulation
033: private Simplex initialTriangle; // The large initial triangle
034: private int initialSize = 10000; // Controls size of initial triangle
035: private boolean isVoronoi; // True iff VoD instead of DT
036: private double dx = 0;
037: private double dy = 0;
038: private Pnt lowerLeftPnt = null;
039: public boolean debug = false; // True iff printing info for debugging
040:
041: public DTriangulationForJTS(ArrayList pointList) {
042: double argmaxx = 0;
043: double argmaxy = 0;
044: double argminx = 0;
045: double argminy = 0;
046: int count = 0;
047: //-- calc coordinates of initial symplex
048: for (Iterator iter = pointList.iterator(); iter.hasNext();) {
049: Point pt = (Point) iter.next();
050: if (count == 0) {
051: argmaxx = pt.getX();
052: argminx = pt.getX();
053: argmaxy = pt.getY();
054: argminy = pt.getY();
055: } else {
056: if (pt.getX() < argminx) {
057: argminx = pt.getX();
058: }
059: if (pt.getX() > argmaxx) {
060: argmaxx = pt.getX();
061: }
062: if (pt.getY() < argminy) {
063: argminy = pt.getY();
064: }
065: if (pt.getY() > argmaxy) {
066: argmaxy = pt.getY();
067: }
068: }
069: count++;
070: }
071: this .dx = argmaxx - argminx;
072: this .dy = argmaxy - argminy;
073: //-- the initial simplex must contain all points
074: //-- take the bounding box, move the diagonals (sidewards)
075: // the meeting point will be the mirrored bbox-center on the top edge
076: this .initialTriangle = new Simplex(new Pnt[] {
077: new Pnt(argminx - (1.5 * dx), argminy - dy), //lower left
078: new Pnt(argmaxx + (1.5 * dx), argminy - dy), //lower right
079: //new Pnt(argminx+(dx/2.0), argmaxy+(dy/2.0))}); //center, top
080: new Pnt(argminx + (dx / 2.0), argmaxy + 1.5 * dy) }); //center, top
081:
082: this .lowerLeftPnt = new Pnt(argminx - (1.5 * dx), argminy - dy);
083: this .dt = new DelaunayTriangulation(initialTriangle);
084: this .addPoints(pointList);
085: }
086:
087: public void addPoints(ArrayList pointList) {
088: for (Iterator iter = pointList.iterator(); iter.hasNext();) {
089: try {
090: Geometry element = (Geometry) iter.next();
091: if (element instanceof Point) {
092: Point jtsPt = (Point) element;
093: Pnt point = new Pnt(jtsPt.getX(), jtsPt.getY());
094: dt.delaunayPlace(point);
095: } else {
096: if (debug)
097: System.out.println("no point geometry");
098: }
099: } catch (Exception e) {
100: if (debug)
101: System.out.println("no geometry");
102: }
103: }
104: }
105:
106: public void addPoint(double x, double y) {
107: Pnt point = new Pnt(x, y);
108: if (debug)
109: System.out.println("Click " + point);
110: dt.delaunayPlace(point);
111: }
112:
113: /**
114: * Draw all the Delaunay edges.
115: * @return Arraylist with LineString geometries.
116: */
117: public ArrayList drawAllDelaunay() {
118: // Loop through all the edges of the DT (each is done twice)
119: GeometryFactory gf = new GeometryFactory();
120: ArrayList lines = new ArrayList();
121: for (Iterator it = dt.iterator(); it.hasNext();) {
122: Simplex triangle = (Simplex) it.next();
123: for (Iterator otherIt = triangle.facets().iterator(); otherIt
124: .hasNext();) {
125: Set facet = (Set) otherIt.next();
126: Pnt[] endpoint = (Pnt[]) facet.toArray(new Pnt[2]);
127: Coordinate[] coords = new Coordinate[2];
128: coords[0] = new Coordinate(endpoint[0].coord(0),
129: endpoint[0].coord(1));
130: coords[1] = new Coordinate(endpoint[1].coord(0),
131: endpoint[1].coord(1));
132: LineString ls = gf.createLineString(coords);
133: lines.add(ls);
134: }
135: }
136: return lines;
137: }
138:
139: /**
140: * Draw all the Voronoi edges.
141: * @return Arraylist with LineString geometries.
142: */
143: public ArrayList drawAllVoronoi() {
144: GeometryFactory gf = new GeometryFactory();
145: ArrayList lines = new ArrayList();
146: // Loop through all the edges of the DT (each is done twice)
147: for (Iterator it = dt.iterator(); it.hasNext();) {
148: Simplex triangle = (Simplex) it.next();
149: for (Iterator otherIt = dt.neighbors(triangle).iterator(); otherIt
150: .hasNext();) {
151: Simplex other = (Simplex) otherIt.next();
152: Pnt p = Pnt.circumcenter((Pnt[]) triangle
153: .toArray(new Pnt[0]));
154: Pnt q = Pnt.circumcenter((Pnt[]) other
155: .toArray(new Pnt[0]));
156: Coordinate[] coords = new Coordinate[2];
157: coords[0] = new Coordinate(p.coord(0), p.coord(1));
158: coords[1] = new Coordinate(q.coord(0), q.coord(1));
159: LineString ls = gf.createLineString(coords);
160: lines.add(ls);
161: }
162: }
163: return lines;
164: }
165:
166: /**
167: * Draw all the sites (i.e., the input points) of the DT.
168: * @return Arraylist with point geometries.
169: */
170: public ArrayList drawAllSites() {
171: // Loop through all sites of the DT
172: // Each is done several times, about 6 times each on average; this
173: // can be proved via Euler's formula.
174: GeometryFactory gf = new GeometryFactory();
175: ArrayList points = new ArrayList();
176: for (Iterator it = dt.iterator(); it.hasNext();) {
177: for (Iterator otherIt = ((Simplex) it.next()).iterator(); otherIt
178: .hasNext();) {
179: Pnt pt = (Pnt) otherIt.next();
180: Coordinate coord = new Coordinate(pt.coord(0), pt
181: .coord(1));
182: Point jtsPt = gf.createPoint(coord);
183: points.add(jtsPt);
184: }
185: }
186: return points;
187: }
188:
189: /**
190: * Draw all the empty circles (one for each triangle) of the DT.
191: * @return Arraylist with polygon geometries.
192: */
193: public ArrayList drawAllCircles() {
194: // Loop through all triangles of the DT
195: GeometryFactory gf = new GeometryFactory();
196: ArrayList circles = new ArrayList();
197: loop: for (Iterator it = dt.iterator(); it.hasNext();) {
198: Simplex triangle = (Simplex) it.next();
199: for (Iterator otherIt = initialTriangle.iterator(); otherIt
200: .hasNext();) {
201: Pnt p = (Pnt) otherIt.next();
202: if (triangle.contains(p))
203: continue loop;
204: }
205: Pnt c = Pnt.circumcenter((Pnt[]) triangle
206: .toArray(new Pnt[0]));
207: double radius = c
208: .subtract((Pnt) triangle.iterator().next())
209: .magnitude();
210: Coordinate coord = new Coordinate(c.coord(0), c.coord(1));
211: Point jtsPt = gf.createPoint(coord);
212: circles.add(jtsPt.buffer(radius));
213: }
214: return circles;
215: }
216:
217: public DelaunayTriangulation getDelaunayTriangulation() {
218: return dt;
219: }
220:
221: /**
222: *
223: * @return the corner points of the initial simplex which is divided
224: * into smaller simplexes by the iterative insertion of the point dataset
225: */
226: public ArrayList getInitialSimmplexAsJTSPoints() {
227: GeometryFactory gf = new GeometryFactory();
228: ArrayList points = new ArrayList();
229:
230: for (Iterator otherIt = this .initialTriangle.iterator(); otherIt
231: .hasNext();) {
232: Pnt pt = (Pnt) otherIt.next();
233: Coordinate coord = new Coordinate(pt.coord(0), pt.coord(1));
234: Point jtsPt = gf.createPoint(coord);
235: points.add(jtsPt);
236: }
237: return points;
238: }
239:
240: /**
241: * the size of the box has been empirically defined to get "undistorted"
242: * outer thiessen polygons
243: * @return a bounding box necesseray to create the final thiessenpolygons
244: */
245: public Geometry getThiessenBoundingBox() {
246: GeometryFactory gf = new GeometryFactory();
247: Coordinate[] coords = new Coordinate[5];
248: coords[0] = new Coordinate(this .lowerLeftPnt.coord(0) + 1
249: * this .dx, this .lowerLeftPnt.coord(1) + 0.5 * this .dy); //lowerleft
250: coords[1] = new Coordinate(this .lowerLeftPnt.coord(0) + 3
251: * this .dx, this .lowerLeftPnt.coord(1) + 0.5 * this .dy); //lowerright
252: coords[2] = new Coordinate(this .lowerLeftPnt.coord(0) + 3
253: * this .dx, this .lowerLeftPnt.coord(1) + 2.5 * this .dy); //topright
254: coords[3] = new Coordinate(this .lowerLeftPnt.coord(0) + 1
255: * this .dx, this .lowerLeftPnt.coord(1) + 2.5 * this .dy); //topleft
256: //-- to close linestring
257: coords[4] = new Coordinate(this .lowerLeftPnt.coord(0) + 1
258: * this .dx, this .lowerLeftPnt.coord(1) + 0.5 * dy); //lowerleft
259: LinearRing lr = gf.createLinearRing(coords);
260: Geometry bbox = gf.createPolygon(lr, null);
261: return bbox;
262: }
263:
264: /**
265: * Method returns thiessen polygons within a empirically enlarged
266: * bounding box around the point set. Therefore the voronoi edges are
267: * polygonized and the intersecting voronoi polygons with the bounding box
268: * are calculated. These intersecting thiessen polygons (in the bounding box) are returned.<p>
269: * Note: "thiesen" and "voronoi" is exchangeable.
270: * @return
271: */
272: public ArrayList getThiessenPolys() {
273: //-- do union of all edges and use the polygonizer to create polygons from it
274: if (debug)
275: System.out.println("get voronoi egdes");
276: ArrayList edges = this .drawAllVoronoi();
277: if (debug)
278: System.out
279: .println("merge voronoi egdes to multiLineString");
280: Geometry mls = (Geometry) edges.get(0);
281: for (int i = 1; i < edges.size(); i++) {
282: Geometry line = (Geometry) edges.get(i);
283: mls = mls.union(line);
284: }
285: if (debug)
286: System.out.println("polygonize");
287: Polygonizer poly = new Polygonizer();
288: poly.add(mls);
289: Collection polys = poly.getPolygons();
290: //-- get final polygons in bounding box (=intersection polygons with the bbox)
291: Geometry bbox = this .getThiessenBoundingBox();
292: if (debug)
293: System.out.println("get intersections and final polys..");
294: ArrayList finalPolys = new ArrayList();
295: for (Iterator iter = polys.iterator(); iter.hasNext();) {
296: Geometry candPoly = (Geometry) iter.next();
297: Geometry intersection = bbox.intersection(candPoly);
298: if (intersection != null) {
299: if (intersection.getArea() > 0) {
300: finalPolys.add(intersection);
301: }
302: }
303: }
304: return finalPolys;
305: }
306:
307: }
|