论文部分内容阅读
多边形及多边形模型的分割问题是计算几何,计算机图形学,计算机辅助设计中的重要课题。多边形中重要的几何特征,具有显著的视觉特征意义,符合人类的潜在认知心理和认知规律。因此,多边形及多边形模型的特征分割方法和技术被广泛地应用于形状分割、无线传感器网络、机器人运动规划、地理信息系统(GIS)等领域。 本文围绕简单多边形特征分割,带孔洞的复杂多边形特征分割,以及任意类型多边形(简单多边形或带孔洞的复杂多边形)特征分割的统一处理框架中的若干问题进行了系统而深入的研究,取得的主要研究成果如下: 首先,针对简单多边形特征分割,构造了新的多边形顶点凹度值的测量公式,并采取有针对性的约束措施和近似凸分割方法的策略思想,给出了简单多边形的一种高质量分割方法;另外,提出了后续补充步骤,直至把多边形所有重要的显著特征的凹点全部剔除为止,符合分割的视觉特征意义;在特征分割过程中,还提出了一种新的估算阈值δ的方法,即采用先验性估计和自适应调整相结合的方法来估算出阈值δ的具体数值,从而满足用户的实际应用需求。 其次,本文提出了一种针对带孔洞的复杂多边形特征分割方法,该方法通过添加合适的连接线把带孔洞的复杂多边形转化成一个新的不带孔洞的多边形,并且改进了对带孔洞的复杂多边形顶点凹度值测量方法,使其凹度值(特征)的测量更精确,更高效,在该特征分割方法中,计算分割线的过程及估算阈值δ的过程,与上述简单多边形的分割方法类似,即采用了各种有效的保证形态质量的约束措施,并结合近似凸分割方法的策略思想来作分割线的计算,根据用户实际需求和几何信息预先估算出阈值δ的具体数值,从而有效地分割该新的不带孔洞的多边形。 最后,对任意类型多边形(简单多边形或带孔洞的复杂多边形)的统一处理分割问题,本文构建了一个多边形的统一分割框架,能有效地分割各种类型的多边形。在此框架中的后续递归分割过程中,给出了一种灵巧而高效的混合递归方法,即通过详细分析各子多边形的特性和构造,采取相应的合理分割步骤。该统一分割框架的算法时间复杂度仅为O(nr),这里n和r分别是目标多边形的顶点数目,和凹点数目。 实验结果表明,对简单多边形的特征分割方法在分割结果的形态质量,及对多边形特征点的有效识别等方面,均大大优于近似凸分割的方法。此外,分割方法的算法复杂度和近似凸分割方法的算法复杂度一样;对带孔洞的复杂多边形的特征分割方法不仅能处理带任意多个复杂孔洞的复杂多边形,还能使其分割结果形态质量高,布局美观,并且,依次调整阈值δ的数值能得到自然而优雅的层次分割序列;我们的统一分割框架有很强的鲁棒性,分割效率高,且所生成的分割结果形态质量好,整体布局美观。