For example, if and then . The Minkowski Difference is just the Minkowski Sum where one of the sets of points is negative.
The application below demonstrates the geometry of the Minkowski Difference. The red point sets are and . The blue point set is the Minkowski Difference. The convex hull of each set of points is also shown to demonstrate the assertion made in the introduction that if the Minkowski Difference of two convex polygons contains the origin then the two polygons intersect. You can move the red vertices or the entire set of points. You can also increase or decrease the number of points in each set. Play around and try to get a feel for how this works geometrically. The convex hulls of point sets and turn red when they intersect.
The algorithm starts by picking a point in the Minkowski Difference. This point can be randomly chosen or chosen based on previous knowledge. But for now let's pick a random point. This point is now our simplex. A simplex is a generalization of a tetrahedral region of space. A point is a 0-simplex. A line is a 1-simplex. A traingle is a 2-simplex, and a tetrahedron is a 3-simplex. That is, the points in a -simplex must be able to span an affine space in dimensions.
The problem can be broken into three parts depending on the size of the simplex.
If we have a 0-simplex, a point, then we create a vector, that is drawn from that point to the origin. Then we find the point in the Minkowski Difference that is furthest along that line. This is accomplished through a support mapping of . This support mapping becomes important when eliminating the need to compute the entire Minkowski Difference. It takes a set of points and a vector, , and returns the point in that set that is farthest along . Each time we compute the point, , farthest along we check to see if that point actually brings us closer to the origin. If it does not bring us closer then we terminate and there is no intersection. Otherwise we place the point that the support mapping returned into our simplex and we now have a 1-simplex. We only continue if
Let's take a closer look at the 1-simplex shown below
Point is the last point placed in the simplex. The first step is to determine whether the origin is in region 1, 2, or 3. We can begin by immediately eliminating region 3. We know the origin cannot be in region 3 because in our last step is defined as being closer to the origin than . Then it's simply a matter of doing a bit of math.
Where is a vector from to the origin. If the origin is in region 1 then we remove from the simplex and proceed with the 0-simplex case as shown above. If the origin is in region 2 then we create a new direction vector, , that is the shortest line from the 1-simplex to the origin. This is the black vector in the example figure. Again we submit and to our support mapping to find the point, , in , the Minkowski Difference, that is farthest along . If we terminate the algorithm because there is no point in that is closer to the origin than the 1-simplex. Otherwise, if there is a point closer we add that to the simplex. We now have a 2-simplex.
But in order to solve this problem algorithmically we need to break our simplex down into regions just as we did in the 1-simplex example. The 2-simplex has 7 regions in which the origin might lie. Let's break down each region shown below.
Remember that is the newest point in our simplex. We can immediately discount region 6 because is by definition closer to the origin than the line , which is our old simplex. We also discount regions 5 and 7. I'll leave the reason for discounting 5 and 7 as an exercise for the reader. Now we only have 4 regions to worry about. To start we can choose either line or line and determine which side of that line the origin lies on. Let's choose to start. If then we know that the origin lies to the right of the line . So now it can be in either region 2 or 3. If then the origin is in region 2 and our new simplex is and we proceed with the 2-simplex case. Otherwise, the origin lies in region 3 and the new simplex is simply the point , in which case we proceed with the 1-simplex case.. If it turns out the origin lies to the left of the line then we've eliminated region 2. So we're left with regions 1, 3, and 4. Now we can take line and find out if the origin is to the left or right. If then the origin lies to the left of . So now the origin can only be in regions 3 or 4. If then the origin is in region 4 and our new simplex is and we proceed with the 2-simplex case. Otherwise, the origin lies in region 3 and the new simplex is the point , in which case we proceed with the 1-simplex case. If the origin lies both to the left of and to the right of then the origin must lie inside our simplex. Eureka! In this case, the Minkowski Difference contains the origin, the algorithm terminates and our two convex polygons intersect. We can show the 2-simplex case in pseudocode
if aO cross ac > 0 //if O is to the right of ac if aO dot ac > 0 //if O is ahead of the point a on the line ac simplex = [a, c] d =-((ac.unit() dot aO) * ac + a) else // O is behind a on the line ac simplex = [a] d = aO else if ab cross aO > 0 //if O is to the left of ab if ab dot aO > 0 //if O is ahead of the point a on the line ab simplex = [a, b] d =-((ab.unit() dot aO) * ab + a) else // O is behind a on the line ab simplex = [a] d = aO else // O if both to the right of ac and to the left of ab return true //we intersect!
In the algorithm above we only have to ever branch twice. The last else returns true. This means this 2-simplex contains the origin. This is the case with our example shown below.
So our support mapping does not actually need the full Minkowski Difference. It can compute the max point along in the Minkowski Difference from the points in the individual sets, and . This greatly increases the efficiency of the algorithm. Our support mapping can also contain performance increases by having specific knowledge of the set of points it is given. For example, it is very easy to compute the max distance from a point to a circle. The support function could also know the vertex order of the point set it is passed, so instead of searching each point randomly, it can choose a point and proceed along by visiting each neighboring vertex in the direction of the origin. This is a Hill Climbing algorithm.