Convex hull of 4 points.

Question

I would like an algorithm to calculate the convex hull of 4 2D points. I have looked at the algorithms for the generalized problem, but I wonder if there is a simple solution for 4 points.

I've been scratching around on paper trying to figure out an algorithm but am having no luck at the moment.

Thanks.

Answer 1

You might want to look at Melkman's Algorithm.

Melkman's Convex Hull Algorithm.

Melkman's algorithm is considered to be the best convex hull algorithm for simple polygons.

Answer 2

Here's a more ad-hoc algorithm specific to 4 points:

• Find the indices of the points with minimum-X, maximum-X, minimum-Y and maximum-Y and get the unique values from this. For example, the indices may be 0,2,1,2 and the unique values will be 0,2,1.
• If there are 4 unique values, then the convex hull is made up of all the 4 points.
• If there are 3 unique values, then these 3 points are definitely in the convex hull. Check if the 4th point lies within this triangle; if not, it is also part of the convex hull.
• If there are 2 unique values, then these 2 points are on the hull. Of the other 2 points, the point that is further away from this line joining these 2 points is definitely on the hull. Do a triangle containment test to check if the other point is also in the hull.
• If there is 1 unique value, then all the 4 points are co-incident.

Some computation is required if there are 4 points to order them correctly so as to avoid getting a bow-tie shape. Hmmm.... Looks like there are enough special cases to justify using a generalized algorithm. However, you could possibly tune this to run faster than a generalized algorithm.

Answer 3

Take three of the points, and determine whether their triangle is clockwise or counterclockwise::

triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)

For a right-handed coordinate system, this value will be positive if ABC is counterclockwise, negative for clockwise, and zero if they are collinear. But, the following will work just as well for a left-handed coordinate system, as the orientation is relative.

Compute comparable values for three triangles containing the fourth point:

triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)

If all three of {ABD,BCD,CAD} have the same sign as ABC, then D is inside ABC, and the hull is triangle ABC.

If two of {ABD,BCD,CAD} have the same sign as ABC, and one has the opposite sign, then all four points are extremal, and the hull is quadrilateral ABCD.

If one of {ABD,BCD,CAD} has the same sign as ABC, and two have the opposite sign, then the convex hull is the triangle with the same sign; the remaining point is inside it.

If any of the triangle values are zero, the three points are collinear and the middle point is not extremal. If all four points are collinear, all four values should be zero, and the hull will be either a line or a point. Beware of numerical robustness problems in these cases!

For those cases where ABC is positive:

ABC  ABD  BCD  CAD  hull
------------------------
 +    +    +    +   ABC
 +    +    +    -   ABCD
 +    +    -    +   ABCD
 +    +    -    -   ABD
 +    -    +    +   ABCD
 +    -    +    -   BCD
 +    -    -    +   CAD
 +    -    -    -   [should not happen]

Answer 4

Or just use Jarvis march.