基于C#如何實(shí)現(xiàn)多邊形沖突檢測(cè)

這篇文章主要為大家展示了“基于C#如何實(shí)現(xiàn)多邊形沖突檢測(cè)”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“基于C#如何實(shí)現(xiàn)多邊形沖突檢測(cè)”這篇文章吧。

前言

之前在項(xiàng)目上碰到了一個(gè)多邊形沖突檢測(cè)的問題，經(jīng)百度、bing、google，發(fā)現(xiàn)目前已有的方案，要么是場(chǎng)景覆蓋不全，要么是通過第三方類庫實(shí)現(xiàn)（而這些第三方類庫幾乎是無法逆向反編譯的），而項(xiàng)目中禁止使用第三方類庫，遂自己實(shí)現(xiàn)了此算法。

場(chǎng)景是這樣的，有兩個(gè)多邊形，多邊形A和多變型B，需要判斷多邊形B是否在多變型A內(nèi)，即多邊形B是否是多邊形A的子多邊形。

1. B的點(diǎn)全部在A內(nèi)

2. A的點(diǎn)全部在B外

3. A的線段與B的線段沒有相交
   

接下來進(jìn)行實(shí)現(xiàn)

第一步：創(chuàng)建多邊形類

1 /// <summary>
 2 /// 多邊形
 3 /// </summary>
 4 public class Area_Dto
 5 {
 6     /// <summary>
 7     /// 點(diǎn)的集合
 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)建點(diǎn)類

1 /// <summary>
 2 /// 點(diǎn)
 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     /// 點(diǎn)的X坐標(biāo)
13     /// </summary>
14     public double X { get; private set; }
15     /// <summary>
16     /// 點(diǎn)的Y坐標(biāo)
17     /// </summary>
18     public double Y { get; private set; }
19 }

點(diǎn)

第三步：創(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      /// 線段的起始點(diǎn)
14      /// </summary>
15      public Point_Dto Start { get; private set; }
16      /// <summary>
17      /// 線段的終止點(diǎn)
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      /// 線段為斜線是才有實(shí)際作用
26      /// 線段的斜率及線段與Y軸的交點(diǎn)
27      /// </summary>
28      public List<double> Params { get; set; } = new List<double>();
29      /// <summary>
30      /// 交點(diǎn)列表
31      /// </summary>
32      public List<Point_Dto> Intersection { get; set; } = new List<Point_Dto>();
33 
34      /// <summary>
35      /// 求當(dāng)前線段的斜率，當(dāng)當(dāng)前線段為斜線時(shí)，同時(shí)是求出與Y軸的交點(diǎn)
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軸的交點(diǎn)
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
}

第五步：在多邊形類中增加沖突檢測(cè)方法

1 /// <summary>
  2 /// 多邊形沖突檢測(cè)
  3 /// </summary>
  4 public bool CheckIfInArea(Area_Dto area)
  5 {
  6     if (area.LineSagements == null)
  7     {
  8         return true;
  9     }
 10     //若子點(diǎn)有在父外的則結(jié)束
 11     foreach (Point_Dto point in this.Points)
 12     {
 13         if (!point.CheckIfInArea(area))
 14             return false;
 15     }
 16     //若父點(diǎn)有在子內(nèi)的則結(jié)束
 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 }

多邊形沖突檢測(cè)

第六步：在點(diǎn)的類中增加點(diǎn)與線段關(guān)系的判斷方法

1 /// <summary>
 2 /// 此點(diǎn)向右引出的射線是否穿過sagement
 3 /// 穿過的定義：
 4 ///     此點(diǎn)在sagement的頂點(diǎn)上
 5 ///     此點(diǎn)在sagement上
 6 ///     此點(diǎn)不符合以上兩種情況且此點(diǎn)引出的射線穿過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     //點(diǎn)與線段頂點(diǎn)重合
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     //判斷線段端點(diǎn)是否在射線兩側(cè)
44     if ((sy < py && ty >= py) || (sy >= py && ty < py))
45     {
46         //線段上與射線Y坐標(biāo)相同的點(diǎn)的X坐標(biāo)
47         double x = sx + (py - sy) * (tx - sx) / (ty - sy);
48         //點(diǎn)在線段上
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 /// 點(diǎn)線的關(guān)系
64 /// </summary>
65 public enum PointWithLineSagementState_Enum
66 {
67     /// <summary>
68     /// 頂點(diǎn)重合
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 }

點(diǎn)與線段關(guān)系的判斷

第七步：在點(diǎn)的類中實(shí)現(xiàn)子多邊形的點(diǎn)是否在父多邊形內(nèi)的判斷方法

1 /// <summary>
 2 /// 子多邊形的點(diǎn)是否在父多邊形內(nèi)
 3 /// </summary>
 4 /// <param name="theArea">父多邊形</param>
 5 /// <param name="vertexOverlap">當(dāng)頂點(diǎn)重合時(shí)，是否算在圖形內(nèi). 默認(rèn)是算的</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ù)時(shí)點(diǎn)在多邊形內(nèi)
27     if (cnt % 2 == 1)
28     {
29         return true;//點(diǎn)在多邊形內(nèi)
30     }
31     else
32     {
33         return false;//點(diǎn)不在多邊形內(nèi)
34     }
35 }

子多邊形的點(diǎn)是否在父多邊形內(nèi)

第八步：在點(diǎn)的類中實(shí)現(xiàn)父多邊形的點(diǎn)是否在子多邊形內(nèi)的判斷方法

1 /// <summary>
 2 /// 父多邊形的點(diǎn)是否在子多邊形內(nèi)
 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ù)時(shí)點(diǎn)在多邊形內(nèi)
26     if (cnt % 2 == 1)
27     {
28         return true;//點(diǎn)在多邊形內(nèi)
29     }
30     else
31     {
32         return false;//點(diǎn)不在多邊形內(nèi)
33     }
34 }

父多邊形的點(diǎn)是否在子多邊形內(nèi)

第九步：在多邊形的類中實(shí)現(xiàn)多邊形自身的線段是否與另外一個(gè)多邊形的所有線段相交的方法

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             // 線段所在直線的交點(diǎn)坐標(biāo) (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             // 判斷交點(diǎn)是否在兩條線段上
174             if (
175                // 交點(diǎn)在線段1上
176                (x - a.X) * (x - b.X) <= 0 && (y - a.Y) * (y - b.Y) <= 0
177                // 且交點(diǎn)也在線段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#如何實(shí)現(xiàn)多邊形沖突檢測(cè)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！