How do I calculate how far to translate a convex hull (along a given axis) to avoid collision with another convex hull I'm trying to come up with a method, given two convex hulls A & B, which overlap, to determine how far along a given axis vector (in a given direction) that I would have to translate B in order to avoid intersection with A. Consider the following two examples, presented visually:

The goal is to determine d. I started my investigation thinking of the Separating Axis Theorem, and initially projected the two hulls onto the given axis and calculated the d necessary to prevent overlap on that axis, but that fails to find the minimum distance for cases like this: 

I'm starting to think that I want to be more like the SAT and project along the axes parallel to each face of the hulls, but it's not coming together in my head. Can anyone help me break this mental logjam?
 A: Hint:


*

*Let $H_1$ and $H_2$ be two convex hulls.

*Project points of $H_1$ onto $H_2$ along the given direction (some might "fall" to infinity).

*Calculate the signed distances between the points and their projections (the direction gives you the sign).

*Pick the minimum.



I hope this helps $\ddot\smile$
A: Maybe let's start with the definition of convexity.
Each of your shapes is some set of vectors $S_k = \{ v_1, v_2, \ldots, v_n\}, v_i \in \mathbb{R}^2$. Each of these vectors defines a vertex of the shape.
When the shapes overlap, then one or more of the vectors in $S_k$ is inside the convex hull of $S_j$.
Denote the "overlapped" vertex of $S_k$ by $v^{(k)}_i$. By convexity, then
$$v_i^{(k)} = \sum_{l=1}^{n_j } \alpha_l v_l^{(j)}, \sum_l \alpha_l = 1, \alpha_l \ge 0.$$
You want to find the smallest $\Delta v$ such that no set of coefficients $\{\alpha\}$ satisify the convexity requirement, or at least such that it is exactly satisfied for the vertex.
This probably requires a linear programming solution, but perhaps it points you in the right direction?
A: I'd tackle this using a sweep line algorithm.  Sweeping bottom to top, computing right-most overlap of left poly and left-most overlap of right poly.  Since both are convex, they have defined 'left' and 'right' sides that are easily determined.
At each edge endpoint and intersection, compute left-most and right-most overlap. (This assumes you transform the polys into the space so the axis is horizontal.)
Here's one introduction to the sweep line approach.
A: See this paper for an algorithm that works for all simple polygons:

G. Toussaint,
  On separating two simple polygons by a single translation. 
  Discrete Comput. Geom. 4 (1989), no. 3, 265–278. MR0988749 (90g:68143) 

