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.

Answer 2

To find the smallest enclosing rectangle aligned in a particular direction, you need to know the extreme points in that direction and in the orthogonal direction, and the convex hull encodes this information in a particularly convenient way for e.g., rotating calipers. If you're willing to approximate, you could just try directions every five degrees (or whatever), with a running time of O(nd) where d is the number of directions. This works well with SIMD support if you have it.

Answer 3

I am just wondering what would happen if you apply the following approach:

Think of your polygon as a 2 x N matrix

P = [x1, x2, ..., xN;
     y1, y2, ..., yN]; 

where each column contains the x and y coordinate of a vertex of the polygon. Then, for any angle phi between say 0 and pi/2 define the rotation matrix

U(phi) = [cos(phi) -sin(phi);
          sin(phi)  cos(phi)];

After that, rotate the polygon to angle phi by multiplying the matrices

P_phi = U(phi)*P;

Then the function

f(phi) = ( max( P_phi[1][] ) - min( P_phi[1][] ) )*( max( P_phi[2][] ) - min( P_phi[2][] ) )

is the area of the rectangle with horizontal and vertical edges, superscribed around the rotated polygon P(phi). Here P_phi[1][] is the first row of x coordinates of the matrix P_phi and P_phi[2][] is the second row of y coordinates. Consequently, you want to find the angle phi and the vertices, collected in the 2 x 4 matrix R_phi, of the axes-aligned rectangle which gives the minimum of the function f(phi) for phi in [0, pi/2]because that is the area of the smallest-area rectangle superscribed around your polygon. After you find phi and R_phi just rotate back as follows R = U(-phi)*R_phi and this is the rectangle you are looking for.

I am not sure whether this suggestion works...