我发现了San San Wu Wu和Sartaj Sahni的论文《快速算法对简单的直线多边形进行分割》，您可能会感兴趣。在您的示例中，字符为“
d”的区域形成一个直线多边形，以及字符为“ c”和“。”的区域。本文包括 无孔简单直线多边形的 算法。
如果多边形包含孔，则存在以O（n ^ 3/2 log n）时间运行的算法，如第11页上的“
多边形分解”中的JM Keil所述。
如果 最小化在分割过程中引入的线段的总长度是另一个优化标准
，则如果多边形包含孔（第12页），问题将变为NP完全。对于这些问题，存在近似算法（本文指的是具有此类算法的论文）。如果多边形不包含孔，则存在O（n ^
4）时间算法。
