What's the most efficient way to find the convex hull of the union of two convex polygons?

Question

Given two convex polygons P and Q in the (x, y) plane, respectively having vertex sets {p₁, ..., p_a} and {q₁, ..., q_b} given in clockwise order (p₁ is the furthest west of the furthest-north vertices of P; q₁ is the furthest west of the furthest-north vertices of Q), I want to find R, the convex hull of the union of P and Q. This is another convex polygon, with at most a + b vertices. I want to get it in the same form, i.e. a sequence of vertices {r₁, ..., r_c} given in clockwise order with r₁ the furthest-west of the furthest-north vertices. What's the most efficient way to do this?

It is not known at the outset whether or not P and Q intersect.

Answer 1

There is powerful method called Rotating Calipers.

Using them, one can make union of two convex hulls in linear time.

Sadly, nice page with a lot of explanations has been deleted (http://cgm.cs.mcgill.ca/~orm/rotcal.html, there is no copy in web archive either).

In general, you choose the leftmost point from your p1 and q1 as start, then walk through vertices of both polygons in parallel order (like merge step in mergesort), choosing the most "clockwise" one at every step. When edge of new convex hull changes from P to Q vertices or vice versa, it is called "bridge" (qj-pi at the picture)

Very short description, perhaps you are lucky to find better one.

Answer 2

It would be inappropriate for me to post the actual code I've written to solve this problem, but I'll post pseudocode instead. I believe this accomplishes the task in linear time, but I have not proven it; I lack either the mathematical sophistication or the motivation to do so. If it is correct and linear-time, it might be formally equivalent to the "rotating calipers" method referred to by MBo.

Note: This might go into a loop if the polygons fail to satisfy my hypotheses. You can detect this by (1) checking at the "find horizon" loop if it's looping too many times, and (2) counting the vertices produced and checking at each produced vertex whether more vertices have been produced than ought to be possible.

Note (2): All indices wrap around; p_{a + 1} is by definition another name for p₁, and p₀ is by definition another name for p_a.

Note (3): We may assume without loss of generality that p₁ is either due west, or anywhere north of q₁ (or they are the same point).

let start_point be p[1]
let current_index be 1
let horizon_index be 1
while true:
    let c  = p[current_index]
    let c' = p[current_index + 1]
    let h  = q[horizon_index]
    yield c
    -- Update the horizon on the other polygon.
    while true:
        let T1 = triangle(c, h, q[horizon_index - 1])
        let T2 = triangle(c, h, q[horizon_index + 1])
        let cond1 = "T1 is clockwise or degenerate"
        let cond2 = "T2 is clockwise"
        if cond1 and cond2:
            -- Found the correct horizon.
            break
        increment horizon_index
    let T = triangle(c, h, c')
    let horizon_further be "from c, the horizon is further away than c'"
    let should_bridge = case
        when T is anticlockwise then false
        when T is clockwise then true
        when T is degenerate then horizon_further
    end case
    increment current_index
    if should_bridge:
        swap p and q
        swap current_index and horizon_index
    if p[current_index] is equal to start_point:
        break