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

Question

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

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

所以我正在考虑运行已知为线性时间算法的 graham 扫描并对其进行修改。

这是我的算法

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

算法是否准确(返回 false 表示它不是凸的)

Answer 1

确实，可以使用行列式在恒定时间内检查角度是否小于或大于 PI。总计为 O(N)。

如果所有角的方向相同，我们仍应检查多边形是否也不是自相交的。在这里，将所有补角相加并检查总和是否为 2 * PI 就足够了。可以使用 float 并检查近似相等性。这也是O(N)。

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

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