基于C#如何实现多边形冲突检测
短信预约 -IT技能 免费直播动态提醒
这篇文章主要为大家展示了“基于C#如何实现多边形冲突检测”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“基于C#如何实现多边形冲突检测”这篇文章吧。
前言
之前在项目上碰到了一个多边形冲突检测的问题，经百度、bing、google，发现目前已有的方案，要么是场景覆盖不全，要么是通过第三方类库实现（而这些第三方类库几乎是无法逆向反编译的），而项目中禁止使用第三方类库，遂自己实现了此算法。
场景是这样的，有两个多边形，多边形A和多变型B，需要判断多边形B是否在多变型A内，即多边形B是否是多边形A的子多边形。
B的点全部在A内
A的点全部在B外
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#如何实现多边形冲突检测”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网行业资讯频道！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
