Introduction

The Minkowski Sum can be used for the translation of a polygonal robot in a polygon scene in order to determine the area of the free configurations of the robot. The obstacles are expanded with the help of the Minkowski Sum between the robot and the obstacles. The robot can be limited thereby to only one point. Thus the motion planning problem for a polygonal robot is reduced to one point. Further information about the Minkowski Sum is to be found in [KK01] and [BKO00].

In the following sections first the definition of the Minkowski Sum is described, afterwards the steps are presented, which accomplish the applet with the computation of the Minkowski Sum. After the explanation of the handling of the applet, some sources are listed for additional information.

• Definition of the Minkowski Sum
• Steps for the computation of the Minkowski Sum
• An applet for the computation of the Minkowski Sum
• References

Definition of the Minkowski Sum

The definition of the Minkowski Sum, based on [KK01]:

Properties of the Minkowski Sum:

Steps for the computation of the Minkowski Sum

If the polygons P₁ and P₂ are convex the Minkowski Sum can be computed directly. There are no intermediate steps, which must be accomplished before. This means concretely that the polygon P₁ is sliding along the boundary of P₂. The range, which is covered thereby, is the Minkowski Sum (see figure).

If one of the two polygons is not convex, it must be first triangulated. Subsequently, the Minkowski Sum of each triangle with the other polygon is computed. Also the illustration of the figure applies for this, since it now concerns the computation of the Minkowski Sum of convex polygons. Subsequently, the result polygons must be merged.

If both polygons are not convex then both must be triangulated first. Then the Minkowski Sums of each triangle of P₁ with each triangle of P₂ must be computed. Subsequently, these partly Minkowski Sums are merged.

Altogether a method arises for the complexity of the result, based on [KK01]:

With 'Divide and Conquer' the algorithmic complexity of the problem is, based on [KK01] :

The Triangulation of Seidel is used to triangulate the polygons (see [SEI91] ) It is illustrated by an applet that can be found on another website.

An applet for the computation of the Minkowski Sum

The points of the polygons can be entered by clicking with the left mouse button. The Minkowski Sum is computed, as soon as the polygon-editor contains two simple, closed polygons. It is represented in the colour beige. It is possible to make modifications to the polygons afterwards, by pulling on the points or on the edges of them with the mouse, while keeping the left mouse button pressed. With means of the context menu, which is opened with the right mouse button over the polygon, one can delete the polygon, scale it and much more. Additionally one can display the reference point, again with the context menu. The Minkowski Sum is then shifted relatively to the reference point. The standard reference point is the most left point of the left polygon. For a better understanding of the Minkowski Sum one can display a visualization of the Computation. This feature can be triggered in the context menu, too.

References