devbox
算法研究专家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Unity 面试题汇总（六）常用的一些几何算法_unity算法题

作者：算法研究专家 | 2024-01-16 15:32:36

赞

踩

unity算法题

Unity 面试题汇总（六）常用的一些几何算法

目录

Unity 面试题汇总（六）常用的一些几何算法

1、怎么判断一个点是否在直线上

2、判断点是否在线段上

3、判断点与线的位置关系

4、计算点在直线上的投影(向量投影)

5、计算点到直线距离

6、计算点到线段的距离

7、判断多边形是否为凸多边形

8、判断线段与线段是否共线

9、判断线段与线段是否重合(非相交)

10、线段与线段是否相交

11、计算直线与直线的交点

12、线段与线段的交点

13、射线与射线是否相交，以及交点

15.点围绕另一点旋转指定角度

16、点是否在任意多变内

17、点是否在椭圆内

18、直线与椭圆的交点计算

1、怎么判断一个点是否在直线上

已知点P(x,y)，以及直线上的两点A(x1,y1)、B(x2,y2)，可以通过计算向量AP与向量AB的叉乘是否等于0来计算点P是否在直线AB上

知识点：叉乘

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.     
  13.  
  14.     /// <summary>
  15.     /// 点是否在直线上
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns></returns>
  21.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  25.     }

2、判断点是否在线段上

已知点P(x,y)，以及线段A(x1,y1)，B(x2,y2)。

1）方法一

可以进行下面两部来判断点P是否在线段AB上：

（1）点是否在线段AB所在的直线上(点是否在直线上)
（2）点是否在以线段AB为对角线的矩形上，来忽略点在线段AB延长线上

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.     
  13.  
  14.     /// <summary>
  15.     /// 点是否在直线上
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns></returns>
  21.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  25.     }
  26.  
  27.  
  28.     /// <summary>
  29.     /// 点是否在线段上
  30.     /// </summary>
  31.     /// <param name="point"></param>
  32.     /// <param name="lineStart"></param>
  33.     /// <param name="lineEnd"></param>
  34.     /// <returns></returns>
  35.     public static bool IsPointOnSegment(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  36.     {
  37.         //1.先通过向量的叉乘确定点是否在直线上
  38.         //2.在拍段点是否在指定线段的矩形范围内
  39.         if (IsPointOnLine(point,lineStart,lineEnd))
  40.         {
  41.             //点的x值大于最小，小于最大x值 以及y值大于最小，小于最大
  42.             if (point.x >= Mathf.Min(lineStart.x, lineEnd.x) && point.x <= Mathf.Max(lineStart.x, lineEnd.x) &&
  43.                 point.y >= Mathf.Min(lineStart.y, lineEnd.y) && point.y <= Mathf.Max(lineStart.y, lineEnd.y))
  44.                 return true;
  45.         }
  46.         return false;
  47.     }
  48.

2）方法二

计算向量AP的长度加上向量BP的长度是否等于向量AB的长度，来确定点P是否在线段AB上

  1.     /// <summary>
  2.     /// 点是否在线段上
  3.     /// </summary>
  4.     /// <param name="point"></param>
  5.     /// <param name="lineStart"></param>
  6.     /// <param name="lineEnd"></param>
  7.     /// <returns></returns>
  8.     public static bool IsPointOnSegment2(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  9.     {
  10.         return Mathf.Approximately(Mathf.Abs((lineStart - point).magnitude) + Mathf.Abs((lineEnd - point).magnitude),
  11.                         Mathf.Abs((lineEnd - lineStart).magnitude));
  12.     }

3、判断点与线的位置关系

已知点P(x,y)，与直线上A(x1,y1)，B(x2,y2)两点，通过向量AP与BP的叉乘返回的结果，即可确定点在直线的位置关系。

判断依据：1）等于0：点在直线上；2）小于0：点在直线的左侧；3）大于0：点在直线的右侧

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.  
  13.  
  14.     /// <summary>
  15.     /// 点与线的位置关系
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns>==0：点在线上 <0：点在线的左侧 >0：点在线的右侧</returns>
  21.     public static int IsPointToLinePosition(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float crossValue = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         if (crossValue < 0) return -1;
  25.         if (crossValue > 0) return 1;
  26.         return 0;
  27.     }

4、计算点在直线上的投影(向量投影)

已知点P(x,y)，与直线上两点A(x1,y1),B(x2,2)，求P点在直线AB上的投影

知识点：通过向量投影公式（点乘），即可获得点P在直线AB投影点。

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.     
  13.  
  14.     /// <summary>
  15.     /// 点是否在直线上
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns></returns>
  21.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  25.     }
  26.     
  27.  
  28.     /// <summary>
  29.     /// 点到直线上的投影坐标
  30.     /// </summary>
  31.     /// <param name="point"></param>
  32.     /// <param name="lineStart"></param>
  33.     /// <param name="lineEnd"></param>
  34.     /// <returns></returns>
  35.     public static Vector2 Point2LineProject(Vector2 point,Vector2 lineStart,Vector2 lineEnd)
  36.     {
  37.     	if (IsPointOnLine(point,lineStart,lineEnd))
  38.             return point;
  39.         Vector2 v = point - lineStart;
  40.         Vector2 u = lineEnd - lineStart;
  41.         //求出u'的长度
  42.         float u1Length = Vector2.Dot(u, v) / u.magnitude;
  43.         return u1Length * u.normalized + lineStart;
  44.     }

5、计算点到直线距离

已点P(x,y)，与直线上两点A(x1,y1)，B(x2,y2)，求点P到直线AB的距离

1）方法1：
先求出点P在直线AB上的投影点P’，求出点P与点P’的距离即可。

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.     
  13.     /// <summary>
  14.     /// 点是否在直线上
  15.     /// </summary>
  16.     /// <param name="point"></param>
  17.     /// <param name="lineStart"></param>
  18.     /// <param name="lineEnd"></param>
  19.     /// <returns></returns>
  20.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  21.     {
  22.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  23.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  24.     }
  25.  
  26.     /// <summary>
  27.     /// 点到直线上的投影坐标
  28.     /// </summary>
  29.     /// <param name="point"></param>
  30.     /// <param name="lineStart"></param>
  31.     /// <param name="lineEnd"></param>
  32.     /// <returns></returns>
  33.     public static Vector2 Point2LineProject(Vector2 point,Vector2 lineStart,Vector2 lineEnd)
  34.     {
  35.     	if (IsPointOnLine(point,lineStart,lineEnd))
  36.             return point;
  37.         Vector2 v = point - lineStart;
  38.         Vector2 u = lineEnd - lineStart;
  39.         //求出u'的长度
  40.         float u1Length = Vector2.Dot(u, v) / u.magnitude;
  41.         return u1Length * u.normalized + lineStart;
  42.     }
  43.  
  44.     /// <summary>
  45.     /// 点到直线的距离
  46.     /// </summary>
  47.     /// <param name="point"></param>
  48.     /// <param name="lineStart"></param>
  49.     /// <param name="lineEnd"></param>
  50.     /// <returns></returns>
  51.     public static float Point2LineDistance(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  52.     {
  53.         return Vector2.Distance(point, Point2LineProject(point, lineStart, lineEnd));
  54.     }

2）方法2：
通过海伦公式+底x高三角形面积公式，就可求得点P到直线AB的距离。
海伦公式：知道三角形3条边长，求三角形面积。链接：海伦公式
底x高三角形面积公式：底x高=2倍的三角形面积

  1.  
  2.     /// <summary>
  3.     /// 2D叉乘
  4.     /// </summary>
  5.     /// <param name="v1">点1</param>
  6.     /// <param name="v2">点2</param>
  7.     /// <returns></returns>
  8.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  9.     {
  10.         //叉乘运算公式 x1*y2 - x2*y1
  11.         return v1.x * v2.y - v2.x * v1.y;
  12.     }
  13.     
  14.     /// <summary>
  15.     /// 点是否在直线上
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns></returns>
  21.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  25.     }    
  26.  
  27.     /// <summary>
  28.     /// 点到直线的距离
  29.     /// </summary>
  30.     /// <param name="point"></param>
  31.     /// <param name="lineStart"></param>
  32.     /// <param name="lineEnd"></param>
  33.     /// <returns></returns>
  34.     public static float Point2LineDistance(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  35.     {
  36.         //先判断点是否在线上
  37.         if (IsPointOnLine(point, lineStart, lineEnd)) return 0;
  38.         //通过海伦公式求得三角形面积，然后面积除以底，得到高度
  39.         //point 简写为p lineStart简写为s lineEnd简写为e
  40.         float se = Vector2.Distance(lineStart, lineEnd);
  41.         float sp = Vector2.Distance(lineStart, point);
  42.         float ep = Vector2.Distance(lineEnd, point);
  43.         
  44.         //海伦公式 + 底x高面积公式
  45.         //半周长
  46.         float p = (se + sp + ep) / 2;
  47.         //求面积
  48.         float s = Mathf.Sqrt(p * (p - se) * (p - sp) * (p - ep));
  49.         //面积除以底得高度
  50.         return 2 * s / se;
  51.     }

6、计算点到线段的距离

已知点P(x,y)，与线段A(x1,y1)，B(x2,y2)，计算点到线段的距离

思路：先求出点到直线AB(包括线段AB的延长线)的投影点，在判断点是否在线段AB的矩形区间内，在计算两点的距离即可。

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.     
  13.     /// <summary>
  14.     /// 点是否在直线上
  15.     /// </summary>
  16.     /// <param name="point"></param>
  17.     /// <param name="lineStart"></param>
  18.     /// <param name="lineEnd"></param>
  19.     /// <returns></returns>
  20.     public static bool IsPointOnLine(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  21.     {
  22.         float value = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  23.         return Mathf.Abs(value) <0.0003 /* 使用 Mathf.Approximately(value,0) 方式，在斜线上好像无法趋近为0*/;
  24.     }
  25.  
  26.     /// <summary>
  27.     /// 点到直线上的投影坐标
  28.     /// </summary>
  29.     /// <param name="point"></param>
  30.     /// <param name="lineStart"></param>
  31.     /// <param name="lineEnd"></param>
  32.     /// <returns></returns>
  33.     public static Vector2 Point2LineProject(Vector2 point,Vector2 lineStart,Vector2 lineEnd)
  34.     {
  35.     	if (IsPointOnLine(point,lineStart,lineEnd))
  36.             return point;
  37.         Vector2 v = point - lineStart;
  38.         Vector2 u = lineEnd - lineStart;
  39.         //求出u'的长度
  40.         float u1Length = Vector2.Dot(u, v) / u.magnitude;
  41.         return u1Length * u.normalized + lineStart;
  42.     }
  43.  
  44.     /// <summary>
  45.     /// 点到线段的距离
  46.     /// </summary>
  47.     /// <param name="point"></param>
  48.     /// <param name="lineStart"></param>
  49.     /// <param name="lineEnd"></param>
  50.     /// <returns></returns>
  51.     public static float Point2SegmentDistance(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  52.     {
  53.         Vector2 projectPoint = Point2LineProject(point,lineStart,lineEnd);
  54.         if (projectPoint.x >= Mathf.Min(lineStart.x, lineEnd.x) &&
  55.             projectPoint.x <= Mathf.Max(lineStart.x, lineEnd.x) &&
  56.             projectPoint.y >= Mathf.Min(lineStart.y, lineEnd.y) && projectPoint.y <= Mathf.Max(lineStart.y, lineEnd.y))
  57.             return Vector2.Distance(point, projectPoint);
  58.         return float.MaxValue;
  59.     }

7、判断多边形是否为凸多边形

凸(凹)多边形 计算方法
已知多边形的逆时针顶点序列，依次判断相邻两个线段走向是否一致即可。

(点与线段位置关系，因为规定为逆时针顶点序列，所以只要两个相邻线段的叉乘都小于0则该多边形为凸多边形)

  1.     /// <summary>
  2.     /// 2D叉乘
  3.     /// </summary>
  4.     /// <param name="v1">点1</param>
  5.     /// <param name="v2">点2</param>
  6.     /// <returns></returns>
  7.     public static float CrossProduct2D(Vector2 v1,Vector2 v2)
  8.     {
  9.         //叉乘运算公式 x1*y2 - x2*y1
  10.         return v1.x * v2.y - v2.x * v1.y;
  11.     }
  12.  
  13.  
  14.     /// <summary>
  15.     /// 点与线的位置关系
  16.     /// </summary>
  17.     /// <param name="point"></param>
  18.     /// <param name="lineStart"></param>
  19.     /// <param name="lineEnd"></param>
  20.     /// <returns>==0：点在线上 <0：点在线的左侧 >0：点在线的右侧</returns>
  21.     public static int IsPointToLinePosition(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
  22.     {
  23.         float crossValue = CrossProduct2D(point - lineStart, lineEnd - lineStart);
  24.         if (crossValue < 0) return -1;
  25.         if (crossValue > 0) return 1;
  26.         return 0;
  27.     }
  28.  
  29.  
  30.     /// <summary>
  31.     /// 是否为凸多边形
  32.     /// </summary>
  33.     /// <param name="points">逆时针点序列</param>
  34.     /// <returns></returns>
  35.     public static bool IsConvexPolygon(List<Vector2> points)
  36.     {
  37.         //计算每个顶点的转向，如果有不一致的转向，则表示该多边形不是凸多边形
  38.         if (points.Count < 3) return false;
  39.         bool isConvex = true;
  40.         for (int i = 1; i < points.Count; i++)
  41.         {
  42.             Vector2 point = points[i];
  43.             //上一个点
  44.             Vector2 point1 = points[i - 1];
  45.             //下一个点，如果超出当前点集合，则需要获取第一个点
  46.             int nextIndex = i + 1;
  47.             if (nextIndex >= points.Count) nextIndex = 0;
  48.             Vector2 point2 = points[nextIndex];
  49.             //计算朝向，因为点集合为逆时针点序列，如果点在线段右侧，则表示该角大于180 该多边形为凹多边形
  50.             float value = IsPointToLinePosition(point1, point,point2);
  51.             if (value > 0)
  52.             {
  53.                 isConvex = false;
  54.                 break;
  55.             }
  56.         }
  57.         return isConvex;
  58.     }

8、判断线段与线段是否共线

思路：

1）先判断两条线段是否平行，即两条线段的叉积等于0
2）在判断两条线段是否共线，即线段1一个点在线段2的延长线上

  1. 	/// <summary>
  2.     /// 线段与线段是否共线
  3.     /// </summary>
  4.     /// <param name="segment1Start"></param>
  5.     /// <param name="segment1End"></param>
  6.     /// <param name="segment2Start"></param>
  7.     /// <param name="segment2End"></param>
  8.     /// <returns></returns>
  9.     public static bool IsSegmentCollineation(Vector2 segment1Start, Vector2 segment1End, Vector2 segment2Start,
  10.                     Vector2 segment2End)
  11.     {
  12.         //1.判断两个向量是否平行
  13.         float value = CrossProduct2D(segment1End - segment1Start, segment2End - segment2Start);
  14.         if (Mathf.Abs(value)<0.0003f)
  15.         {    
  16.             // 平行，则判断一个线上的点是否在另一线上
  17.             if (IsPointOnLine(segment2Start, segment2End , segment2Start))
  18.                 return true;
  19.         }
  20.         return false;
  21.     }

9、判断线段与线段是否重合(非相交)

1）判断两条线段必须共线
2）然后片段判断线段A的起终点是否在线段B，以及线段B的起终点，是否在线段A上，只要有一个条件成立，则可以认为两条线段是重合的
或
1）判断两条线段是否共线
2）对两条线段的4个定点进行排序，如果1,3 或 1,4 为为同一条线段上的点，则可以任务两条线段是否重合的

  1.     /// <summary>
  2.     /// 线段与线段是否重合(全部重合或局部重合)
  3.     /// </summary>
  4.     /// <param name="segment1Start"></param>
  5.     /// <param name="segment1End"></param>
  6.     /// <param name="segment2Start"></param>
  7.     /// <param name="segment2End"></param>
  8.     /// <returns></returns>
  9.     public static bool IsSegmentCoincide(Vector2 segment1Start, Vector2 segment1End, Vector2 segment2Start,
  10.                     Vector2 segment2End)
  11.     {
  12.         //先判断两条线段是否在同一条线上
  13.         if (!IsSegmentCollineation(segment1Start,segment1End,segment2Start,segment2End))
  14.             return false;
  15.  
  16.         //如果是相同的起终点
  17.         if (segment1Start == segment2Start && segment1End == segment2End) return true;
  18.         //判断检测点是否在另一条线段上
  19.         if (IsPointOnSegment2(segment1Start, segment2Start, segment2End) ||
  20.             IsPointOnSegment2(segment1End, segment2Start, segment2End) ||
  21.             IsPointOnSegment2(segment2Start, segment1Start, segment1End) ||
  22.             IsPointOnSegment2(segment2End, segment1Start, segment1End))
  23.             return true;
  24.         return false;
  25.     }

10、线段与线段是否相交

线段与线段是否相交1
线段与线段是否相交2

  1.     /// <summary>
  2.     /// 线段是否相交
  3.     /// </summary>
  4.     /// <param name="segment1Start"></param>
  5.     /// <param name="segment1End"></param>
  6.     /// <param name="segment2Start"></param>
  7.     /// <param name="segment2End"></param>
  8.     /// <returns></returns>
  9.     public static bool IsSegmentIntersect(Vector2 segment1Start, Vector2 segment1End, Vector2 segment2Start,
  10.                     Vector2 segment2End)
  11.     {
  12.         //快速排斥实验
  13.         if (Mathf.Min(segment1Start.x,segment1End.x) <= Mathf.Max(segment2Start.x,segment2End.x) 
  14.             && Mathf.Min(segment2Start.x,segment2End.x) <= Mathf.Max(segment2Start.x,segment2End.x)
  15.             && Mathf.Min(segment1Start.y,segment1End.y)<=Mathf.Max(segment2Start.y,segment2End.y)
  16.             && Mathf.Min(segment2Start.y,segment2End.y) <= Mathf.Max(segment1Start.y,segment1End.y))
  17.         {
  18.             //先判断线段是否重合，重合，则认为也是相交
  19.             if (IsSegmentCoincide(segment1Start, segment1End, segment2Start, segment2End))
  20.                 return true;
  21.             //互为跨立的判断 一线的点相对另一线的位置关系，左右 -1 1，之和为 0
  22.             int state = IsPointToLinePosition(segment1Start, segment2Start, segment2End) +
  23.                         IsPointToLinePosition(segment1End, segment2Start, segment2End) +
  24.                         IsPointToLinePosition(segment2Start, segment1Start, segment1End) +
  25.                         IsPointToLinePosition(segment2End, segment1Start, segment1End);
  26.             if (state==0) return true;
  27.         }
  28.         return false;
  29.     }

11、计算直线与直线的交点

推导公式

  1.     /// <summary>
  2.     /// 求直线的交点
  3.     /// </summary>
  4.     /// <param name="line1Start"></param>
  5.     /// <param name="line2End"></param>
  6.     /// <param name="line2Start"></param>
  7.     /// <param name="line2End"></param>
  8.     /// <returns></returns>
  9.     public static Vector2 LineIntersectPoint(Vector2 line1Start, Vector2 line1End, Vector2 line2Start,
  10.                     Vector2 line2End)
  11.     {
  12.         //两点式公式
  13.         //x0 = ((x3-x4) * (x2*y1 - x1*y2) - (x1-x2) * (x4*y3 - x3*y4)) / ((x3-x4) * (y1-y2) - (x1-x2) * (y3-y4));
  14.         //y0 = ((y3-y4) * (y2*x1 - y1*x2) - (y1-y2) * (y4*x3 - y3*x4)) / ((y3-y4) * (x1-x2) - (y1-y2) * (x3-x4));
  15.         
  16.         float x1 = line1Start.x, x2 = line1End.x, x3 = line2Start.x, x4 = line2End.x;
  17.         float y1 = line1Start.y, y2 = line1End.y, y3 = line2Start.y, y4 = line2End.y;
  18.         
  19.         Vector2 point = Vector2.zero;
  20.         point.x = ((x3-x4) * (x2*y1 - x1*y2) - (x1-x2) * (x4*y3 - x3*y4)) / ((x3-x4) * (y1-y2) - (x1-x2) * (y3-y4));
  21.         point.y = ((y3-y4) * (y2*x1 - y1*x2) - (y1-y2) * (y4*x3 - y3*x4)) / ((y3-y4) * (x1-x2) - (y1-y2) * (x3-x4));
  22.         return point;
  23.     }

12、线段与线段的交点

1）先判断线段与线段是否相交。
2）如果相交，则获取直线与直线的交点
其中，需要注意线段平行与重合情况。
平行：无交点
全部重合：返回其中一条线段的起点与终点
部分重合：返回重合部分的起点与终点

  1.     /// <summary>
  2.     /// 线段与线段的交点
  3.     /// </summary>
  4.     /// <param name="segment1Start"></param>
  5.     /// <param name="segment1End"></param>
  6.     /// <param name="segment2Start"></param>
  7.     /// <param name="segment2End"></param>
  8.     /// <param name="points"></param>
  9.     /// <returns></returns>
  10.     public static bool SegmentIntersectPoint(Vector2 segment1Start,Vector2 segment1End,Vector2 segment2Start,Vector2 segment2End,out List<Vector2> points)
  11.     {
  12.         //线段相同情况下 直接返回其中一条线段即可
  13.         if (segment1Start==segment2Start && segment1End== segment2End)
  14.         {
  15.             points = new List<Vector2>(){segment1Start,segment1End};
  16.             return true;
  17.         }
  18.         points = new List<Vector2>();
  19.         //线段平行，且不共线，则无交点
  20.         float value = CrossProduct2D(segment1End - segment1Start, segment2End - segment2Start);
  21.         if (Mathf.Approximately(Mathf.Abs(value), 0))
  22.         {
  23.             //共线判断，一点是否在另一条线段上
  24.             if (!IsPointOnLine(segment1Start,segment2Start,segment2End))
  25.                 return false;
  26.             //平行且共线的情况下，需要知道线段是否重合
  27.             if (IsPointOnSegment2(segment1Start, segment2Start, segment2End))
  28.                 points.Add(segment1Start);
  29.             if (IsPointOnSegment2(segment1End, segment2Start, segment2End))
  30.                 points.Add(segment1End);
  31.             if (IsPointOnSegment2(segment2Start, segment1Start, segment1End))
  32.                 points.Add(segment2Start);
  33.             if (IsPointOnSegment2(segment2End, segment1Start, segment1End))
  34.                 points.Add(segment2End);
  35.             if (points.Count <= 0) return false;
  36.             return true;
  37.         }
  38.  
  39.         //不平行，且不共线，则需要判断两个线段是否相交
  40.         if (!IsSegmentIntersect(segment1Start, segment1End, segment2Start, segment2End))
  41.             return false;
  42.         
  43.         //计算直线与直线的交点
  44.         Vector2 outPoint = Vector2.zero;
  45.         if (LineIntersectPoint(segment1Start,segment1End,segment2Start,segment2End,out outPoint))
  46.         {
  47.             points.Add(outPoint);
  48.             return true;
  49.         }
  50.         
  51.         /*********用此种方式也可*************************/
  52.         //1.先求交点
  53.         //2.在计算点是否在两线段上
  54.         /*
  55.         if (LineIntersectPoint(segment1Start,segment1End,segment2Start,segment2End,out outPoint))
  56.         {
  57.             if (IsPointOnLine(outPoint,segment1Start,segment1End) && IsPointOnLine(outPoint,segment2Start,segment2End))
  58.             {
  59.                 points.Add(outPoint);
  60.                 return true;
  61.             }
  62.         }*/
  63.         
  64.         return false;
  65.     }

13、射线与射线是否相交，以及交点

1）判断射线所在的直线是否相交
2）判断点是否在两条射线上

  1.     /// <summary>
  2.     /// 射线是否相交
  3.     /// </summary>
  4.     /// <param name="ray1Start"></param>
  5.     /// <param name="ray1Dir"></param>
  6.     /// <param name="ray2Start"></param>
  7.     /// <param name="ray2Dir"></param>
  8.     /// <returns></returns>
  9.     public static bool IsRayIntersect(Vector2 ray1Start, Vector2 ray1Dir, Vector2 ray2Start, Vector2 ray2Dir,out Vector2 point)
  10.     {
  11.         //先计算两条直线是否相交
  12.         if (!LineIntersectPoint(ray1Start,ray1Start+ray1Dir * 1,ray2Start,ray2Start+ray2Dir*1,out point))
  13.             return false;
  14.         if (Vector2.Dot((point - ray1Start).normalized, ray1Dir.normalized) < 0) return false;
  15.         if (Vector2.Dot((point - ray2Start).normalized, ray2Dir.normalized) < 0) return false;
  16.         return true;
  17.     }

14、射线与线段是否相交，以及交点
1）所在直线是否相交
2）点是否在射线以及直线上

  1.     /// <summary>
  2.     /// 射线与线段是否相交
  3.     /// </summary>
  4.     /// <param name="rayStart"></param>
  5.     /// <param name="rayDir"></param>
  6.     /// <param name="segmentStart"></param>
  7.     /// <param name="segmentEnd"></param>
  8.     /// <returns></returns>
  9.     public static bool IsRaySegmentIntersect(Vector2 rayStart,Vector2 rayDir,Vector2 segmentStart,Vector2 segmentEnd,out Vector2 point)
  10.     {
  11.         //先计算两条直线是否相交
  12.         if (!LineIntersectPoint(rayStart,rayStart+rayDir * 1,segmentStart,segmentEnd,out point))
  13.             return false;
  14.         //判断交点的位置是否在射线上 方向相同可以确定点在射线上
  15.         if (Vector2.Dot((point - rayStart).normalized, rayDir.normalized) < 0) return false;
  16.         //点是否在线段上
  17.         if (!IsPointOnSegment2(point,segmentStart, segmentEnd)) return false;
  18.         return true;
  19.     }

15.点围绕另一点旋转指定角度

2维向量旋转

需要注意的是，需要将角度转为弧度制进行计算(角度与弧度)

  1.     /// <summary>
  2.     /// 点绕另一个点进行旋转
  3.     /// </summary>
  4.     /// <param name="originPoint"></param>
  5.     /// <param name="point"></param>
  6.     /// <param name="angle"></param>
  7.     /// <returns></returns>
  8.     public static Vector2 PointRoationOnPoint(Vector2 originPoint, Vector2 point, float angle)
  9.     {
  10.         if (originPoint == point) return originPoint;
  11.         Vector2 resultPoint = Vector2.zero;
  12.         Vector2  v= (point - originPoint).normalized;
  13.         angle *= Mathf.Deg2Rad;
  14.         resultPoint.x = v.x * Mathf.Cos(angle) - v.y * Mathf.Sin(angle);
  15.         resultPoint.y = v.x * Mathf.Sin(angle) + v.y * Mathf.Cos(angle);
  16.         return resultPoint * Vector2.Distance(originPoint,point) + originPoint ;
  17.     }
  18.     
  19.       /// <summary>
  20.     /// 点集合绕点旋转
  21.     /// </summary>
  22.     /// <param name="points"></param>
  23.     /// <param name="point"></param>
  24.     /// <param name="angle"></param>
  25.     /// <returns></returns>
  26.     public static List<Vector2> PointsRoationOnPoint(List<Vector2> points, Vector2 point, float angle)
  27.     {
  28.         List<Vector2> resultPoints = new List<Vector2>();
  29.         if (points == null) return resultPoints;
  30.         for (int i = 0; i < points.Count; i++)
  31.         {
  32.             Vector2 nPoint = PointRoationOnPoint(point,points[i],angle);
  33.             resultPoints.Add(nPoint);
  34.         }
  35.         return resultPoints;
  36.     }

16、点是否在任意多变内

判断点是否在任意多变内部的几种方法
射线法：
1）求出多边形所在矩形，判断点是否在矩形内
2）点是否在多边形顶点或边上
3）以当前点做一条水平射线，计算该射线与多边形线段的相交数量，如果为奇数则点在多边形内部

  1.     /// <summary>
  2.     /// 点是否在任意多边形内部
  3.     /// </summary>
  4.     /// <param name="point"></param>
  5.     /// <param name="polygon"></param>
  6.     /// <returns>-1：不在多边形内 0：在多边形上 1:多边形内 </returns>
  7.     public static int IsPointInAnyPolygon(Vector2 point, List<Vector2> polygon)
  8.     {
  9.         //顶点数量小于3，则无法形成多边形
  10.         if (polygon.Count < 3) return -1;
  11.  
  12.         //1.先获取多边形所在矩形范围内
  13.  
  14.         Vector2 rectMin = polygon[0], rectMax = polygon[0];
  15.         for (int i = 1; i < polygon.Count; i++)
  16.         {
  17.             if (polygon[i].x < rectMin.x) rectMin.x = polygon[i].x;
  18.             if (polygon[i].y < rectMin.y) rectMin.y = polygon[i].y;
  19.             if (polygon[i].x > rectMax.x) rectMax.x = polygon[i].x;
  20.             if (polygon[i].y > rectMax.y) rectMax.y = polygon[i].y;
  21.         }
  22.         if (point.x < rectMin.x || point.y < rectMin.y || point.x > rectMax.x || point.y > rectMax.y) return -1;
  23.         //2.射线相交点计算
  24.         int intersectCount = 0;
  25.         for (int i = 0; i < polygon.Count; i++)
  26.         {
  27.             int nextIndex = i + 1;
  28.             if (nextIndex >= polygon.Count)
  29.                 nextIndex = 0;
  30.             //目标在顶点上
  31.             if (polygon[i] == point || polygon[nextIndex] == point)
  32.                 return 0;
  33.             //目标在线段上
  34.             if (IsPointOnSegment2(point, polygon[i], polygon[nextIndex]))
  35.                 return 0;
  36.             Vector2 intersectPoint;
  37.             //射线与线段相交
  38.             if (IsRaySegmentIntersect(point,Vector2.right,polygon[i],polygon[nextIndex],out intersectPoint))
  39.             {
  40.                 //如果相交为线段的顶点，则需要增加2，因为在同一点进入，又在同一个点出去
  41.                 if (intersectPoint == polygon[i] || intersectPoint == polygon[nextIndex])
  42.                     intersectCount += 2;
  43.                 else
  44.                     intersectCount += 1;
  45.             }
  46.         }
  47.         return intersectCount % 2 == 1 ? 1:-1;
  48.     }

17、点是否在椭圆内

c# 实现求一个点是否在一个面内

如果P（x，y）是否在椭圆内，则小于等于1

焦点在x轴上时，长轴为2a，短轴为2b，圆方程为x^2/a^2+y^2/b^2=1
焦点在y轴上时，长轴为2a，短轴为2b，圆方程为x^2/b^2+y^2/a^2=1
笔误

  1.     /// <summary>
  2.     /// 点是否在椭圆内
  3.     /// </summary>
  4.     /// <param name="point">目标点</param>
  5.     /// <param name="xAxis">长轴半径</param>
  6.     /// <param name="yAxis">短轴半径</param>
  7.     /// <returns></returns>
  8.     private bool PointIsInEllipse(Vector2 point,float xAxis,float yAxis)
  9.     {
  10.         return (point.x * point.x) / (xAxis  * xAxis ) + (point.y * point.y) / (yAxis  * yAxis )<=1;
  11.     }

18、直线与椭圆的交点计算

直线与椭圆相交求交点

  1.   /// <summary>
  2.         /// 线段和椭圆弧的交点
  3.         /// </summary>
  4.         /// <param name="line">线段对象</param>
  5.         /// <param name="ht">存储交点和error信息</param>
  6.         /// <returns>返回交点和error信息</returns>
  7.         internal static Hashtable LineIntersectEllipticArc(Line line, Hashtable ht)
  8.         {
  9.             //线段的终点
  10.             Vector2 LineendPoint = line.endPoint;
  11.             //线段的起点
  12.             Vector2 LinestartPoint = line.startPoint;
  13.             //椭圆弧的长轴的一半
  14.             double maxAxis = 262.39051820125013 / 2;
  15.             //椭圆弧的短轴一半
  16.             double minAxis = 135.76528231694766 / 2;
  17.             //椭圆弧的起点
  18.             //椭圆弧的起始角度 
  19.             double startAngle = DegreeToRadian(132.0438345714015);
  20.             //椭圆弧的终点
  21.             //椭圆弧的终止角度 //默认设置为90度对应的弧度
  22.             double endAngle = DegreeToRadian(258.13766538237763);
  23.             //椭圆弧的圆心
  24.             Vector2 center = new Vector2(17.7894639270817, 15.0254309579905);
  25.             //设置原点坐标(0,0)
  26.             Vector2 centerZero = new Vector2(0, 0);
  27.             //椭圆弧的导入角度'
  28.             double angle = DegreeToRadian(191.75357833501226);
  29.             //将直线顺时针旋转angle度
  30.             Vector2[] ve = Anticlockwise(LineendPoint, LinestartPoint, center, angle);
  31.             //假设默认交点坐标
  32.             Vector2 ptInter1 = new Vector2(0, 0);
  33.             Vector2 ptInter2 = new Vector2(0, 0);
  34.             //直线和椭圆的交点坐标
  35.             LineIntersectEllipse(MoveOne(ve[0], center), MoveOne(ve[1], center), maxAxis, minAxis, ref ptInter1, ref ptInter2);
  36.             //用于存储交点
  37.             List<Vector2> node = new List<Vector2>();
  38.             //用于判断是否有交点
  39.             bool judgeNode = false;
  40.             //存储的版本号
  41.             int version = 0;
  42.             double a = NormalizeRadianAngle(startAngle);
  43.             double b = NormalizeRadianAngle(endAngle);
  44.             if (Zero(ptInter1))
  45.             {
  46.                 JudgeDotQualified(centerZero, ptInter1, a, b, node);
  47.                 if (node.Count == 1)
  48.                 {
  49.                     if (node[0] != null)
  50.                     {
  51.                         //表示第一次有一个值
  52.                         //将交点逆时针旋转
  53.                         Vector2[] ve1 = Anticlockwise(ptInter1, ptInter2, centerZero, angle, false);
  54.                         //再将交点平移得到最后真正的交点
  55.                         ve1[0] = MoveTwo(ve1[0], center);
  56.                         node[0] = ve1[0];
  57.                         version = 1;
  58.                     }
  59.                 }
  60.             }
  61.             if (Zero(ptInter2))
  62.             {
  63.                 if (version == 0)
  64.                 {
  65.                     JudgeDotQualified(centerZero, ptInter2, a, b, node);
  66.                     if (node.Count == 1)
  67.                     {
  68.                         if (node[0] != null)
  69.                         {
  70.                             //表示第一次没有一个值
  71.                             //将交点逆时针旋转
  72.                             Vector2[] ve1 = Anticlockwise(ptInter1, ptInter2, centerZero, angle, false);
  73.                             //再将交点平移得到最后真正的交点
  74.                             ve1[1] = MoveTwo(ve1[1], center);
  75.                             node[0] = ve1[1];
  76.                         }
  77.                     }
  78.                 }
  79.                 else if (version == 1)
  80.                 {
  81.                     JudgeDotQualified(centerZero, ptInter2, a, b, node);
  82.                     if (node.Count == 2)
  83.                     {
  84.                         if (node[1] != null)
  85.                         {
  86.                             //表示第一次有一个值
  87.                             //将交点逆时针旋转
  88.                             Vector2[] ve1 = Anticlockwise(ptInter1, ptInter2, centerZero, angle, false);
  89.                             //再将交点平移得到最后真正的交点
  90.                             ve1[1] = MoveTwo(ve1[1], center);
  91.                             node[1] = ve1[1];
  92.                         }
  93.                     }
  94.                 }
  95.             }
  96.             ht.Add("node", node);
  97.             return ht;
  98.         }
  99.    /// <summary>
  100.         /// 角度转弧度
  101.         /// </summary>
  102.         /// <param name="angle">角度</param>
  103.         /// <returns>弧度</returns>
  104.         public static double DegreeToRadian(double angle)
  105.         {
  106.             return ((angle * System.Math.PI) / 180.0);
  107.         }
  108.         public const double EPSILON = 1E-12;
  109.  public static bool IsEqual(double x, double y, double epsilon = EPSILON)
  110.         {
  111.             return IsEqualZero(x - y, epsilon);
  112.         }
  113.         public static bool IsEqualZero(double x, double epsilon = EPSILON)
  114.         {
  115.             return (System.Math.Abs(x) < epsilon);
  116.         }
  117.         /// <summary>
  118.         /// 点的绕椭圆弧弧心旋转
  119.         /// </summary>
  120.         /// <param name="LineendPoint">线段终点</param>
  121.         /// <param name="LinestartPoint">线段起点</param>
  122.         /// <param name="center">椭圆弧弧心</param>
  123.         /// <param name="angle">椭圆弧的导入角度'</param>
  124.         /// /// <param name="isClockwise">顺逆旋转，默认为顺时针旋转</param>
  125.         internal static Vector2[] Anticlockwise(Vector2 LineendPoint, Vector2 LinestartPoint, Vector2 center, double angle, bool isClockwise = true)
  126.         {
  127.             Vector2[] ve = new Vector2[2];
  128.             if (isClockwise)
  129.             {
  130.                 angle = -angle;
  131.             }
  132.             double cos = System.Math.Cos(angle);
  133.             double sin = System.Math.Sin(angle);
  134.             if (IsEqual(cos, 0))
  135.             {
  136.                 cos = 0;
  137.             }
  138.             if (IsEqual(sin, 0))
  139.             {
  140.                 sin = 0;
  141.             }
  142.             double x = ((LineendPoint.x - center.x) * cos - (LineendPoint.y - center.y) * sin + center.x);
  143.             double y = ((LineendPoint.x - center.x) * sin + (LineendPoint.y - center.y) * cos + center.y);
  144.             ve[0].x = x;
  145.             ve[0].y = y;
  146.             double x1 = ((LinestartPoint.x - center.x) * cos - (LinestartPoint.y - center.y) * sin + center.x);
  147.             double y1 = ((LinestartPoint.x - center.x) * sin + (LinestartPoint.y - center.y) * cos + center.y);
  148.             ve[1].x = x1;
  149.             ve[1].y = y1;
  150.             return ve;
  151.         }
  152.         /// <summary>
  153.         /// 第一次平移
  154.         /// </summary>
  155.         /// <param name="dot">交点坐标</param>
  156.         /// <param name="center">圆心坐标</param>
  157.         /// <returns>返回平移后的点坐标</returns>
  158.         internal static Vector2 MoveOne(Vector2 dot, Vector2 center)
  159.         {
  160.             Vector2 returnDot = new Vector2();
  161.             if (center.x >= 0 && center.y >= 0)
  162.             {
  163.                 //圆心在第一象限
  164.                 returnDot.x = dot.x - center.x;
  165.                 returnDot.y = dot.y - center.y;
  166.             }
  167.             else if (center.x <= 0 && center.y >= 0)
  168.             {
  169.                 //圆心在第二象限
  170.                 returnDot.x = dot.x + center.x;
  171.                 returnDot.y = dot.y - center.y;
  172.             }
  173.             else if (center.x <= 0 && center.y <= 0)
  174.             {
  175.                 //圆心在第三象限
  176.                 returnDot.x = dot.x + center.x;
  177.                 returnDot.y = dot.y + center.y;
  178.             }
  179.             else if (center.x >= 0 && center.y <= 0)
  180.             {  //圆心在第四象限
  181.                 returnDot.x = dot.x - center.x;
  182.                 returnDot.y = dot.y + center.y;
  183.             }
  184.             return returnDot;
  185.         }
  186.         /// <summary>
  187.         /// 第二次平移
  188.         /// </summary>
  189.         /// <param name="dot">点坐标</param>
  190.         /// <param name="center">圆心坐标</param>
  191.         /// <returns>返回平移后的点</returns>
  192.         internal static Vector2 MoveTwo(Vector2 dot, Vector2 center)
  193.         {
  194.             Vector2 returnDot = new Vector2();
  195.             if (center.x >= 0 && center.y >= 0)
  196.             {
  197.                 //圆心在第一象限
  198.                 returnDot.x = dot.x + center.x;
  199.                 returnDot.y = dot.y + center.y;
  200.             }
  201.             else if (center.x <= 0 && center.y >= 0)
  202.             {
  203.                 //圆心在第二象限
  204.                 returnDot.x = dot.x - center.x;
  205.                 returnDot.y = dot.y + center.y;
  206.             }
  207.             else if (center.x <= 0 && center.y <= 0)
  208.             {
  209.                 //圆心在第三象限
  210.                 returnDot.x = dot.x - center.x;
  211.                 returnDot.y = dot.y - center.y;
  212.             }
  213.             else if (center.x >= 0 && center.y <= 0)
  214.             {  //圆心在第四象限
  215.                 returnDot.x = dot.x + center.x;
  216.                 returnDot.y = dot.y - center.y;
  217.             }
  218.             return returnDot;
  219.         }
  220.         /// <summary>
  221.         /// 判断点是否为(0,0)
  222.         /// </summary>
  223.         /// <param name="dot">交点</param>
  224.         /// <returns>是(0，0)返回false</returns>
  225.         internal static bool Zero(Vector2 dot)
  226.         {
  227.             if (dot.x == 0)
  228.             {
  229.                 if (dot.y == 0)
  230.                 {
  231.                     return false;
  232.                 }
  233.                 else
  234.                 {
  235.                     return true;
  236.                 }
  237.             }
  238.             else
  239.             {
  240.                 return true;
  241.             }
  242.         }
  243.         /// <summary>
  244.         /// 规整化弧度
  245.         /// 返回值范围:[0, 2*PI)
  246.         /// </summary>
  247.         internal static double NormalizeRadianAngle(double rad)
  248.         {
  249.             double value = rad % (2 * System.Math.PI);
  250.             if (value < 0)
  251.                 value += 2 * System.Math.PI;
  252.             return value;
  253.         }

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号