如何确定多边形的类型

用户输入第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

如何确定多边形的类型

回答

相关问题