The machining performance of five-axis machining can be significantly enhanced by partitioning the surface into subregions, each employing an adaptive machining strategy. This approach is particularly beneficial because non-spherical cutting tools offer a wide range of effective cutting radii, making them ideal for efficiently machining of complex surfaces while preventing local gouging. Current methods for partitioning complex surface primarily focus on individual surface geometries designed for conventional cutting tools, which are inadequate for accommodating non-spherical cutting tools and fail to consider the comprehensive geometric factors related to both the surface and the cutting tool. In this research, we propose a vertex clustering-based surface partitioning method that utilizes three novel geometric metrics to represent interference conditions, tool orientation smoothness, and cutting width. Based on the partitioned surface, we introduce a method for generating and smoothing a preferred tool orientation vector field. From this, we generate an iso-scallop distance scalar field, where the iso-scallop Cutter Contact (CC) curves are defined as the iso-curves of the proposed scalar field. To validate our proposed method, we conducted computer simulations and physical cutting experiments. The results demonstrated that the average cutting width achieved by our approach significantly surpasses that of two benchmark methods, leading to drastically reduced path lengths and machining time.