基于C#如何实现多边形冲突检测

这篇文章主要为大家展示了“基于C#如何实现多边形冲突检测”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“基于C#如何实现多边形冲突检测”这篇文章吧。

前言

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

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

1. B的点全部在A内

2. A的点全部在B外

3. A的线段与B的线段没有相交
   

接下来进行实现

创建多边形类

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 /// <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 /// <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 }线段

创建线段的类型枚举

/// <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     else108     {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_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 /// <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 /// <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  /// <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#如何实现多边形冲突检测”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网精选频道！