Hierarchical Path Planning for Multi-Component Graphics Guided by Topological Information

This study addressed the problem of reducing non-productive pen-up motion when drawing graphics that contain multiple disconnected and nested components.A hierarchical topological optimization algorithm was developed to model component-wise containment relations and to improve the planning of inter-component transitions.The graphic was first decomposed into connected components,and an internal coverage path was generated for each component.Topological containment was then identified through component boundary analysis.A hierarchical planning strategy was established:global traveling-sequence optimization was applied to top-level components using a nearest-neighbor and 2-opt solver,and nested components were processed through a deterministic greedy rule based on local distance.The algorithm integrated internal paths with optimized inter-component connections to form a complete drawing path.The algorithm was evaluated on three datasets—custom graphics,Google QuickDraw sketches,and KanjiVG characters.The results showed that it achieved 100% path completeness and produced the lowest pen-up movement distance ratio among the compared strategies,including simple concatenation,depth-first-search greedy planning,and traveling-salesman-based optimization.Execution time increased only slightly and exhibited no growth in computational order.Experiments on a sugar-painting robot demonstrated that the algorithm reduced non-productive motion and improved drawing efficiency.These results indicate that the method is effective for complex graphics used in robotic drawing,additive manufacturing,and CNC machining.