基于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=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 }