001/*
002 * Copyright (c) 2004-2010 The Regents of the University of California.
003 * All rights reserved.
004 *
005 * '$Author: welker $'
006 * '$Date: 2010-05-06 05:21:26 +0000 (Thu, 06 May 2010) $' 
007 * '$Revision: 24234 $'
008 * 
009 * Permission is hereby granted, without written agreement and without
010 * license or royalty fees, to use, copy, modify, and distribute this
011 * software and its documentation for any purpose, provided that the above
012 * copyright notice and the following two paragraphs appear in all copies
013 * of this software.
014 *
015 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
016 * FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
017 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
018 * THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
019 * SUCH DAMAGE.
020 *
021 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
022 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
023 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
024 * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
025 * CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
026 * ENHANCEMENTS, OR MODIFICATIONS.
027 *
028 */
029
030/**
031 *         <b>Name:</b> ConvexHull.java<br>
032 *      <b>Purpose:</b> Given a set of x,y points, this code calculates those points
033 *               which makeup the ConvexHull, a polygon which surrounds the
034 *               original set like a 'rubberband'. In this case, the 'wrapping paper'
035 *               algorithm' described at
036 *               http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
037 *               is used.<br>
038 *
039 *               Note that the ConvexHull points can be converted to a Java2D 'Shape'
040 *               Point location within the Hull can then be tested using Java2D methods.
041 *               There is also a method for 'scaling' the ConvexHull polygon about its center 
042 *
043 *       @author: Dan Higgins NCEAS UC Santa Barbara
044 *         @date: November, 2004  
045 *
046 */
047
048package org.ecoinformatics.seek.gis.java_gis;
049
050import java.awt.Shape;
051import java.awt.geom.AffineTransform;
052import java.awt.geom.GeneralPath;
053import java.awt.geom.PathIterator;
054import java.awt.geom.Point2D;
055import java.io.BufferedReader;
056import java.io.File;
057import java.io.FileOutputStream;
058import java.io.FileReader;
059import java.io.PrintWriter;
060import java.text.DecimalFormat;
061import java.util.StringTokenizer;
062import java.util.Vector;
063
064public class ConvexHull {
065
066        Vector pointList; // vector of points as Point2D.Double objects
067        Vector cvList; // ConvexHull list
068        Vector scvList; // scaled ConvexHull list
069
070        public ConvexHull() {
071        }
072
073        public int getCHListSize() {
074                if (cvList != null) {
075                        return cvList.size();
076                }
077                return 0;
078        }
079
080        public ConvexHull(File pointsFile) {
081                double x1, x2, x3, y1, y2, y3;
082                FileReader inReader = null;
083                BufferedReader bufReader = null;
084                try {
085                        inReader = new FileReader(pointsFile);
086                        bufReader = new BufferedReader(inReader);
087                        pointList = getPoints(bufReader);
088                } catch (Exception ee) {
089                        System.out.println("Exception reading points!");
090                }
091                Point2D cvpt = findFirstPoint(pointList);
092                Point2D cvpt1 = cvpt;
093                boolean flag = true;
094                int i, j;
095                cvList = new Vector();
096                cvList.addElement(cvpt);
097                do {
098                        for (i = 0; i < pointList.size(); i++) {
099                                flag = true;
100                                x1 = cvpt.getX();
101                                y1 = cvpt.getY();
102                                x2 = ((Point2D) pointList.elementAt(i)).getX();
103                                y2 = ((Point2D) pointList.elementAt(i)).getY();
104                                if ((x1 == x2) && (y1 == y2))
105                                        continue;
106                                for (j = 0; j < pointList.size(); j++) {
107                                        x3 = ((Point2D) pointList.elementAt(j)).getX();
108                                        y3 = ((Point2D) pointList.elementAt(j)).getY();
109                                        if ((x3 == x2) && (y3 == y2))
110                                                continue;
111                                        if ((x3 == x1) && (y3 == y1))
112                                                continue;
113                                        double det = x1 * (y2 - y3) - y1 * (x2 - x3)
114                                                        + (y3 * x2 - y2 * x3);
115                                        if (det > 0.0) {
116                                                flag = false;
117                                                break;
118                                        }
119                                } // end of j loop
120                                if (flag) {
121                                        cvpt = (Point2D) pointList.elementAt(i);
122                                        cvList.addElement(cvpt);
123                                        break;
124                                }
125                        } // end of i loop
126                } while (!((cvpt.getX() == cvpt1.getX()) && (cvpt.getY() == cvpt1
127                                .getY())));// end of do
128                // last point is a repeat of first, so remove it
129                cvList.removeElementAt(cvList.size() - 1);
130        }
131
132        public void listCVHullPts() {
133                for (int i = 0; i < cvList.size(); i++) {
134                        Point2D cvpt = (Point2D) cvList.elementAt(i);
135                        // System.out.println("X: "+cvpt.getX()+"   Y: "+cvpt.getY());
136                }
137        }
138
139        public void cvHullToFile(String outfileName) {
140                PrintWriter out = null;
141                DecimalFormat myFormatter = new DecimalFormat("##0.00000");
142
143                try {
144                        out = new PrintWriter(new FileOutputStream(outfileName));
145                        for (int i = 0; i < cvList.size(); i++) {
146                                Point2D cvpt = (Point2D) cvList.elementAt(i);
147                                double xval = cvpt.getX();
148                                out.print(" " + myFormatter.format(xval) + "  ");
149                                double yval = cvpt.getY();
150                                out.print(myFormatter.format(yval));
151                                out.println();
152                        }
153                } catch (Exception e) {
154                        System.out.println("Problem writing CHull output file!");
155                }
156                out.close();
157        }
158
159        public void cvScaledHullToFile(double scalefactor, String outfileName) {
160                createScaledShape(scalefactor);
161                PrintWriter out = null;
162                DecimalFormat myFormatter = new DecimalFormat("##0.00000");
163
164                try {
165                        out = new PrintWriter(new FileOutputStream(outfileName));
166                        for (int i = 0; i < scvList.size(); i++) {
167                                Point2D cvpt = (Point2D) scvList.elementAt(i);
168                                double xval = cvpt.getX();
169                                out.print(" " + myFormatter.format(xval) + "  ");
170                                double yval = cvpt.getY();
171                                out.print(myFormatter.format(yval));
172                                out.println();
173                        }
174                } catch (Exception e) {
175                        System.out.println("Problem writing ScaledCHull output file!");
176                }
177                out.close();
178        }
179
180        public Shape createShape() {
181                GeneralPath gp = new GeneralPath();
182                Point2D cvpt = (Point2D) cvList.elementAt(0);
183                gp.moveTo((float) (cvpt.getX()), (float) (cvpt.getY()));
184                for (int i = 1; i < cvList.size(); i++) {
185                        cvpt = (Point2D) cvList.elementAt(i);
186                        gp.lineTo((float) (cvpt.getX()), (float) (cvpt.getY()));
187                }
188                gp.closePath();
189                return gp;
190        }
191
192        public Shape createScaledShape(double scalefactor) {
193                Shape initshp = createShape();
194                // find center
195                double xcen = initshp.getBounds2D().getCenterX();
196                double ycen = initshp.getBounds2D().getCenterY();
197                AffineTransform at = AffineTransform.getTranslateInstance(-1.0 * xcen,
198                                -1.0 * ycen);
199                Shape sh1 = at.createTransformedShape(initshp);
200                at = AffineTransform.getScaleInstance(scalefactor, scalefactor);
201                Shape sh2 = at.createTransformedShape(sh1);
202                at = AffineTransform.getTranslateInstance(xcen, ycen);
203                Shape sh3 = at.createTransformedShape(sh2);
204
205                // get the scaled points
206                scvList = new Vector();
207                PathIterator pi = sh3.getPathIterator(null);
208                while (pi.isDone() == false) {
209                        double[] coords = new double[6];
210                        int type = pi.currentSegment(coords);
211                        // System.out.println("x: "+coords[0] + "  y: "+coords[1]);
212                        java.awt.geom.Point2D.Double pt = new java.awt.geom.Point2D.Double(
213                                        coords[0], coords[1]);
214                        scvList.addElement(pt);
215                        pi.next();
216                }
217                scvList.removeElementAt(scvList.size() - 1);
218                return sh3;
219        }
220
221        public static void main(String[] args) {
222                File df = new File("dataPoints.txt");
223                // System.out.println("File: "+ df);
224                long start = System.currentTimeMillis();
225                ConvexHull ch = new ConvexHull(df);
226                ch.cvHullToFile("HullPoints.txt");
227                long stop = System.currentTimeMillis();
228                ch.listCVHullPts();
229                Shape cvshape = ch.createShape();
230                System.out.println("Bounding Box: " + cvshape.getBounds2D());
231                System.out.println("Is (0, 0) inside? : " + cvshape.contains(0.0, 0.0));
232                System.out.println("Is (-50, -10) inside? : "
233                                + cvshape.contains(-50.0, -10.0));
234                Shape shx2 = ch.createScaledShape(2.0);
235                System.out.println("Scaled Bounding Box: " + shx2.getBounds2D());
236
237                System.out.println("Time(ms): " + (stop - start));
238        }
239
240        private Vector getPoints(BufferedReader br) {
241                String cachedLine = "";
242                double xval = 0.0;
243                double yval = 0.0;
244                Vector pts = new Vector();
245                // unsure exactly how many point lines there are
246                // but each line should have only two tokens
247                boolean eoh = false;
248                while (!eoh) {
249                        try {
250                                cachedLine = br.readLine();
251                                // System.out.println("cachedLine: "+cachedLine);
252                        } catch (Exception w) {
253                                System.out.println("error reading next line in points file!");
254                                eoh = true;
255                        }
256                        if (cachedLine == null)
257                                return pts;
258                        if (cachedLine.trim().length() > 0) {
259                                StringTokenizer st = new StringTokenizer(cachedLine);
260                                int cnt = st.countTokens(); // should be only 2
261                                if (cnt != 2)
262                                        eoh = true;
263                                String firstToken = st.nextToken().trim();
264                                String secondToken = st.nextToken().trim();
265                                try {
266                                        xval = java.lang.Double.parseDouble(firstToken);
267                                        yval = java.lang.Double.parseDouble(secondToken);
268                                } catch (Exception e) {
269                                        eoh = true;
270                                }
271                                if (!eoh) {
272
273                                        java.awt.geom.Point2D.Double pt2D = new java.awt.geom.Point2D.Double(
274                                                        xval, yval);
275                                        pts.addElement(pt2D);
276                                }
277                        }
278                }
279                return pts;
280        }
281
282        private Point2D findFirstPoint(Vector pts) {
283                double minx;
284                Point2D fp = (Point2D) pts.elementAt(0);
285                minx = fp.getX();
286                for (int i = 1; i < pts.size(); i++) {
287                        double tempx = ((Point2D) pts.elementAt(i)).getX();
288                        // System.out.println("i: "+i+"    tempx: "+tempx+
289                        // "    minx: "+minx);
290                        if (tempx < minx) {
291                                fp = (Point2D) pts.elementAt(i);
292                                minx = tempx;
293                        }
294                }
295                // System.out.println("MinX: "+fp.getX()+"   MinY: "+fp.getY());
296                return fp;
297        }
298}