Determining two minimal circumscribing discs for a polygon

Abstract

The paper proposes a 2-disc motion planning strategy to navigate an object within free space between obstacles from an initial location to a final location. The method makes use of the medial axis transform of the free space. Two minimal overlapping discs that fully enclose the moving object are determined, and then the centres of the two discs are constrained to move continuously along a path on the medial axis. The paper focuses on the problem of finding the two enclosing discs for an arbitrary moving polygon object. The problem is reduced to one of finding an optimal straight line cut through the polygon such that each of the subpolygons can be covered by a minimal disc. The paper discusses how an arbitrary polygon is cut, and how the two minimal overlapping discs that cover the given polygon are determined. Simulations are presented for a variety of polygons. The method has been used for planning part disassembly motion from inside to outside assembly.