基于夹角符号序列的凸多边形直径算法

对一个凸多边形直径算法———夹角序列法,进行了较为深入的分析和研究,并在此基础上提出了夹角符号序列算法。算法分别讨论了利用求夹角正切值符号序列和余弦值符号序列来求解凸多边形直径的两种途径,并给出了各自的算法实现,最后对算法进行了验证,实验结果证明夹角符号序列算法效率高、可靠性好。

基于顶点间距离性质的凸多边形直径算法

平面点集的直径问题在计算机图形学、模式识别、图像处理、CAD/CAM等众多领域中均有广泛应用,该问题可转化为求凸多边形直径问题。研究得出了凸多边形顶点间距离关系的4条性质,利用这些性质提出一种基于顶点间距离性质的凸多边形直径算法。理论分析和实验结果表明,该算法计算速度快、存储效率高,实用性较强。