简单多边形方向与顶点凸凹性的本质联系

深入剖析平面简单多边形方向（逆时针或顺时针）与顶点凸凹性的内在本质联系，并由此提出解决平面简单多边形两类基本问题的快速方法。该方法已应用于工厂设计软件FOSOFT的工厂模型消隐和平剖图消隐中，并取得较好的效果。

简单多边形顶点凸凹性的快速确定算法

本文深入剖析了平面简单多边形方向（逆时针或顺时针）与顶点凸凹性的内在本质联系，提出了确定顶点凸凹性的快速算法，并解决了根据凸点确定多边形方向的基本问题。本文方法已应用于工厂设计软件ＰＤＳＯＦＴ的工厂模型消隐和平剖图消隐中。实践证明效果很好。

基于象限划分的简单多边形方向与顶点凸凹性快速判别算法

文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系;不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘/除法”运算;算法利用“假设-检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O(n)。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。

基于顶点凸凹性多边形的核的算法

简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。

关于多边形顶点凸凹性识别算法的研究

多边形顶点凸凹性识别是计算机图形学的一个很重要研究方向，曾出现了各种各样的自动识别方法。本文主要针对两种典型的多边形顶点凸凹性识别算法进行深入研究，并对它们的计算时间复杂度进行分析。

简单多边形凸凹顶点的识别

对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究,对多边形的方向进行预处理,使其按逆时针方向排列,彻底摆脱了先假设多边形方向后判断的重复判断思路,使得算法原理简单明了,实现过程容易。本算法采用C++语言、Visual Basic语言混合编程、Visual Basic 6.0演示输出结果。实际运行表明,该算法快捷,运行稳定。