View Javadoc

1   /**
2    * 
3    */
4   
5   package math.geom2d.polygon.convhull;
6   
7   import java.util.ArrayList;
8   import java.util.Collection;
9   
10  import math.geom2d.Angle2D;
11  import math.geom2d.Point2D;
12  import math.geom2d.polygon.Polygon2D;
13  import math.geom2d.polygon.SimplePolygon2D;
14  
15  /**
16   * Computes the convex hull of a set of points as a single Polygon2D.
17   * 
18   * @author dlegland
19   */
20  public class JarvisMarch2D implements ConvexHull2D {
21  
22      /**
23       * Creates a new Convex hull calculator.
24       */
25      public JarvisMarch2D(){
26      }
27      
28      /**
29       * Computes the convex hull of a set of points as a single Polygon2D.
30       * Current implementation start at the point with lowest y-coord. The points
31       * are considered in counter-clockwise order. Result is an instance of
32       * SimplePolygon2D. Complexity is O(n*h), with n number of points, h number
33       * of points of the hull. Worst case complexity is O(n^2).
34       */
35      public Polygon2D convexHull(Collection<? extends Point2D> points) {
36          // Init iteration on points
37          Point2D lowestPoint = null;
38          double y;
39          double ymin = Double.MAX_VALUE;
40  
41          // Iteration on the set of points to find point with lowest y-coord
42          for (Point2D point : points) {
43              y = point.getY();
44              if (y<ymin) {
45                  ymin = y;
46                  lowestPoint = point;
47              }
48          }
49  
50          // initialize array of points located on convex hull
51          ArrayList<Point2D> hullPoints = new ArrayList<Point2D>();
52  
53          // Init iteration on points
54          Point2D currentPoint = lowestPoint;
55          Point2D nextPoint = null;
56          double angle = 0;
57  
58          // Iterate on point set to find point with smallest angle with respect
59          // to previous line
60          do {
61              hullPoints.add(currentPoint);
62              nextPoint = findNextPoint(currentPoint, angle, points);
63              angle = Angle2D.getHorizontalAngle(currentPoint, nextPoint);
64              currentPoint = nextPoint;
65          } while (currentPoint!=lowestPoint);
66  
67          // Create a polygon with points located on the convex hull
68          SimplePolygon2D convexHull = new SimplePolygon2D(hullPoints);
69          return convexHull;
70      }
71  
72      private Point2D findNextPoint(Point2D basePoint, double startAngle,
73              Collection<? extends Point2D> points) {
74          Point2D minPoint = null;
75          double minAngle = Double.MAX_VALUE;
76          double angle;
77  
78          for (Point2D point : points) {
79              // Avoid to test same point
80              if (basePoint.equals(point))
81                  continue;
82  
83              // Compute angle between current direction and next point
84              angle = Angle2D.getHorizontalAngle(basePoint, point);
85              angle = Angle2D.formatAngle(angle-startAngle);
86  
87              // Keep current point if angle is minimal
88              if (angle<minAngle) {
89                  minAngle = angle;
90                  minPoint = point;
91              }
92          }
93  
94          return minPoint;
95      }
96  }