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
17
18
19
20 public class JarvisMarch2D implements ConvexHull2D {
21
22
23
24
25 public JarvisMarch2D(){
26 }
27
28
29
30
31
32
33
34
35 public Polygon2D convexHull(Collection<? extends Point2D> points) {
36
37 Point2D lowestPoint = null;
38 double y;
39 double ymin = Double.MAX_VALUE;
40
41
42 for (Point2D point : points) {
43 y = point.getY();
44 if (y<ymin) {
45 ymin = y;
46 lowestPoint = point;
47 }
48 }
49
50
51 ArrayList<Point2D> hullPoints = new ArrayList<Point2D>();
52
53
54 Point2D currentPoint = lowestPoint;
55 Point2D nextPoint = null;
56 double angle = 0;
57
58
59
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
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
80 if (basePoint.equals(point))
81 continue;
82
83
84 angle = Angle2D.getHorizontalAngle(basePoint, point);
85 angle = Angle2D.formatAngle(angle-startAngle);
86
87
88 if (angle<minAngle) {
89 minAngle = angle;
90 minPoint = point;
91 }
92 }
93
94 return minPoint;
95 }
96 }