| Popis: |
This article addresses the two-polygon containment problem. The problem is to determine if two polygons, denoted P1, and P2, can fit inside a fixed polygon Q without overlap. The case when P1 and P2 are allowed to translate and rotate and all three polygons are convex, is considered. After characterizing the solution space, an approach utilizing mathematical programming is introduced. An efficient algorithm is developed and implemented for the special case when sides of P1 and P2 are matching. The problem is solved by viewing it as a parametric programming problem with a nonlinear parameter. As the algorithm proceeds, optimality conditions (primal feasibility, dual feasibility, and complementary slackness) are maintained continuously. The complexity of the algorithm is O(b(p1 + p2)q), where p1, p2, and q are the numbers of vertices in the polygons, and b is the number of dual bases encountered (switches in combinations of contacts being maintained) as the angle of rotation ranges through 2π radians. The detailed algebraic development, an example, and computational experience are included. |
Full Text from ScienceDirect