任意平面多边形顶点凸凹性的快速新算法

摘要

给出了一个基于叉积、顶点凸凹性、顺逆性的关系，同时确定xoy平面多边形顶点凸凹性和顺逆性的快速新算法。该算法简单、直观，且不需要事先假定顶点序列的顺逆性。用该算法解决了三维空间平面多边形的顶点凸凹性问题，算法的时间复杂度为o（n）。