简单多边形顶点凹凸性快速判断

摘要

在计算机图形学中，经常要判断多边形顶点的凹凸性及顶点顺序。利用向量叉积的算法比较简单直观，并且算法可以达到O(n)。参考了一些论文，用js实现了一个demo，并且可以在线演示。

步骤

1. 找到一个多边形的凸顶点，上下左右极点必然是凸顶点。
2. 计算该顶点的叉积，得到多边形的顺序（顺时针还是逆时针）。
3. 计算出所有顶点的叉积，叉积方向与凸顶点方向相同的则是凸顶点，相反的凹顶点。

示例

拖动范围条可以看到凹点变成凸点