3

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:

Before and After States

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:

Fault in Naive approach

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?

ipmcc
  • 235
  • 1
  • 6

4 Answers4

1

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.

projection

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • How is the choice in the fourth image "the minimum"? Is it in that it's the "most negative"? Or perhaps more generally, what is the criteria for that choice? And how did you choose which edge to project onto? Or do you project onto all of them? – ipmcc Aug 06 '13 at 16:46
  • @ipmcc The minimum of signed distances, "most negative" could be a description. How I choose which edge to project onto: you "shoot" a ray and look for where it hits (knowing if you start inside $H_2$ or outside might help). – dtldarek Aug 06 '13 at 17:29
0

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?

Emily
  • 35,688
  • 6
  • 93
  • 141
  • "When the shapes overlap, then one or more of the vectors in Sk is inside the convex hull of Sj." This is not true; Consider two rectangles that form a cross; No vertex of one is contained within the other, yet they overlap. – ipmcc Aug 06 '13 at 15:14
  • @ipmcc That's true. I guess I was just looking at your examples. – Emily Aug 06 '13 at 15:20
0

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.

Mark Ping
  • 401
  • 3
  • 8
  • It would seem that this suffers from the exact problem I pointed out in my second image. Am I missing something? – ipmcc Aug 06 '13 at 16:37
  • The overlap is computed along the sweep line, not on the whole object. By maintaining all edges that cross the line, you can do this efficiently. It's essentially a simplified polygon intersection test only at the sweep points (corners and intersections). – Mark Ping Aug 06 '13 at 18:18
0

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)

lhf
  • 216,483