多边形C++的凸性？

我如何测试多边形是凸或不只是通过知道多边形与它们在C++中的坐标的点？多边形C++的凸性？

来源

2013-03-03 user2116010

当然，您不希望我们为您提供此类问题的完整源代码。你有什么尝试？你坚持使用算法吗？你不知道如何用C++来制定算法吗？ – Oswald 2013-03-03 21:04:07

您可以逐个查看点，抓住当前点的两个相邻点，然后使用余弦定理找出这三点所包围的角度。如果发现角度大于90度，那么多边形是凹的，如果没有大于90度的角度，那么它是凸的。 – 2013-03-03 21:04:16

我试过这种方式，但我不知道如何确定它是内部角度还是外部因为我需要内部的一个 – user2116010 2013-03-03 21:08:58

多边形的每一面，计算线方程（Ax+By+C=0），检查（放x和y入式，并得到其踪影），所有的点都从它的一边。

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

来源

2013-03-03 21:12:14

礼物包装算法是计算给定点集合的凸壳的算法。从wiki

伪代码：

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

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

来源

2013-03-03 21:03:54 deepmax

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

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

来源

2013-03-03 21:29:49

多边形C++的凸性？

回答

相关问题