<p>A pocket is one of the most machined features of mechanical parts. However, when machining complex pockets, calculating the maximum allowable tool diameter and cutting path is difficult owing to the boundary spline curve and irregular shape. To improve the cutting efficiency of pockets, a method is proposed to build the medial axis to obtain a feasible set of cutting tools using the Voronoi graph. The pocket is triangulated by the point insertion method to calculate the medial axis, and the curve of the medial axis is fitted by the least-squares method. An optimal tool combination method is proposed to achieve a high cutting efficiency. The reachable cutting areas of tools with different radii in the CAD geometric model are analyzed. The simulated annealing algorithm is used to obtain an optimal tool combination, which is the contribution of this study. The high-efficiency cutting of complex pockets with optimal cutting tools was tested experimentally. The results show the excellent performance of the proposed method, with the processing efficiency increased by 28.47%.</p>