Calculating Convex Hull from Multiple Collection of Points

Question

I have a collection of Polygons (think cycles if you like graph theory), and I want to find the convex hull of the whole feature collection, not each individual feature/polygon. I was thinking of using monotone chaining, which gives me O(n log n) time for a single set of points, but since I can have 0 to n collections of points, is there a better way to do this to achieve fast processing time?

Thanks

Answer 1

If your polygons are convex, consider using of rotating calipers.

One of their applications is building of common convex hull for two convex polygons (repeat convex hull merging for more and more polygons) (chapter 5, chapter 2.6)