基于C#的多边形冲突检测

 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=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 /// <summary>  2 /// 线段的类型  3 /// </summary>  4  public enum LineType_Enum  5  {  6      /// <summary>  7      /// 竖线  8      /// </summary>  9      XX, 10      /// <summary> 11      /// 横线 12      /// </summary> 13      YY, 14      /// <summary> 15      /// 斜线 16      /// </summary> 17      XnXYnY 18 }

  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 }

 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     else 32     { 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     else 31     { 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                     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 }