c++ - 多边形C++的凸性？

Question

我如何通过知道多边形的点及其在 C++ 中的坐标来测试多边形是否是凸的？

Answer 1

对于多边形的每一侧，计算线方程 ( Ax+By+C=0) 并检查（将x和y放入方程并得到它的符号），所有点都来自它的一侧。

编辑：如果旅行凸多边形，您将始终在每个点上旋转到一个方向（左或右）。使用叉积，您可以简单地推断出下一回合您将旋转到哪一侧（负或正）。如果三个连续点的所有叉积都等号，那么你的多边形是凸的。

Answer 2

礼品包装算法是一种用于计算给定点集的凸包的算法。

来自维基的伪代码：

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]  // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (endpoint == pointOnHull) or
            (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0] // wrapped around to first hull point

如果您的点与上述算法的检测点匹配，则多边形是凸的。

Answer 3

使用任何常用算法找到凸包。一个多边形是凸的当且仅当它的所有顶点都属于它的凸包。

这是 O(n log n)，但不依赖于点在多边形边缘周围以正确顺序给出的假设。如果假设为真，那么来自仇恨引擎的答案是最优的（即线性时间。）