Minkovski operations with Mathematica.

Petr Tomiczek

University of West Bohemia, Plzen.

Minkovski operations
(Světlana Tomiczková, West Bohemia University)

The operations Minkowski sum and Minkowski difference are very useful especially for robot motion planning, solution of the packing, nesting and containment problems or for the computing of offset.

SetDirectory["E:Users\petr\CestyaKonference\USA2006"];

<< Minkoperations.m

Minkovski sum

We define the Minkowski sum of two sets A, B  as  A ⊕ B = { a + b : a ∈ A,  b ∈ B }.

We put  (A^b) = { a + b : a ∈ A } ,  then   A  ⊕ B = (⋃_(b ∈ B))(A^b) .

SetA = {{0. , 2.5}, {3. , 2. }, {4. , 4. }, {3.8, 5.5}, {0.2, 
            5. }};
SetB1 = {2. , 
          1. };
<< 
        Graphics`Arrow`;
vektB=Graphics[Arrow[{0, 0}, SetB1],HeadLength ->  .02,HeadWidth ->  .5];
Msuma = 
        Table[SetA[[i]] + SetB1,  {i, 
            Length[SetA]}];
Show[Graphics[{  {RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[1, 0, 0],Disk[SetB1, 0.03]},{RGBColor[0, 1, 1],Polygon[Msuma]} ,Line[Pripoj[Msuma]],Line[Pripoj[SetA]]}],vektB,Axes -> True];

SetB1 = {{0. , 0. }, {1.5, 0. }, {1.5, 
            1. }};
Msuma = Minksuma[SetA, SetB1]; 
Show[Graphics[{  {RGBColor[1, 0, 0],Polygon[SetB1]},{RGBColor[0, 1, 1],Polygon[Msuma]} ,{RGBColor[1, 1, 0],Polygon[SetA]},Line[Pripoj[SetB1]],Line[Pripoj[SetA]],Line[Pripoj[Msuma]]}],Axes -> True];

Minkovski difference

The Minkowski difference is defined in mathematical literature in various ways. 

We define the  Minkowski difference  of two sets  A, B  as  A ⊖ B = (⋂_(b ∈ B))(A^(-b)) .

For convex, bounded and closed sets this operation is reverse to the operation  A ⊕ B , i.e.   ( A ⊕ B )  ⊖ B = A . This operation is also useful for the solution of the containment problem, because if  it is possible to put B in A, then  A ⊖ B ≠ ∅ .  With the help of the Minkowski difference, we can also find all vectors which can move the set  B  into  A.

ShiftA = 
        Table[Table[
            SetA[[i]] - SetB1[[j]],  {i, Length[SetA]}],  {j, 
            Length[SetB1]}];
Show[Graphics[{{RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[1, 0, 0],Polygon[SetB1]},Line[Pripoj[SetB1]],Table[
                  Line[Pripoj[ShiftA[[i]]]],  {i, Length[ShiftA]}]}],Axes -> True];

If we compute Minkowski difference by definition as intersection of convex polygons, the computational complexity is   mn ln(mn).

Minkdiff = Mroz1[SetA, SetB1]; 
    ShiftBin = 
      Table[Minkdiff[[4]] + SetB1[[j]],  {j, 
          Length[SetB1]}];
Show[Graphics[{{RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[1, 0, 0],Polygon[SetB1]},{RGBColor[0, 1, 1],Polygon[Minkdiff]},Line[Pripoj[SetB1]],Line[Pripoj[ShiftBin]],Table[
                  Line[Pripoj[ShiftA[[i]]]],  {i, Length[ShiftA]}]}],Axes -> True];

This algorithm has the linear computational complexity.

http://webmath.zcu.cz:8080/webMathTest/tomiczek/CML/paja/mroz.jsp

Minkovski product

We define the Minkowski product of the set  B  and  singleton  A = { z }  as  
B  ⊗  A =  { b z :  b ∈ B } .
The Minkowski product of the set B and singleton A = { z }  is rotation of the set B about the origin by the angle arg z, and scaling of it by the magnification factor  | z |.

fi = 0;step = (π/20);While[fi < 2 π,Minkdiff = Mroz1[SetA, Otocofi[fi, SetB1]];
Show[Graphics[{{RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[1, 0, 0],Polygon[Otocofi[fi, SetB1]]},{RGBColor[0, 1, 1],Polygon[Minkdiff]},Line[Pripoj[Otocofi[fi, SetB1]]] ,Line[Pripoj[SetA]],Line[Pripoj[Minkdiff]]}],Axes -> True,ImageSize -> {700, 500},PlotRange -> {{-2.5, 4.5}, {-2, 6}}];fi = fi + step]

Containment problem

allpos = Optpoloha[SetA, SetB1, (π/360)]; 
    MujmnB1 = Vybermn[SetA, allpos];
Mindi = 
      Mroz1[SetA, MujmnB1]; 
    ShiftMindi = 
      Table[Mindi[[i]] + MujmnB1[[1]],  {i, 
          Length[Mindi]}];
Show[Graphics[{   
{RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[0, 1, 1],Polygon[ShiftMindi]},{RGBColor[1, 0, 0],Polygon[MujmnB1]},Line[Pripoj[SetA]],Table[
                  Line[Pripoj[allpos[[i]]]],  {i, Length[allpos]}]
                                                  }],Axes -> True];

1. We find the maximum of area of the Minkowski difference  M = A ⊖ ( B ⊗ {(e^i)φ} ) . 
    We obtain an optimal angle  (Subscript[φ, 1])  and we denote  (Subscript[B, 1 ])= B ⊗ {(e^i)(Subscript[φ, 1])}.
2. We consider all suitable positions of  (Subscript[B, 1])  (vertices of M + (Subscript[B, 1]))  and we find optimum of these positions.

SetB2 = {{-0.1, 0. }, {0. , 1. }, {-1. , 
            0. }};
vsechnypolroz = 
        Optpolrozdilu[SetA, SetB2, 
          MujmnB1, (π/360)];
MujmnB2 = 
        VyberB2[SetA, MujmnB1, vsechnypolroz];
Show[Graphics[{   
{RGBColor[1, 1, 0],Polygon[SetA]},{RGBColor[1, 0, 0],Polygon[SetB1]},
{RGBColor[0, 1, 0],Polygon[SetB2]},{RGBColor[1, 0, 0],Polygon[MujmnB1]},{RGBColor[0, 1, 0],Polygon[MujmnB2]}
                                                  }],
Graphics[{ 
              Table[Line[Pripoj[vsechnypolroz[[i]]]], {i, 
                  Length[vsechnypolroz]}] ,  
              Line[Pripoj[SetA]], 
Line[Pripoj[SetB2]], 
              Line[Pripoj[SetB1]] , Line[Pripoj[MujmnB2]]  , 
              Line[Pripoj[MujmnB1]]    }],Axes -> True,AspectRatio -> (1.7/2)];

1. We find the maximum of area of the Minkowski difference  
      M = (A \ (Subscript[B, 1]) ) ⊖ B2 = ( A  ⊖ B2 )\(TraditionalForm\`\(\(\ \)\(\(\\)\(\ \)\)\)\) ( (Subscript[B, 1]) ⊕ B2 ) . 
     We obtain an optimal angle  (Subscript[φ, 2])  and we denote  (Subscript[B, 2 ])= B2 ⊗ { (e^i)(Subscript[φ, 2]) }.
2. We consider all suitable positions of   (Subscript[B, 2 ])  ( vertices of M + (Subscript[B, 2 ]) )  and we find optimum of 
    these positions.