1 package org.djutils.draw.line;
2
3 import java.util.ArrayList;
4 import java.util.Collection;
5 import java.util.Collections;
6 import java.util.Comparator;
7 import java.util.Iterator;
8 import java.util.List;
9
10 import org.djutils.draw.Drawable2d;
11 import org.djutils.draw.bounds.Bounds2d;
12 import org.djutils.draw.point.Point2d;
13 import org.djutils.exceptions.Throw;
14
15
16
17
18
19
20
21
22
23
24
25
26
27 public final class ConvexHull
28 {
29
30
31
32 private ConvexHull()
33 {
34
35 }
36
37
38
39
40
41
42 public static Polygon2d convexHull(final Iterator<Point2d> iterator)
43 {
44 List<Point2d> list = new ArrayList<>();
45 iterator.forEachRemaining(list::add);
46 return convexHullAlshamrani(list);
47 }
48
49
50
51
52
53
54
55
56 public static Polygon2d convexHull(final Drawable2d... drawable2d)
57 {
58 return convexHull(Bounds2d.pointsOf(drawable2d));
59 }
60
61
62
63
64
65
66
67
68
69 public static Polygon2d convexHull(final Collection<Drawable2d> drawableCollection)
70 {
71 Throw.whenNull(drawableCollection, "drawableCollection");
72 Throw.when(drawableCollection.isEmpty(), IllegalArgumentException.class, "drawableCollection may not be empty");
73 return convexHull(Bounds2d.pointsOf(drawableCollection));
74 }
75
76
77
78
79
80
81 public static Polygon2d convexHull(final List<Point2d> list)
82 {
83 return convexHullAlshamrani(list);
84 }
85
86
87
88
89
90
91
92
93
94 private static boolean ccw(final Point2d a, final Point2d b, final Point2d c)
95 {
96 return ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x));
97 }
98
99
100
101
102
103
104
105 private static void cleanAndAppend(final List<Point2d> list, final Point2d newPoint)
106 {
107 Point2d last = list.get(list.size() - 1);
108 if (last.x == newPoint.x && last.y == newPoint.y)
109 {
110 return;
111 }
112 while (list.size() >= 2 && !ccw(list.get(list.size() - 2), list.get(list.size() - 1), newPoint))
113 {
114 list.remove(list.size() - 1);
115 }
116 list.add(newPoint);
117 }
118
119
120
121
122
123
124
125
126
127
128 public static Polygon2d convexHullAlshamrani(final List<Point2d> list)
129 {
130
131 Throw.whenNull(list, "list");
132 Throw.when(list.size() < 1, IllegalArgumentException.class, "Too few points in list");
133 Point2d minX = list.get(0);
134 Point2d minY = list.get(0);
135 Point2d maxX = list.get(0);
136 Point2d maxY = list.get(0);
137 for (Point2d point : list)
138 {
139 if (minX.x > point.x || minX.x == point.x && minX.y > point.y)
140 {
141 minX = point;
142 }
143 if (minY.y > point.y || minY.y == point.y && minY.x < point.x)
144 {
145 minY = point;
146 }
147 if (maxX.x < point.x || maxX.x == point.x && maxX.y > point.y)
148 {
149 maxX = point;
150 }
151 if (maxY.y < point.y || maxY.y == point.y && maxY.x < point.x)
152 {
153 maxY = point;
154 }
155 }
156
157
158
159
160 Comparator<Point2d> forwardComparator = new Comparator<Point2d>()
161 {
162 @Override
163 public int compare(final Point2d point1, final Point2d point2)
164 {
165 if (point1.x == point2.x)
166 {
167 return (int) Math.signum(point1.y - point2.y);
168 }
169 return (int) Math.signum(point1.x - point2.x);
170 }
171 };
172 Comparator<Point2d> reverseComparator = new Comparator<Point2d>()
173 {
174 @Override
175 public int compare(final Point2d point1, final Point2d point2)
176 {
177 if (point1.x == point2.x)
178 {
179 return (int) Math.signum(point1.y - point2.y);
180 }
181 return (int) Math.signum(point2.x - point1.x);
182 }
183 };
184 List<Point2d> lowerLeft = new ArrayList<>();
185 List<Point2d> lowerRight = new ArrayList<>();
186 List<Point2d> upperRight = new ArrayList<>();
187 List<Point2d> upperLeft = new ArrayList<>();
188
189 for (Point2d point : list)
190 {
191 if (point.x <= minY.x && point.y <= minX.y)
192 {
193 if (ccw(minX, point, minY))
194 {
195 lowerLeft.add(point);
196 }
197 }
198 else if (point.x >= minY.x && point.y <= maxX.y)
199 {
200 if (ccw(minY, point, maxX))
201 {
202 lowerRight.add(point);
203 }
204 }
205 else if (point.x >= maxY.x && point.y >= maxX.y)
206 {
207 if (ccw(maxX, point, maxY))
208 {
209 upperRight.add(point);
210 }
211 }
212 else if (point.x <= maxY.x && point.y >= minX.y)
213 {
214 if (ccw(maxY, point, minX))
215 {
216 upperLeft.add(point);
217 }
218 }
219 }
220 Collections.sort(lowerLeft, forwardComparator);
221 Collections.sort(lowerRight, forwardComparator);
222 Collections.sort(upperRight, reverseComparator);
223 Collections.sort(upperLeft, reverseComparator);
224
225 List<Point2d> result = new ArrayList<>();
226 result.add(minX);
227 for (Point2d point : lowerLeft)
228 {
229 cleanAndAppend(result, point);
230 }
231 cleanAndAppend(result, minY);
232 for (Point2d point : lowerRight)
233 {
234 cleanAndAppend(result, point);
235 }
236 cleanAndAppend(result, maxX);
237 for (Point2d point : upperRight)
238 {
239 cleanAndAppend(result, point);
240 }
241 cleanAndAppend(result, maxY);
242 for (Point2d point : upperLeft)
243 {
244 cleanAndAppend(result, point);
245 }
246 return new Polygon2d(result);
247 }
248
249
250
251
252
253
254
255
256
257 public static Polygon2d convexHullMonotone(final List<Point2d> list)
258 {
259 Collections.sort(list, new Comparator<Point2d>()
260 {
261 @Override
262 public int compare(final Point2d point1, final Point2d point2)
263 {
264 if (point1.x == point2.x)
265 {
266 return (int) Math.signum(point1.y - point2.y);
267 }
268 return (int) Math.signum(point1.x - point2.x);
269 }
270 });
271
272 List<Point2d> result = new ArrayList<>();
273
274 for (Point2d p : list)
275 {
276 while (result.size() >= 2 && !ccw(result.get(result.size() - 2), result.get(result.size() - 1), p))
277 {
278 result.remove(result.size() - 1);
279 }
280 result.add(p);
281 }
282
283 int lowLimit = result.size() + 1;
284 for (int i = list.size() - 1; i >= 0; i--)
285 {
286 Point2d p = list.get(i);
287 while (result.size() >= lowLimit && !ccw(result.get(result.size() - 2), result.get(result.size() - 1), p))
288 {
289 result.remove(result.size() - 1);
290 }
291 result.add(p);
292 }
293 if (result.size() > 0)
294 {
295 result.remove(result.size() - 1);
296 }
297
298 return new Polygon2d(result);
299 }
300
301 }