前言
之前在项目上碰到了一个多边形冲突检测的问题，经百度、bing、google，发现目前已有的方案，要么是场景覆盖不全，要么是通过第三方类库实现（而这些第三方类库几乎是无法逆向反编译的），而项目中禁止使用第三方类库，遂自己实现了此算法。
场景是这样的，有两个多边形，多边形A和多变型B，需要判断多边形B是否在多变型A内，即多边形B是否是多边形A的子多边形。
- B的点全部在A内
- A的点全部在B外
- A的线段与B的线段没有相交
接下来进行实现
第一步：创建多边形类
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
1 /// <summary> 2 /// 多边形 3 /// </summary> 4 public class Area_Dto 5 { 6 /// <summary> 7 /// 点的集合 8 /// </summary> 9 public List<Point_Dto> Points { get; set; }10 /// <summary>11 /// 线段的集合12 /// </summary>13 public List<LineSagement_Dto> LineSagements { get; set; }14 }多边形 |
第二步：创建点类
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
1 /// <summary> 2 /// 点 3 /// </summary> 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 /// <summary>12 /// 点的X坐标13 /// </summary>14 public double X { get; private set; }15 /// <summary>16 /// 点的Y坐标17 /// </summary>18 public double Y { get; private set; }19 }点 |
第三步：创建线段类
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
1 /// <summary> 2 /// 线段 3 /// </summary> 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 /// <summary>13 /// 线段的起始点14 /// </summary>15 public Point_Dto Start { get; private set; }16 /// <summary>17 /// 线段的终止点18 /// </summary>19 public Point_Dto End { get; private set; }20 /// <summary>21 /// 线段的类型22 /// </summary>23 public LineType_Enum FunType { get; set; }24 /// <summary>25 /// 线段为斜线是才有实际作用26 /// 线段的斜率及线段与Y轴的交点27 /// </summary>28 public List<double> Params { get; set; } = new List<double>();29 /// <summary>30 /// 交点列表31 /// </summary>32 public List<Point_Dto> Intersection { get; set; } = new List<Point_Dto>();33 34 /// <summary>35 /// 求当前线段的斜率，当当前线段为斜线时，同时是求出与Y轴的交点36 /// </summary>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=247 this.FunType = LineType_Enum.XX;48 this.Params.Add(x1);49 50 }51 else if (y1 == y2)52 {53 //type=154 this.FunType = LineType_Enum.YY;55 this.Params.Add(y1);56 }57 else58 {59 //type=360 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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/// <summary>/// 线段的类型/// </summary> public enum LineType_Enum { /// <summary> /// 竖线 /// </summary> XX, /// <summary> /// 横线 /// </summary> YY, /// <summary> /// 斜线 /// </summary> XnXYnY} |
第五步：在多边形类中增加冲突检测方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
1 /// <summary> 2 /// 多边形冲突检测 3 /// </summary> 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<Point_Dto> 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<Point_Dto> 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<Point_Dto> 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<Point_Dto> 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 else108 {109 return true;110 }111 return true;112 }多边形冲突检测 |
第六步：在点的类中增加点与线段关系的判断方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
1 /// <summary> 2 /// 此点向右引出的射线是否穿过sagement 3 /// 穿过的定义： 4 /// 此点在sagement的顶点上 5 /// 此点在sagement上 6 /// 此点不符合以上两种情况且此点引出的射线穿过sagement 7 /// </summary> 8 /// <param name="sagement"></param> 9 /// <returns>True:穿过线段 False:没有穿过线段</returns>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 /// <summary>63 /// 点线的关系64 /// </summary>65 public enum PointWithLineSagementState_Enum66 {67 /// <summary>68 /// 顶点重合69 /// </summary>70 VertexOverlap,71 /// <summary>72 /// 相交73 /// </summary>74 Cross,75 /// <summary>76 /// 不相交77 /// </summary>78 UnCross,79 /// <summary>80 /// 在线段上81 /// </summary>82 OnLineSagement83 }点与线段关系的判断 |
第七步：在点的类中实现子多边形的点是否在父多边形内的判断方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
1 /// <summary> 2 /// 子多边形的点是否在父多边形内 3 /// </summary> 4 /// <param name="theArea">父多边形</param> 5 /// <param name="vertexOverlap">当顶点重合时，是否算在图形内. 默认是算的</param> 6 /// <returns></returns> 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 else32 {33 return false;//点不在多边形内34 }35 }子多边形的点是否在父多边形内 |
第八步：在点的类中实现父多边形的点是否在子多边形内的判断方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
1 /// <summary> 2 /// 父多边形的点是否在子多边形内 3 /// </summary> 4 /// <param name="theArea"></param> 5 /// <returns></returns> 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 else31 {32 return false;//点不在多边形内33 }34 }父多边形的点是否在子多边形内 |
第九步：在多边形的类中实现多边形自身的线段是否与另外一个多边形的所有线段相交的方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
1 /// <summary> 2 /// 线段是否与多边形的所有线段有相交 3 /// True:是 4 /// False:否 5 /// </summary> 6 public bool WhetherPolygonIntersection(Area_Dto father) 7 { 8 List<LineSagement_Dto> childEdgeXfatherEdge_List = new List<LineSagement_Dto>(); 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 else113 {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 else161 {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.X169 - (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.Y172 - (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) <= 0177 // 且交点也在线段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 else183 {184 continue;185 }186 }187 }188 if (this.LineSagements.Where(m => m.Intersection.Any()).Any())189 {190 return true;191 }192 else193 {194 return false;195 }196 }线段是否与多边形的所有线段有相交 |
总结
到此这篇基于C#实现的多边形冲突检测的文章就介绍到这了,更多相关C#多边形冲突检测内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://www.cnblogs.com/wangzhenyao1994/p/14963059.html
