Convex Hull For User-Drawn Circle

Question

I'm working on a game in which I must find the convex hull for a set of points. I'm trying to choose the right algorithm. The sets of points are user-drawn shapes, so there is an order to them. Ideally, the user draws an ellipse, but they can draw anything as long as it is a single stroke. Some examples are below:

I want to find the convex hull of these shapes. All the convex hull algorithms I have found assume a random, orderless set of points. Which algorithm would be best for my particular situation, when the user has drawn the points by clicking and dragging the mouse, so the points are in order.

Notes:

In particular, many are output-sensitive algorithms. O(n log h) where n is the number of points in the set of all points, the original, and h is the set of points in the convex hull. With these shapes, I expect the h ~= n, because they are basically outlines in and of themselves.

Finally, the whole goal of this is to find the least-area rectangle of the points, such as this:

Can anyone think of a better way to find the rectangle other than first finding the convex hull? After research, this seems to be the best way, but my special case might be different.

Thank you in advance!

Answer 1

Stay away for the O(N Log H) algorithms. They are difficult and slow !

Using O(N Log N) ones is a much better option. I recommend the monotone chain approach, both easy and fast.

You shouldn't be worried by the complexity order O(N Log N), which is only due to the sorting phase. The extra Log N / Log H factor is not so catastrophic (and inexistent for a convex point set), while the asymptotic constant for a sort is very good.

If you are after maximum efficieny, the particular arrangement of your points suggests an alternative approach: the points will form long increasing (decreasing) sequences, which you can easily detect and sort by merging steps. The complexity will drop to O(N Log K) where K is the number of monotone sequences hence virtually O(N) (this is called Natural Merge Sort).

You are not very far from the use case of Melkman's O(N) algorithm, which can be used for the hull of a simple polygon. Unfortunately, the simplicity condition might fail near the closing of the curve, and I see no simple way to fix that.

---

For the bounding rectangle, the Rotating Calipers are definitely your best friends.