[CSharpTips]判断两条线段是否相交

  • [CSharpTips]判断两条线段是否相交已关闭评论
  • 30 次浏览
  • A+
所属分类:.NET技术
摘要

判断两条线段是否相交主要用到了通过向量积的正负判断两个向量位置关系向量a×向量b(×为向量叉乘),若结果小于0,表示向量b在向量a的顺时针方向;若结果大于0,表示向量b在向量a的逆时针方向;若等于0,表示向量a与向量b平行

判断两条线段是否相交

主要用到了通过向量积的正负判断两个向量位置关系

向量a×向量b(×为向量叉乘),若结果小于0,表示向量b在向量a的顺时针方向;若结果大于0,表示向量b在向量a的逆时针方向;若等于0,表示向量a与向量b平行

主要代码参考自文末链接,但是他并没有给出跨立检验函数的具体内容,因此补充了一下放在下面

using System; using System.Collections.Generic; using System.Windows; using System.Linq; using System.Text; using System.Threading.Tasks;   namespace lineTest {     class Program     {         public struct Point         {             public double X;             public double Y;              public Point(double x, double y)             {                 X = x;                 Y = y;             }         }          static void Main(string[] args)         {             Point a = new Point(0, 0);             Point b = new Point(100, 100);             Point c = new Point(100,0);             Point d = new Point(50,49);             var result = IsIntersect(a, b, c, d);         }          public static Point? GetIntersection(Point lineAStart, Point lineAEnd, Point lineBStart, Point lineBEnd)         {             double x1 = lineAStart.X, y1 = lineAStart.Y;             double x2 = lineAEnd.X, y2 = lineAEnd.Y;              double x3 = lineBStart.X, y3 = lineBStart.Y;             double x4 = lineBEnd.X, y4 = lineBEnd.Y;              //equations of the form x=c (two vertical lines)             if (x1 == x2 && x3 == x4 && x1 == x3)             {                 return null;             }              //equations of the form y=c (two horizontal lines)             if (y1 == y2 && y3 == y4 && y1 == y3)             {                 return null;             }              //equations of the form x=c (two vertical lines)             if (x1 == x2 && x3 == x4)             {                 return null;             }              //equations of the form y=c (two horizontal lines)             if (y1 == y2 && y3 == y4)             {                 return null;             }             double x, y;              if (x1 == x2)             {                 double m2 = (y4 - y3) / (x4 - x3);                 double c2 = -m2 * x3 + y3;                  x = x1;                 y = c2 + m2 * x1;             }             else if (x3 == x4)             {                 double m1 = (y2 - y1) / (x2 - x1);                 double c1 = -m1 * x1 + y1;                  x = x3;                 y = c1 + m1 * x3;             }             else             {                 //compute slope of line 1 (m1) and c2                 double m1 = (y2 - y1) / (x2 - x1);                 double c1 = -m1 * x1 + y1;                  //compute slope of line 2 (m2) and c2                 double m2 = (y4 - y3) / (x4 - x3);                 double c2 = -m2 * x3 + y3;                  x = (c1 - c2) / (m2 - m1);                 y = c2 + m2 * x;             }              if (IsInsideLine(lineAStart, lineAEnd, x, y) &&                 IsInsideLine(lineBStart, lineBEnd, x, y))             {                 return new Point(x, y);             }              //return default null (no intersection)             return null;         }         private static bool IsInsideLine(Point start, Point end, double x, double y)         {             return ((x >= start.X && x <= end.X)                 || (x >= end.Y && x <= start.Y))                 && ((y >= start.Y && y <= end.Y)                     || (y >= end.Y && y <= start.Y));         }          public static bool IsIntersect(Point p1, Point p2, Point q1, Point q2)         {             //排斥试验,判断p1p2在q1q2为对角线的矩形区之外             if (Math.Max(p1.X, p2.X) < Math.Min(q1.X, q2.X))             {//P1P2中最大的X比Q1Q2中的最小X还要小,说明P1P2在Q1Q2的最左点的左侧,不可能相交。                 return false;             }              if (Math.Min(p1.X, p2.X) > Math.Max(q1.X, q2.X))             {//P1P2中最小的X比Q1Q2中的最大X还要大,说明P1P2在Q1Q2的最右点的右侧,不可能相交。                 return false;             }              if (Math.Max(p1.Y, p2.Y) < Math.Min(q1.Y, q2.Y))             {//P1P2中最大的Y比Q1Q2中的最小Y还要小,说明P1P2在Q1Q2的最低点的下方,不可能相交。                 return false;             }              if (Math.Min(p1.Y, p2.Y) > Math.Max(q1.Y, q2.Y))             {//P1P2中最小的Y比Q1Q2中的最大Y还要大,说明P1P2在Q1Q2的最高点的上方,不可能相交。                 return false;             }              //跨立试验             var crossP1P2Q1 = VectorCross(p1, p2, q1);             var crossP1Q2P2 = VectorCross(p1, q2, p2);             var crossQ1Q2P1 = VectorCross(q1, q2, p1);             var crossQ1P2Q2 = VectorCross(q1, p2, q2);              bool isIntersect = (crossP1P2Q1 * crossP1Q2P2 >= 0) && (crossQ1Q2P1 * crossQ1P2Q2 >= 0);             return isIntersect;         }          private static double VectorCross(Point p1, Point p2, Point p3)         {             Vector vectorP1 = new Vector(p1.X, p1.Y);             Vector vectorP2 = new Vector(p2.X, p2.Y);             Vector vectorP3 = new Vector(p3.X, p3.Y);             Vector vectorP1P2 = Vector.Subtract(vectorP2, vectorP1);             Vector vectorP1P3 = Vector.Subtract(vectorP3, vectorP1);             return Vector.CrossProduct(vectorP1P2, vectorP1P3);         }     } }

 

参考

https://blog.csdn.net/weixin_33973609/article/details/93580049

https://www.cnblogs.com/tuyang1129/p/9390376.html