多邊形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++的凸性？

回答

相關問題