之前在项目上碰到了一个多边形冲突检测的问题，经百度、bing、google，发现目前已有的方案，要么是场景覆盖不全，要么是通过第三方类库实现（而这些第三方类库几乎是无法逆向反编译的），而项目中禁止使用第三方类库，遂自己实现了此算法。

场景是这样的，有两个多边形，多边形A和多变型B，需要判断多边形B是否在多变型A内，即多边形B是否是多边形A的子多边形。

1. B的点全部在A内
2. A的点全部在B外
3. A的线段与B的线段没有相交

接下来进行实现

第一步：创建多边形类

1 ///

2 /// 多边形 3 ///

4 public class Area_Dto
5 {
6 ///

7 /// 点的集合 8 ///

9 public List Points { get; set; }
10 ///

11 /// 线段的集合 12 ///

13 public List LineSagements { get; set; }
14 }

多边形

第二步：创建点类

1 ///

2 /// 点 3 ///

4 public class Point_Dto
5 {
6 public Point_Dto(double x, double y)
7 {
8 this.X = x;
9 this.Y = y;
10 }
11 ///

12 /// 点的X坐标 13 ///

14 public double X { get; private set; }
15 ///

16 /// 点的Y坐标 17 ///

18 public double Y { get; private set; }
19 }

点

第三步：创建线段类

1 ///

2 /// 线段 3 ///

4 public class LineSagement_Dto
5 {
6 public LineSagement_Dto(Point_Dto start, Point_Dto end)
7 {
8 this.Start = start;
9 this.End = end;
10 GetFuncParam(this);
11 }
12 ///

13 /// 线段的起始点 14 ///

15 public Point_Dto Start { get; private set; }
16 ///

17 /// 线段的终止点 18 ///

19 public Point_Dto End { get; private set; }
20 ///

21 /// 线段的类型 22 ///

23 public LineType_Enum FunType { get; set; }
24 ///

25 /// 线段为斜线是才有实际作用 26 /// 线段的斜率及线段与Y轴的交点 27 ///

28 public List Params { get; set; } = new List();
29 ///

30 /// 交点列表 31 ///

32 public List Intersection { get; set; } = new List();
33
34 ///

35 /// 求当前线段的斜率，当当前线段为斜线时，同时是求出与Y轴的交点 36 ///

37 public void GetFuncParam(LineSagement_Dto lineSegment)
38 {
39 double x1 = this.Start.X;
40 double y1 = this.Start.Y;
41 double x2 = this.End.X;
42 double y2 = this.End.Y;
43
44 if (x1 == x2)
45 {
46 //type=2
47 this.FunType = LineType_Enum.XX;
48 this.Params.Add(x1);
49
50 }
51 else if (y1 == y2)
52 {
53 //type=1
54 this.FunType = LineType_Enum.YY;
55 this.Params.Add(y1);
56 }
57 else
58 {
59 //type=3
60 this.FunType = LineType_Enum.XnXYnY;
61 double a = (y2 - y1) / (x2 - x1);//斜率
62 double b = y1 - (x1 * ((y2 - y1) / (x2 - x1)));//与Y轴的交点
63 this.Params.Add(a);
64 this.Params.Add(b);
65 }
66
67 }
68 }

线段

第四步：创建线段的类型枚举

1 ///

2 /// 线段的类型 3 ///

4 public enum LineType_Enum
5 {
6 ///

7 /// 竖线 8 ///

9 XX,
10 ///

11 /// 横线 12 ///

13 YY,
14 ///

15 /// 斜线 16 ///

17 XnXYnY
18 }

第五步：在多边形类中增加冲突检测方法

1 ///

2 /// 多边形冲突检测 3 ///

4 public bool CheckIfInArea(Area_Dto area)
5 {
6 if (area.LineSagements == null)
7 {
8 return true;
9 }
10 //若子点有在父外的则结束
11 foreach (Point_Dto point in this.Points)
12 {
13 if (!point.CheckIfInArea(area))
14 return false;
15 }
16 //若父点有在子内的则结束
17 foreach (Point_Dto point in area.Points)
18 {
19 if (point.CheckIfInChildArea(this))
20 return false;
21 }
22 //所有子线段与父线段没有相交则不冲突
23 if (WhetherPolygonIntersection(area))
24 {
25 foreach (LineSagement_Dto edg in this.LineSagements)
26 {
27 if (edg.Intersection.Any())
28 {
29 if (edg.FunType == LineType_Enum.XX)
30 {
31 List jiaodainList = edg.Intersection.OrderBy(m => m.Y).ToList();
32 for (int i = 0; i < jiaodainList.Count - 1; i++) 33 { 34 Point_Dto start = jiaodainList[i]; 35 Point_Dto end = jiaodainList[i + 1]; 36 Point_Dto z = new Point_Dto(start.X, start.Y + ((end.Y - start.Y) / 2)); 37 if (z.CheckIfInArea(area)) 38 { 39 continue; 40 } 41 else 42 { 43 return false; 44 } 45 } 46 } 47 else if (edg.FunType == LineType_Enum.YY) 48 { 49 List jiaodainList = edg.Intersection.OrderBy(m => m.X).ToList();
50 for (int i = 0; i < jiaodainList.Count - 1; i++) 51 { 52 Point_Dto start = jiaodainList[i]; 53 Point_Dto end = jiaodainList[i + 1]; 54 Point_Dto z = new Point_Dto(start.X + ((end.X - start.X) / 2), start.Y); 55 if (z.CheckIfInArea(area)) 56 { 57 continue; 58 } 59 else 60 { 61 return false; 62 } 63 } 64 } 65 else if (edg.FunType == LineType_Enum.XnXYnY) 66 { 67 if (edg.Start.Y <= edg.End.Y) 68 { 69 List jiaodainList = edg.Intersection.OrderBy(m => m.X).ThenBy(m => m.Y).ToList();
70 for (int i = 0; i < jiaodainList.Count - 1; i++) 71 { 72 Point_Dto start = jiaodainList[i]; 73 Point_Dto end = jiaodainList[i + 1]; 74 Point_Dto z = new Point_Dto(start.X + ((end.X - start.X) / 2), start.Y + ((end.Y - start.Y) / 2)); 75 if (z.CheckIfInArea(area)) 76 { 77 continue; 78 } 79 else 80 { 81 return false; 82 } 83 } 84 } 85 else 86 { 87 List jiaodainList = edg.Intersection.OrderBy(m => m.X).ThenByDescending(m => m.Y).ToList();
88 for (int i = 0; i < jiaodainList.Count - 1; i++)
89 {
90 Point_Dto start = jiaodainList[i];
91 Point_Dto end = jiaodainList[i + 1];
92 Point_Dto z = new Point_Dto(start.X + ((end.X - start.X) / 2), start.Y - ((start.Y - end.Y) / 2));
93 if (z.CheckIfInArea(area))
94 {
95 continue;
96 }
97 else
98 {
99 return false;
100 }
101 }
102 }
103 }
104 }
105 }
106 }
107 else
108 {
109 return true;
110 }
111 return true;
112 }

多边形冲突检测

第六步：在点的类中增加点与线段关系的判断方法

1 ///

2 /// 此点向右引出的射线是否穿过sagement 3 /// 穿过的定义： 4 /// 此点在sagement的顶点上 5 /// 此点在sagement上 6 /// 此点不符合以上两种情况且此点引出的射线穿过sagement 7 ///

8 ///
9 /// True:穿过线段 False:没有穿过线段
10 public PointWithLineSagementState_Enum CheckPointInLineSagement(LineSagement_Dto sagement)
11 {
12 double px = this.X;
13 double py = this.Y;
14 //bool flag = false;
15
16
17 Point_Dto pi = sagement.Start;
18 Point_Dto pj = sagement.End;
19 double sx = pi.X; double sy = pi.Y;
20 double tx = pj.X; double ty = pj.Y;
21
22 //点与线段顶点重合
23 bool psTf = (px == sx && py == sy);
24 bool ptTf = (px == tx && py == ty);
25 if (psTf || ptTf)
26 {
27 return PointWithLineSagementState_Enum.VertexOverlap;
28 }
29 switch (sagement.FunType)
30 {
31 case LineType_Enum.XX:
32 if (px == pi.X && ((py <= sy && py >= ty) || (py >= sy && py <= ty))) 33 return PointWithLineSagementState_Enum.OnLineSagement; 34 break; 35 case LineType_Enum.YY: 36 if (py == pi.Y && ((px >= sx && px <= tx) || (px <= sx && px >= tx)))
37 return PointWithLineSagementState_Enum.OnLineSagement;
38 break;
39 case LineType_Enum.XnXYnY:
40 default:
41 break;
42 }
43 //判断线段端点是否在射线两侧
44 if ((sy < py && ty >= py) || (sy >= py && ty < py)) 45 { 46 //线段上与射线Y坐标相同的点的X坐标 47 double x = sx + (py - sy) * (tx - sx) / (ty - sy); 48 //点在线段上 49 if (x == px) 50 { 51 return PointWithLineSagementState_Enum.OnLineSagement; 52 } 53 //射线穿过线段 54 if (x > px)
55 {
56 return PointWithLineSagementState_Enum.Cross;
57 }
58 }
59 return PointWithLineSagementState_Enum.UnCross;
60 }
61
62 ///

63 /// 点线的关系 64 ///

65 public enum PointWithLineSagementState_Enum
66 {
67 ///

68 /// 顶点重合 69 ///

70 VertexOverlap,
71 ///

72 /// 相交 73 ///

74 Cross,
75 ///

76 /// 不相交 77 ///

78 UnCross,
79 ///

80 /// 在线段上 81 ///

82 OnLineSagement
83 }

点与线段关系的判断

第七步：在点的类中实现子多边形的点是否在父多边形内的判断方法

1 ///

2 /// 子多边形的点是否在父多边形内 3 ///

4 /// 父多边形
5 /// 当顶点重合时，是否算在图形内. 默认是算的
6 ///
7 public bool CheckIfInArea(Area_Dto theArea)
8 {
9 int cnt = 0;
10 foreach (LineSagement_Dto lineSagement in theArea.LineSagements)
11 {
12 switch (CheckPointInLineSagement(lineSagement))
13 {
14 case PointWithLineSagementState_Enum.Cross:
15 cnt += 1;
16 break;
17 case PointWithLineSagementState_Enum.OnLineSagement:
18 return true;
19 case PointWithLineSagementState_Enum.VertexOverlap:
20 return true;
21 case PointWithLineSagementState_Enum.UnCross:
22 default:
23 break;
24 }
25 }
26 //射线穿过多边形边界的次数为奇数时点在多边形内
27 if (cnt % 2 == 1)
28 {
29 return true;//点在多边形内
30 }
31 else
32 {
33 return false;//点不在多边形内
34 }
35 }

子多边形的点是否在父多边形内

第八步：在点的类中实现父多边形的点是否在子多边形内的判断方法

1 ///

2 /// 父多边形的点是否在子多边形内 3 ///

4 ///
5 ///
6 public bool CheckIfInChildArea(Area_Dto theArea)
7 {
8 int cnt = 0;
9 foreach (LineSagement_Dto lineSagement in theArea.LineSagements)
10 {
11 switch (CheckPointInLineSagement(lineSagement))
12 {
13 case PointWithLineSagementState_Enum.Cross:
14 cnt += 1;
15 break;
16 case PointWithLineSagementState_Enum.OnLineSagement:
17 return false;
18 case PointWithLineSagementState_Enum.VertexOverlap:
19 return false;
20 case PointWithLineSagementState_Enum.UnCross:
21 default:
22 break;
23 }
24 }
25 //射线穿过多边形边界的次数为奇数时点在多边形内
26 if (cnt % 2 == 1)
27 {
28 return true;//点在多边形内
29 }
30 else
31 {
32 return false;//点不在多边形内
33 }
34 }

父多边形的点是否在子多边形内

第九步：在多边形的类中实现多边形自身的线段是否与另外一个多边形的所有线段相交的方法

1 ///

2 /// 线段是否与多边形的所有线段有相交 3 /// True:是 4 /// False:否 5 ///

6 public bool WhetherPolygonIntersection(Area_Dto father)
7 {
8 List childEdgeXfatherEdge_List = new List();
9 foreach (LineSagement_Dto edg in this.LineSagements)
10 {
11 Point_Dto a = edg.Start;
12 Point_Dto b = edg.End;
13 foreach (LineSagement_Dto fatherEdge in father.LineSagements)
14 {
15 Point_Dto c = fatherEdge.Start;
16 Point_Dto d = fatherEdge.End;
17
18 double denominator = (b.Y - a.Y) * (d.X - c.X) - (a.X - b.X) * (c.Y - d.Y);
19 // 如果分母为0 则平行或共线, 不相交
20 if (denominator == 0)
21 {
22 //竖线
23 if (edg.FunType == LineType_Enum.XX)
24 {
25 //共线
26 if (edg.Start.X == fatherEdge.Start.X)
27 {
28 //不重叠
29 if (b.Y > c.Y || a.Y < d.Y) 30 { 31 continue; 32 } 33 //完全重叠 34 if (a.Y == c.Y && b.Y == d.Y) 35 { 36 continue; 37 } 38 //上跨立（包含两线相接） 39 if (a.Y > c.Y && b.Y <= c.Y && b.Y >= d.Y)
40 {
41 edg.Intersection.Add(c);
42 continue;
43 }
44 //下跨立（包含两线相接）
45 if (a.Y <= c.Y && a.Y >= d.Y && b.Y < d.Y) 46 { 47 edg.Intersection.Add(d); 48 continue; 49 } 50 //父包子 51 if (c.Y >= a.Y && d.Y <= b.Y) 52 { 53 continue; 54 } 55 //子包父 56 if (a.Y >= c.Y && b.Y <= d.Y) 57 { 58 edg.Intersection.Add(c); 59 edg.Intersection.Add(d); 60 continue; 61 } 62 } 63 //平行 64 else 65 { 66 continue; 67 } 68 } 69 70 //横线 71 else if (edg.FunType == LineType_Enum.YY) 72 { 73 //共线 74 if (edg.Start.Y == fatherEdge.Start.Y) 75 { 76 //不重叠 77 if (b.X < c.X || a.X > d.X)
78 {
79 continue;
80 }
81 //完全重叠
82 if (a.X == c.X && b.X == d.X)
83 {
84 continue;
85 }
86 //左跨立（包含两线相接）
87 if (a.X < c.X && b.X >= c.X && b.X <= d.X) 88 { 89 edg.Intersection.Add(c); 90 continue; 91 } 92 //右跨立（包含两线相接） 93 if (b.X > d.X && a.X >= c.X && a.X <= d.X) 94 { 95 edg.Intersection.Add(d); 96 continue; 97 } 98 //父包子 99 if (c.X <= a.X && d.X >= b.X)
100 {
101 continue;
102 }
103 //子包父
104 if (a.X <= c.X && b.X >= d.X)
105 {
106 edg.Intersection.Add(c);
107 edg.Intersection.Add(d);
108 continue;
109 }
110 }
111 //平行
112 else
113 {
114 continue;
115 }
116 }
117 //斜线
118 else if (edg.FunType == LineType_Enum.XnXYnY)
119 {
120 //共线
121 if (edg.Params.First().Equals(fatherEdge.Params.First()) && edg.Params.Last().Equals(fatherEdge.Params.Last()))
122 {
123 //不重叠
124 if ((a.X < c.X && b.X < c.X) 125 || (a.X > d.X && b.X > d.X))
126 {
127 continue;
128 }
129 //完全重叠
130 if (a.X == c.X && a.Y == c.Y && b.X == d.X && b.Y == d.Y)
131 {
132 continue;
133 }
134 //跨立（包含两线相接）
135 if (a.X < c.X && b.X >= c.X && b.X <= d.X) 136 { 137 edg.Intersection.Add(c); 138 continue; 139 } 140 //跨立（包含两线相接） 141 if (a.X >= c.X && a.X <= d.X && b.X > d.X)
142 {
143 edg.Intersection.Add(d);
144 continue;
145 }
146 //父包子
147 if (a.X >= c.X && a.X <= d.X && b.X >= c.X && b.X <= d.X) 148 { 149 continue; 150 } 151 //子包父 152 if (a.X <= c.X && b.X >= d.X)
153 {
154 edg.Intersection.Add(c);
155 edg.Intersection.Add(d);
156 continue;
157 }
158 }
159 //平行
160 else
161 {
162 continue;
163 }
164 }
165 }
166 // 线段所在直线的交点坐标 (x , y)
167 double x = ((b.X - a.X) * (d.X - c.X) * (c.Y - a.Y)
168 + (b.Y - a.Y) * (d.X - c.X) * a.X
169 - (d.Y - c.Y) * (b.X - a.X) * c.X) / denominator;
170 double y = -((b.Y - a.Y) * (d.Y - c.Y) * (c.X - a.X)
171 + (b.X - a.X) * (d.Y - c.Y) * a.Y
172 - (d.X - c.X) * (b.Y - a.Y) * c.Y) / denominator;
173 // 判断交点是否在两条线段上
174 if (
175 // 交点在线段1上
176 (x - a.X) * (x - b.X) <= 0 && (y - a.Y) * (y - b.Y) <= 0 177 // 且交点也在线段2上 178 && (x - c.X) * (x - d.X) <= 0 && (y - c.Y) * (y - d.Y) <= 0) 179 { 180 edg.Intersection.Add(new Point_Dto(x, y)); 181 } 182 else 183 { 184 continue; 185 } 186 } 187 } 188 if (this.LineSagements.Where(m => m.Intersection.Any()).Any())
189 {
190 return true;
191 }
192 else
193 {
194 return false;
195 }
196 }

线段是否与多边形的所有线段有相交