设计一种线性时间算法检查n个顶点多边形是否凸

Question

而且我也不应该假设多边形是不相交的。

我知道凸多边形是一个不相交的多边形，它的性质是所有的角度都小于PI，换句话说，它的方向总是顺时针或逆时针方向。

因此，我想运行格雷厄姆扫描，这是已知的线性时间算法，并修改它。

这是我的算法

we sort the vertices by orientation (using determinants)
Select the right most vertex in the Polygon P (call it r)
Let q and p be the next and second next vertex of Polygon P (based on orientation)
while(there is a vertex in the Polygon P)
  if orientation(p, q, r) == CW (clock wise , that means we changed directions)
     return false
  else
   r = p
   p = q
   q = next vertex
return true

那个算法准确(返回假表示它不是凸的)

Answer 1

事实上，可以用行列式在恒定时间内检查一个角度是小于还是大于PI。总数为O (N)。

如果所有的角度都有相同的方向，我们仍然应该检查多边形是否也不是自相交的。这里，只要把所有的补充角加起来，并检查和是否为2* PI就足够了。使用浮点和检查近似相等是很好的。这也是O (N)。

但是，我们应该按照顶点在多边形边界上的顺序访问它们。如果给你一个多边形，你可能已经有了这个顺序。另一方面，如果你只得到平面上的一组点，在一般情况下，在这些点上有顶点的多边形并不是唯一的。因此，不需要对顶点进行任何排序:不仅是O (N log N)，而且我们这样做也失去了重要的顺序信息。

我们可以从任何顶点开始。

Answer 2

你的算法不起作用

(例如，如果多边形链绕原点旋转两次)

请参阅http://hal.inria.fr/inria-00413179/en