View Javadoc
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   * ConvexHull.java. Compute the convex hull of a collection of Point2d or Drawable2d. All implementations here return a
17   * Polygon2d object. If the convex hull of the input would be a single point, the implementations will throw a
18   * DrawRuntimeException because a single point does not make a valid Polygon2d.
19   * <p>
20   * Copyright (c) 2020-2025 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
21   * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
22   * </p>
23   * @author <a href="https://www.tudelft.nl/averbraeck">Alexander Verbraeck</a>
24   * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
25   * @author <a href="https://github.com/wjschakel">Wouter Schakel</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 that shall return all the points for which the convex hull is to be computed
40       * @return the convex hull of the points
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       * Compute the convex hull of one or more Drawable2d objects.
51       * @param drawable2d the Drawable2d objects
52       * @return the convex hull of the Drawable2d objects
53       * @throws NullPointerException when any of the drawable2d object is <code>null</code>
54       * @throws IllegalArgumentException when zero arguments are provided
55       */
56      public static Polygon2d convexHull(final Drawable2d... drawable2d)
57      {
58          return convexHull(Bounds2d.pointsOf(drawable2d));
59      }
60  
61      /**
62       * Construct a Bounds2d for a Collection of Drawable2d objects.
63       * @param drawableCollection the collection
64       * @return the convex hull of the Drawable2d objects
65       * @throws NullPointerException when the <code>drawableCollection</code> is <code>null</code>, or contains a
66       *             <code>null</code> value
67       * @throws IllegalArgumentException when the <code>drawableCollection</code> is empty
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       * Compute the convex hull of a list of Point2d objects. The input list will not be modified.
78       * @param list the list of Point2d objects
79       * @return the convex hull of the points
80       */
81      public static Polygon2d convexHull(final List<Point2d> list)
82      {
83          return convexHullAlshamrani(list);
84      }
85  
86      /**
87       * Return whether moving from a through b to c, the turn at b is counter-clockwise.
88       * @param a point a
89       * @param b point b
90       * @param c point c
91       * @return <code>true</code> if the turn at b is counter clockwise; <code>false</code> if there is not turn; or it is
92       *         clockwise
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      * Repeatedly remove the last point if not counter clockwise with new point; then add the new point. If the new point is
101      * equal to the last point in the list; do nothing.
102      * @param list the list of points
103      * @param newPoint the point that will be added.
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      * Implementation of the convex hull algorithm by Reham Alshamrani c.s.; see
121      * <a href="https://www.sciencedirect.com/science/article/pii/S1877050920304750">A Preprocessing Technique for Fast Convex
122      * Hull Computation</a>.
123      * @param list list of the points (will not be modified)
124      * @return the convex hull of the points
125      * @throws NullPointerException when the <code>list</code> is <code>null</code>
126      * @throws IllegalArgumentException when the <code>list</code> contains too few points
127      */
128     public static Polygon2d convexHullAlshamrani(final List<Point2d> list)
129     {
130         // Find the four extreme points
131         Throw.whenNull(list, "list");
132         Throw.when(list.size() < 1, IllegalArgumentException.class, "Too few points in list");
133         Point2d minX = list.get(0); // Initialize to the first point in list to avoid checking for null on each iteration
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         // Filter and group the points into priority queues that order by x value (tie breaker is y value)
157         // Alshamrani does not show how he tests that a point is outside each edge of the four extreme points. We use ccw.
158         // Alshamrani poorly documents the ordering method for the four queues when the primary component values are the same.
159         // Testing has shown that sorting a filled ArrayList is faster than putting the same elements one by one in a TreeSet.
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         // Construct the convex hull
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      * Implementation of Andrew's Monotone Chain convex hull algorithm. This implementation (sorts) modifies the provided list
251      * of points!
252      * @param list list of the points (will be modified)
253      * @return the convex hull of the points
254      * @throws NullPointerException when the <code>list</code> is <code>null</code>
255      * @throws IllegalArgumentException when the <code>list</code> contains too few points
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         // That sort operation was O(N log (N)); the remainder is O(N)
272         List<Point2d> result = new ArrayList<>();
273         // Lower hull
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         // Upper hull
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         // else; zero points; the constructor of the Polygon2d will throw an IllegalArgumentException
298         return new Polygon2d(result);
299     }
300 
301 }