基于C#實現(xiàn)的多邊形沖突檢測實例
更新時間：2021年07月05日 11:36:22 作者：王振耀
這篇文章主要給大家介紹了基于C#實現(xiàn)的多邊形沖突檢測的相關資料,文中介紹的方法并未使用第三方類庫,可以完美解決這個問題,需要的朋友可以參考下
前言
之前在項目上碰到了一個多邊形沖突檢測的問題，經(jīng)百度、bing、google，發(fā)現(xiàn)目前已有的方案，要么是場景覆蓋不全，要么是通過第三方類庫實現(xiàn)（而這些第三方類庫幾乎是無法逆向反編譯的），而項目中禁止使用第三方類庫，遂自己實現(xiàn)了此算法。
場景是這樣的，有兩個多邊形，多邊形A和多變型B，需要判斷多邊形B是否在多變型A內，即多邊形B是否是多邊形A的子多邊形。
- B的點全部在A內
- A的點全部在B外
- A的線段與B的線段沒有相交
接下來進行實現(xiàn)
第一步：創(chuàng)建多邊形類
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 }
多邊形
第二步：創(chuàng)建點類
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 }
點
第三步：創(chuàng)建線段類
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=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 }
線段
第四步：創(chuàng)建線段的類型枚舉
/// <summary>
/// 線段的類型
/// </summary>
public enum LineType_Enum
{
/// <summary>
/// 豎線
/// </summary>
XX,
/// <summary>
/// 橫線
/// </summary>
YY,
/// <summary>
/// 斜線
/// </summary>
XnXYnY
}
第五步：在多邊形類中增加沖突檢測方法
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 else
108 {
109 return true;
110 }
111 return true;
112 }
多邊形沖突檢測
第六步：在點的類中增加點與線段關系的判斷方法
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_Enum
66 {
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 OnLineSagement
83 }
點與線段關系的判斷
第七步：在點的類中實現(xiàn)子多邊形的點是否在父多邊形內的判斷方法
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 //射線穿過多邊形邊界的次數(shù)為奇數(shù)時點在多邊形內
27 if (cnt % 2 == 1)
28 {
29 return true;//點在多邊形內
30 }
31 else
32 {
33 return false;//點不在多邊形內
34 }
35 }
子多邊形的點是否在父多邊形內
第八步：在點的類中實現(xiàn)父多邊形的點是否在子多邊形內的判斷方法
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 //射線穿過多邊形邊界的次數(shù)為奇數(shù)時點在多邊形內
26 if (cnt % 2 == 1)
27 {
28 return true;//點在多邊形內
29 }
30 else
31 {
32 return false;//點不在多邊形內
33 }
34 }
父多邊形的點是否在子多邊形內
第九步：在多邊形的類中實現(xiàn)多邊形自身的線段是否與另外一個多邊形的所有線段相交的方法
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 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 }
線段是否與多邊形的所有線段有相交
總結
到此這篇基于C#實現(xiàn)的多邊形沖突檢測的文章就介紹到這了,更多相關C#多邊形沖突檢測內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
C#使用zxing/zbar/thoughtworkQRcode解析二維碼的示例代碼
zxing是谷歌開源的二維碼庫，zbar，thoughtworkQRcode也是開源的，三者之間比較各有優(yōu)劣，本文將通過一個案例demo源碼，帶來認識學習下這三者的實際解碼效果，感興趣的可以了解一下2023-07-07
Jquery+Ajax+Json+存儲過程實現(xiàn)高效分頁
這篇文章主要介紹Jquery+Ajax+Json+存儲過程實現(xiàn)分頁，需要的朋友可以參考下2015-08-08
這篇文章主要介紹了C#中的is和as操作符區(qū)別小結,is是驗證操作對象是不是自己希望的,as是將對象轉換成指定類型,需要的朋友可以參考下2015-01-01
C#修改及重置電腦密碼DirectoryEntry實現(xiàn)方法
這篇文章主要介紹了C#修改及重置電腦密碼DirectoryEntry實現(xiàn)方法,實例分析了C#修改及重置電腦密碼的相關技巧,需要的朋友可以參考下2015-05-05
這篇文章主要為大家詳細介紹了Unity實現(xiàn)聊天室功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03
這篇文章主要給大家介紹了關于C#中Task.Yield的用途的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-11-11
在一些軟件,比如,進銷存管理系統(tǒng)中添加銷售單信息時,每個銷售單都可能對應多種商品,而且在向銷售單中添加商品時,一般都是在新彈出的窗體中選擇商品,這時就涉及通過子窗體刷新父窗體的問題,本文給大家介紹了C#通過子窗體刷新父窗體的實現(xiàn)方法,需要的朋友可以參考下2024-04-04
Unity登錄注冊時限制發(fā)送驗證碼次數(shù)功能的解決方法
這篇文章主要為大家詳細介紹了Unity登錄注冊時限制發(fā)送驗證碼次數(shù)功能的解決方案，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
本文主要介紹了C#中利用GDI來繪制圖形和文字的方法，并提供的簡單的示例供大家參考學習，希望能夠對大家有所幫助。2016-03-03
本篇文章是對c#中引用類型與值類型的區(qū)別進行了詳細的分析介紹，需要的朋友參考下2013-05-05