CODEWITHSUNDEEP
pythonpandasgeometryconvex-hull
code base 5000
code base 5000

Reputation: 4102

Calculating Convex Hull from Multiple Collection of Points

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

Upvotes: 1

Views: 1721

Answers (2)

Eric Ouellet
Eric Ouellet

Reputation: 11754

There is 2 ways to acheive what you want to do:

First way Use an "online" convex hull algorithm. "Online" means (dynamic add) which enable you to add points one by one. I have done an algorithm in O(log h) per point which is accessible in GitHub. It is actually the fastest aglorithm. It is based on Ouellet Convex hull. The project is OuelletConvexHullAvl2Online. In your case you loop over each of your polygons and for each of them, you loop on each of their points feeding the online algorithm.

Sample usage:

OuelletConvexHullAvl2Online.ConvexHullOnline convexHullOnline = new OuelletConvexHullAvl2Online.ConvexHullOnline();
                foreach (Point pt in points)
                {
                    convexHullOnline.DynamicallyAddAnotherPointToConvexHullIfAppropriate(pt);
                }

                return convexHullOnline.GetResultsAsArrayOfPoint();

The second way Use a "Composite" design pattern to wrap your Polygons as it would be a single instance of a vector of point (an IEnumerable or points). Then you feed any regular algorithm with the composite object. The composite will do the hard work of supplying each and every node of all your polygons as if they were a single object (kind of an array of point). By the way I do use composite in my algorithm in class OuelletConvexHullAvl2Online:ConvexHullEnumerator which would enumerate the resulting convex hull points contained in the 4 quadrant (AVL tree).

Upvotes: 0

MBo
MBo

Reputation: 80187

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)

Upvotes: 2

Related Questions