Polycenter: fast and precise polygon center identification for GIS and beyond

Identifying the visual centers of polygons, including those with holes, holds significant importance across multiple disciplines. Applications range from improving label placement in Geographic Information Science (GIS) and enabling obstacle avoidance and object grasping in robotics to facilitating roundness evaluation in materials science. However, widely used algorithms such as Polylabel exhibit notable limitations. To overcome these, the Polycenter algorithm combines binary search for local optima with a divide-and-conquer partitioning strategy to attain global optimality. Theoretical analysis and empirical tests on diverse datasets—including complex geometries such as the coastlines of the ten largest islands in the world—demonstrate that Polycenter outperforms Polylabel. Notably, Polycenter handles any non-self-intersecting polygon, including those with parallel sides, which Polylabel cannot address. By leveraging polygon elements in contact with the maximum inscribed circle, the algorithm operates directly without requiring a predefined precision parameter, fully exploiting floating-point precision. In terms of efficiency, Polycenter surpasses Polylabel by an average factor of ten at a precision parameter of 10−8 and by a factor of three at a precision parameter of 1.0. These advancements not only enhance the aforementioned applications but also promise broader impacts in urban planning and image recognition.