如何判断一个多边形是凸多边形还是凹多边形

admin

1. 如何判断一个多边形是凹多边形还是凸多边形？
2. 1.角度和判断：将多边形每个顶点处的较小角(内角或外角)相加，如果小于(n-2)*180,则为凹多边形。（可以使用向量点乘来等价求两个向量的夹角，它的值（角）总是以较短的弧度来度量）
3. 实现：
5. public static bool IsConcavePolygon(Vector2[] points)
6. {
7.         int totalAngle = (points.Length - 2) * 180;
8.         float angle = 0;
9.         for(int i=0;i<points.Length;i++)
10.         {
11.                 Vector2 v1,v2;
12.                 //向量1
13.                 if(i==0)
14.                         v1=points[points.Length-1]-points[i];
15.                 else
16.                         v1=points[i-1]-points[i];
17.                 //向量2
18.                 if(i==points.Length-1)
19.                         v2=points[0]-points[i];
20.                 else
21.                         v2 = points[i+1]-points[i];
22.                 //计算夹角：Mathf.Acos(Mathf.Clamp(Vector2.Dot(v1.normalized,to.normalized),-1f,1f))*57.29578f;
23.                 float a = Vector2.Angle(v1,v2);
24.                 angle+=a;
25.         }
26.         return angle<totalAngle;       
27. }
29. 2.检测凹点：凸多变形的每个顶点的转向都应该是一致的，不一致的点就是凹点。(向量的叉乘)
30. 实现：
32. //假设传入的是逆时针单向链
33. //判断两个向量的转向，如果是逆时针转，则为凸点，顺时针转则为凹点
34. public static bool IsConcavePolygon(Vector2[] points)
35. {
36.         for(int i=0;i<points.Length;i++)
37.         {
38.                 Vector2 v1,v2;
39.                 //向量1
40.                 if(i==0)
41.                         v1=points[points.Length-1]-points[i];
42.                 else
43.                         v1=points[i-1]-points[i];
44.                 //向量2
45.                 if(i==points.Length-1)
46.                         v2=points[0]-points[i];
47.                 else
48.                         v2 = points[i+1]-points[i];
49.                 //计算叉积，根据三维叉积公式计算，z轴为0
50.                 float corss = v1.x*v2.y-v1.y*v2.x;
51.                 if(corss>0)
52.                         return true;
53.         }
54.         return false;
55. }

复制代码