如何確定多邊形的類型

用戶輸入第n個點。我需要檢查多邊形是否存在，然後確定類型 - 凹面或凸面多邊形。我知道如果每個角度都在180度以下，多邊形就是凸的。所以問題歸結爲尋找多邊形的每個內角。我一直在尋找公式或算法，但沒有成功。如何確定多邊形的類型

實施例：

輸入：N = 4;

POINT1：（5; 6）

POINT2：（4; -5）

點3：（-5; 4）

Point4：（1-5; 5）

預期輸出：多邊形是凸

這是到目前爲止的代碼：日現在它只能找到飛機中各點之間的最大和最小距離。

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

int main() 
{ 
    double a[15][2]; 
    int n; 
    cin >> n; 
    if (n <= 0 && n > 15) 
     return 1; 

    for (int i = 0; i < n; i++) 
    { 
     cout << "x" << i << " = , y" << i << " = "; 
     cin >> a[i][0] >> a[i][1]; 
    } 

    double maxDistance = 0.0; 
    double minDistance = 0.0; 
    double maxpoint1[2]; 
    double maxpoint2[2]; 
    double minpoint1[2]; 
    double minpoint2[2]; 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      if (j != i) 
      { 
       double x1 = a[i][0]; 
       double x2 = a[j][0]; 
       double y1 = a[i][1]; 
       double y2 = a[j][1]; 
       double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); 

       if (currentDistance > maxDistance) 
       { 
        maxDistance = currentDistance; 
        maxpoint1[0] = x1; 
        maxpoint1[1] = y1; 
        maxpoint2[0] = x2; 
        maxpoint2[1] = y2; 

       } 

       if (minDistance > currentDistance) 
       { 
        currentDistance = minDistance; 
        minpoint1[0] = x1; 
        minpoint1[1] = y1; 
        minpoint2[0] = x2; 
        minpoint2[1] = y2; 
       } 

       cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2; 
       cout << endl << "Distance is " << currentDistance; 
       cout << endl; 
      } 
     } 
    } 

    cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1]; 
    cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1]; 


    return 0; 
}

來源

2016-11-22 S.Yankov

找到，如果多邊形是凸或凹，只是檢查跨產品的標誌爲所有連續點三胞胎CrossProduct(P[0], P[1], P[2]) etc。如實施例

CrossProductSign(A, B, C) = 
       SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X))

對於凸一個所有跨產品必須具有相同的符號（+或 - ）。

它是如何工作的：對於凸多邊形，每個三元組在同一側（或CW，或CCW取決於行走方向）轉彎。對於凹面的標誌會有所不同（內角超過180度）。請注意，您不需要計算角度值。

來源

2016-11-22 10:12:24 MBo

如果要查找兩側之間的角度，請使用矢量的交叉或點積。

a dot b = | a || b | COS（angle_between_vectors）= A [0] * B [0] + A [1] * B [1] + A [2] * B [2]

內角將（PI - angle_between_vectors）

哦，順便說一下，多邊形可能會相交，這在許多使用情況下也是有害的問題。您的定義將無法檢測到......例如復四邊形的所有角度都小於90度。

這不是唯一的方法來確定多邊形是凸的，也可能是大多數計算豐富的一個？點產品的問題是，如果角度小於或大於pi/2，它的符號將顯示。確定您的多邊形是不是複雜或非凸的正確方法是檢查方向是否改變。爲此，你需要交叉產品。對於二維向量，其交叉積的結果只有z分量（垂直於平面），其符號決定了旋轉發生的方向。

問題已經在這裏。

How do determine if a polygon is complex/convex/nonconvex?

來源

2016-11-22 09:40:05 Swift

如何確定多邊形的類型

回答

相關問題