之前在项目上碰到了一个多边形冲突检测的问题，经百度、bing、google，发现目前已有的方案，要么是场景覆盖不全，要么是通过第三方类库实现（而这些第三方类库几乎是无法逆向反编译的），而项目中禁止使用第三方类库，遂自己实现了此算法。
场景是这样的，有两个多边形，多边形A和多变型B，需要判断多边形B是否在多变型A内，即多边形B是否是多边形A的子多边形。
接下来进行实现
第一步：创建多边形类
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
