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.DrawRuntimeException;
11 import org.djutils.draw.Drawable2d;
12 import org.djutils.draw.bounds.Bounds2d;
13 import org.djutils.draw.point.Point2d;
14 import org.djutils.exceptions.Throw;
15
16 /**
17 * ConvexHull.java. Compute the convex hull of a collection of Point2d or Drawable2d. All implementations here return a
18 * Polygon2d object. If the convex hull of the input would be a single point, the implementations will throw a
19 * DrawRuntimeException because a single point does not make a valid Polygon2d.
20 * <p>
21 * Copyright (c) 2020-2021 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
22 * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
23 * </p>
24 * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
25 * @author <a href="https://www.tudelft.nl/pknoppers">Peter Knoppers</a>
26 */
27 public final class ConvexHull
28 {
29 /**
30 * Do not instantiate.
31 */
32 private ConvexHull()
33 {
34 // Do not instantiate
35 }
36
37 /**
38 * Compute the convex hull of a collection of Point2d objects.
39 * @param iterator Iterator<Point2d>; iterator that shall return all the points for which the convex hull is to be
40 * computed
41 * @return Polygon2d; the convex hull of the points
42 */
43 public static Polygon2d convexHull(final Iterator<Point2d> iterator)
44 {
45 List<Point2d> list = new ArrayList<>();
46 iterator.forEachRemaining(list::add);
47 return convexHullAlshamrani(list);
48 }
49
50 /**
51 * Compute the convex hull of one or more Drawable2d objects.
52 * @param drawable2d Drawable2d...; the Drawable2d objects
53 * @return Polygon2d; the convex hull of the Drawable2d objects
54 * @throws NullPointerException when any of the drawable2d object is null
55 * @throws IllegalArgumentException when zero arguments are provided
56 */
57 public static Polygon2d convexHull(final Drawable2d... drawable2d) throws NullPointerException, IllegalArgumentException
58 {
59 return convexHull(Bounds2d.pointsOf(drawable2d));
60 }
61
62 /**
63 * Construct a Bounds2d for a Collection of Drawable2d objects.
64 * @param drawableCollection Collection<Drawable2d>; the collection
65 * @return Polygon2d; the convex hull of the Drawable2d objects
66 * @throws NullPointerException when the collection is null, or contains null values
67 * @throws IllegalArgumentException when the collection is empty
68 */
69 public static Polygon2d convexHull(final Collection<Drawable2d> drawableCollection)
70 throws NullPointerException, IllegalArgumentException
71 {
72 Throw.whenNull(drawableCollection, "drawableCollection may not be null");
73 Throw.when(drawableCollection.isEmpty(), DrawRuntimeException.class, "drawableCollection may not be empty");
74 return convexHull(Bounds2d.pointsOf(drawableCollection));
75 }
76
77 /**
78 * Compute the convex hull of a list of Point2d objects. The input list will not be modified.
79 * @param list List<Point2d>; the list of Point2d objects
80 * @return Polygon2d; the convex hull of the points
81 */
82 public static Polygon2d convexHull(final List<Point2d> list)
83 {
84 return convexHullAlshamrani(list);
85 }
86
87 /**
88 * Return whether moving from a through b to c, the turn at b is counter-clockwise.
89 * @param a Point2d; point a
90 * @param b Point2d; point b
91 * @param c Point2d; point c
92 * @return boolean; true if the turn at b is counter clockwise; false if there is not turn; or it is clockwise
93 */
94 private static boolean ccw(final Point2dint2d.html#Point2d">Point2dint2d.html#Point2d">Point2d a, final Point2dint2d.html#Point2d">Point2d b, final Point2d c)
95 {
96 // System.out.println("left " + ((b.x - a.x) * (c.y - a.y)) + ", right " + ((b.y - a.y) * (c.x - a.x)));
97 return ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x));
98 }
99
100 /**
101 * Repeatedly remove the last point if not counter clockwise with new point; then add the new point. If the new point is
102 * equal to the last point in the list; do nothing.
103 * @param list List<Point2d>; the list of points
104 * @param newPoint Point2d; the point that will be added.
105 */
106 private static void cleanAndAppend(final List<Point2d> list, final Point2d newPoint)
107 {
108 Point2d last = list.get(list.size() - 1);
109 if (last.x == newPoint.x && last.y == newPoint.y)
110 {
111 return;
112 }
113 while (list.size() >= 2 && !ccw(list.get(list.size() - 2), list.get(list.size() - 1), newPoint))
114 {
115 list.remove(list.size() - 1);
116 }
117 list.add(newPoint);
118 }
119
120 /**
121 * Implementation of the convex hull algorithm by Reham Alshamrani c.s.; see
122 * <a href="https://www.sciencedirect.com/science/article/pii/S1877050920304750">A Preprocessing Technique for Fast Convex
123 * Hull Computation</a>.
124 * @param list List<Point2d>; list of the points (will not be modified)
125 * @return Polygon2d; the convex hull of the points
126 * @throws NullPointerException when the list is null
127 * @throws DrawRuntimeException when the list contains too few points
128 */
129 public static Polygon2d convexHullAlshamrani(final List<Point2d> list) throws NullPointerException, DrawRuntimeException
130 {
131 // Find the four extreme points
132 Throw.whenNull(list, "list may not be null");
133 Throw.when(list.size() < 1, DrawRuntimeException.class, "Too few points in list");
134 Point2d minX = list.get(0); // Initialize to the first point in list to avoid checking for null on each iteration
135 Point2d minY = list.get(0);
136 Point2d maxX = list.get(0);
137 Point2d maxY = list.get(0);
138 for (Point2d point : list)
139 {
140 if (minX.x > point.x || minX.x == point.x && minX.y > point.y)
141 {
142 minX = point;
143 }
144 if (minY.y > point.y || minY.y == point.y && minY.x < point.x)
145 {
146 minY = point;
147 }
148 if (maxX.x < point.x || maxX.x == point.x && maxX.y > point.y)
149 {
150 maxX = point;
151 }
152 if (maxY.y < point.y || maxY.y == point.y && maxY.x < point.x)
153 {
154 maxY = point;
155 }
156 }
157 // Filter and group the points into priority queues that order by x value (tie breaker is y value)
158 // Alshamrani does not show how he tests that a point is outside each edge of the four extreme points. We use ccw.
159 // Alshamrani poorly documents the ordering method for the four queues when the primary component values are the same.
160 // Testing has shown that sorting a filled ArrayList is faster than putting the same elements one by one in a TreeSet.
161 Comparator<Point2d> forwardComparator = new Comparator<Point2d>()
162 {
163 @Override
164 public int compare(final Point2d.html#Point2d">Point2d point1, final Point2d point2)
165 {
166 if (point1.x == point2.x)
167 {
168 return (int) Math.signum(point1.y - point2.y);
169 }
170 return (int) Math.signum(point1.x - point2.x);
171 }
172 };
173 Comparator<Point2d> reverseComparator = new Comparator<Point2d>()
174 {
175 @Override
176 public int compare(final Point2d.html#Point2d">Point2d point1, final Point2d point2)
177 {
178 if (point1.x == point2.x)
179 {
180 return (int) Math.signum(point1.y - point2.y);
181 }
182 return (int) Math.signum(point2.x - point1.x);
183 }
184 };
185 List<Point2d> lowerLeft = new ArrayList<>();
186 List<Point2d> lowerRight = new ArrayList<>();
187 List<Point2d> upperRight = new ArrayList<>();
188 List<Point2d> upperLeft = new ArrayList<>();
189
190 for (Point2d point : list)
191 {
192 if (point.x <= minY.x && point.y <= minX.y)
193 {
194 if (ccw(minX, point, minY))
195 {
196 lowerLeft.add(point);
197 }
198 }
199 else if (point.x >= minY.x && point.y <= maxX.y)
200 {
201 if (ccw(minY, point, maxX))
202 {
203 lowerRight.add(point);
204 }
205 }
206 else if (point.x >= maxY.x && point.y >= maxX.y)
207 {
208 if (ccw(maxX, point, maxY))
209 {
210 upperRight.add(point);
211 }
212 }
213 else if (point.x <= maxY.x && point.y >= minX.y)
214 {
215 if (ccw(maxY, point, minX))
216 {
217 upperLeft.add(point);
218 }
219 }
220 }
221 // System.out.println(String.format("minX %s, minY %s, maxX %s, maxY %s", minX, minY, maxX, maxY));
222 // System.out.println(String.format("total: %d, ll: %d (%.0f%%), lr: %d (%.0f%%), ur: %d (%.0f%%), ul: %d (%.0f%%)",
223 // list.size(), lowerLeft.size(), 100.0 * lowerLeft.size() / list.size(), lowerRight.size(),
224 // 100.0 * lowerRight.size() / list.size(), upperRight.size(), 100.0 * upperRight.size() / list.size(),
225 // upperLeft.size(), 100.0 * upperLeft.size() / list.size()));
226 Collections.sort(lowerLeft, forwardComparator);
227 Collections.sort(lowerRight, forwardComparator);
228 Collections.sort(upperRight, reverseComparator);
229 Collections.sort(upperLeft, reverseComparator);
230 // Construct the convex hull
231 List<Point2d> result = new ArrayList<>();
232 result.add(minX);
233 for (Point2d point : lowerLeft)
234 {
235 cleanAndAppend(result, point);
236 }
237 cleanAndAppend(result, minY);
238 for (Point2d point : lowerRight)
239 {
240 cleanAndAppend(result, point);
241 }
242 cleanAndAppend(result, maxX);
243 for (Point2d point : upperRight)
244 {
245 cleanAndAppend(result, point);
246 }
247 cleanAndAppend(result, maxY);
248 for (Point2d point : upperLeft)
249 {
250 cleanAndAppend(result, point);
251 }
252 return new Polygon2d(result);
253 }
254
255 /**
256 * Implementation of Andrew's Monotone Chain convex hull algorithm. This implementation (sorts) modifies the provided list
257 * of points!
258 * @param list List<Point2d>; list of the points (will be modified)
259 * @return Polygon2d; the convex hull of the points
260 * @throws NullPointerException when the list is null
261 * @throws DrawRuntimeException when the list contains too few points
262 */
263 public static Polygon2d convexHullMonotone(final List<Point2d> list) throws NullPointerException, DrawRuntimeException
264 {
265 Collections.sort(list, new Comparator<Point2d>()
266 {
267 @Override
268 public int compare(final Point2d.html#Point2d">Point2d point1, final Point2d point2)
269 {
270 if (point1.x == point2.x)
271 {
272 return (int) Math.signum(point1.y - point2.y);
273 }
274 return (int) Math.signum(point1.x - point2.x);
275 }
276 });
277 // That sort operation was O(N log (N)); the remainder is O(N)
278 List<Point2d> result = new ArrayList<>();
279 // Lower hull
280 for (Point2d p : list)
281 {
282 while (result.size() >= 2 && !ccw(result.get(result.size() - 2), result.get(result.size() - 1), p))
283 {
284 result.remove(result.size() - 1);
285 }
286 result.add(p);
287 }
288 // Upper hull
289 int lowLimit = result.size() + 1;
290 for (int i = list.size() - 1; i >= 0; i--)
291 {
292 Point2d p = list.get(i);
293 while (result.size() >= lowLimit && !ccw(result.get(result.size() - 2), result.get(result.size() - 1), p))
294 {
295 result.remove(result.size() - 1);
296 }
297 result.add(p);
298 }
299 if (result.size() > 0)
300 {
301 result.remove(result.size() - 1);
302 }
303 // else; zero points; the constructor of the Polygon2d will throw a DrawRuntimeException
304 return new Polygon2d(result);
305 }
306
307 }