两条线的交叉算法？
我有2行。 两条线都包含它们的2点X和Y.这意味着它们都有长度。
我看到2个公式，一个使用决定因素，一个使用普通代数。 哪个是最有效的计算方法，公式是什么样的？
我在代码中使用矩阵很困难。
这是我到目前为止，它是否更有效？
public static Vector3 Intersect(Vector3 line1V1, Vector3 line1V2, Vector3 line2V1, Vector3 line2V2) { //Line1 float A1 = line1V2.Y - line1V1.Y; float B1 = line1V2.X - line1V1.X; float C1 = A1*line1V1.X + B1*line1V1.Y; //Line2 float A2 = line2V2.Y - line2V1.Y; float B2 = line2V2.X - line2V1.X; float C2 = A2 * line2V1.X + B2 * line2V1.Y; float det = A1*B2 - A2*B1; if (det == 0) { return null;//parallel lines } else { float x = (B2*C1 - B1*C2)/det; float y = (A1 * C2 - A2 * C1) / det; return new Vector3(x,y,0); } } 假设您有两行formsAx + By = C ，您可以很容易地找到它：
float delta = A1 * B2 - A2 * B1; if (delta == 0) throw new ArgumentException("Lines are parallel"); float x = (B2 * C1 - B1 * C2) / delta; float y = (A1 * C2 - A2 * C1) / delta;
从这里拉出来
我最近回到纸面上找到使用基本代数解决这个问题的方法。 只需求解两条线形成的方程，如果存在有效解，那么就有一个交点。
检查此Github存储库以获取扩展实现，处理双重和测试的潜在精度问题。
public struct Line { public double x1 { get; set; } public double y1 { get; set; } public double x2 { get; set; } public double y2 { get; set; } } public struct Point { public double x { get; set; } public double y { get; set; } } public class LineIntersection { // Returns Point of intersection if do intersect otherwise default Point (null) public static Point FindIntersection(Line lineA, Line lineB, double tolerance = 0.001) { double x1 = lineA.x1, y1 = lineA.y1; double x2 = lineA.x2, y2 = lineA.y2; double x3 = lineB.x1, y3 = lineB.y1; double x4 = lineB.x2, y4 = lineB.y2; // equations of the form x = c (two vertical lines) if (Math.Abs(x1 - x2) < tolerance && Math.Abs(x3 - x4) < tolerance && Math.Abs(x1 - x3) < tolerance) { throw new Exception("Both lines overlap vertically, ambiguous intersection points."); } //equations of the form y=c (two horizontal lines) if (Math.Abs(y1 - y2) < tolerance && Math.Abs(y3 - y4) < tolerance && Math.Abs(y1 - y3) < tolerance) { throw new Exception("Both lines overlap horizontally, ambiguous intersection points."); } //equations of the form x=c (two vertical lines) if (Math.Abs(x1 - x2) < tolerance && Math.Abs(x3 - x4) < tolerance) { return default(Point); } //equations of the form y=c (two horizontal lines) if (Math.Abs(y1 - y2) < tolerance && Math.Abs(y3 - y4) < tolerance) { return default(Point); } //general equation of line is y = mx + c where m is the slope //assume equation of line 1 as y1 = m1x1 + c1 //=> -m1x1 + y1 = c1 ----(1) //assume equation of line 2 as y2 = m2x2 + c2 //=> -m2x2 + y2 = c2 -----(2) //if line 1 and 2 intersect then x1=x2=x & y1=y2=y where (x,y) is the intersection point //so we will get below two equations //-m1x + y = c1 --------(3) //-m2x + y = c2 --------(4) double x, y; //lineA is vertical x1 = x2 //slope will be infinity //so lets derive another solution if (Math.Abs(x1 - x2) < tolerance) { //compute slope of line 2 (m2) and c2 double m2 = (y4 - y3) / (x4 - x3); double c2 = -m2 * x3 + y3; //equation of vertical line is x = c //if line 1 and 2 intersect then x1=c1=x //subsitute x=x1 in (4) => -m2x1 + y = c2 // => y = c2 + m2x1 x = x1; y = c2 + m2 * x1; } //lineB is vertical x3 = x4 //slope will be infinity //so lets derive another solution else if (Math.Abs(x3 - x4) < tolerance) { //compute slope of line 1 (m1) and c2 double m1 = (y2 - y1) / (x2 - x1); double c1 = -m1 * x1 + y1; //equation of vertical line is x = c //if line 1 and 2 intersect then x3=c3=x //subsitute x=x3 in (3) => -m1x3 + y = c1 // => y = c1 + m1x3 x = x3; y = c1 + m1 * x3; } //lineA & lineB are not vertical //(could be horizontal we can handle it with slope = 0) 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; //solving equations (3) & (4) => x = (c1-c2)/(m2-m1) //plugging x value in equation (4) => y = c2 + m2 * x x = (c1 - c2) / (m2 - m1); y = c2 + m2 * x; //verify by plugging intersection point (x, y) //in orginal equations (1) & (2) to see if they intersect //otherwise x,y values will not be finite and will fail this check if (!(Math.Abs(-m1 * x + y - c1) < tolerance && Math.Abs(-m2 * x + y - c2) < tolerance)) { return default(Point); } } //x,y can intersect outside the line segment since line is infinitely long //so finally check if x, y is within both the line segments if (IsInsideLine(lineA, x, y) && IsInsideLine(lineB, x, y)) { return new Point { x = x, y = y }; } //return default null (no intersection) return default(Point); } // Returns true if given point(x,y) is inside the given line segment private static bool IsInsideLine(Line line, double x, double y) { return (x >= line.x1 && x <= line.x2 || x >= line.x2 && x <= line.x1) && (y >= line.y1 && y <= line.y2 || y >= line.y2 && y <= line.y1); } }
如何找到两条线/段/光线与矩形的交点
public class LineEquation{ public LineEquation(Point start, Point end){ Start = start; End = end; IsVertical = Math.Abs(End.X - start.X) < 0.00001f; M = (End.Y - Start.Y)/(End.X - Start.X); A = -M; B = 1; C = Start.Y - M*Start.X; } public bool IsVertical { get; private set; } public double M { get; private set; } public Point Start { get; private set; } public Point End { get; private set; } public double A { get; private set; } public double B { get; private set; } public double C { get; private set; } public bool IntersectsWithLine(LineEquation otherLine, out Point intersectionPoint){ intersectionPoint = new Point(0, 0); if (IsVertical && otherLine.IsVertical) return false; if (IsVertical || otherLine.IsVertical){ intersectionPoint = GetIntersectionPointIfOneIsVertical(otherLine, this); return true; } double delta = A*otherLine.B - otherLine.A*B; bool hasIntersection = Math.Abs(delta - 0) > 0.0001f; if (hasIntersection){ double x = (otherLine.B*C - B*otherLine.C)/delta; double y = (A*otherLine.C - otherLine.A*C)/delta; intersectionPoint = new Point(x, y); } return hasIntersection; } private static Point GetIntersectionPointIfOneIsVertical(LineEquation line1, LineEquation line2){ LineEquation verticalLine = line2.IsVertical ? line2 : line1; LineEquation nonVerticalLine = line2.IsVertical ? line1 : line2; double y = (verticalLine.Start.X - nonVerticalLine.Start.X)* (nonVerticalLine.End.Y - nonVerticalLine.Start.Y)/ ((nonVerticalLine.End.X - nonVerticalLine.Start.X)) + nonVerticalLine.Start.Y; double x = line1.IsVertical ? line1.Start.X : line2.Start.X; return new Point(x, y); } public bool IntersectWithSegementOfLine(LineEquation otherLine, out Point intersectionPoint){ bool hasIntersection = IntersectsWithLine(otherLine, out intersectionPoint); if (hasIntersection) return intersectionPoint.IsBetweenTwoPoints(otherLine.Start, otherLine.End); return false; } public bool GetIntersectionLineForRay(Rect rectangle, out LineEquation intersectionLine){ if (Start == End){ intersectionLine = null; return false; } IEnumerable lines = rectangle.GetLinesForRectangle(); intersectionLine = new LineEquation(new Point(0, 0), new Point(0, 0)); var intersections = new Dictionary(); foreach (LineEquation equation in lines){ Point point; if (IntersectWithSegementOfLine(equation, out point)) intersections[equation] = point; } if (!intersections.Any()) return false; var intersectionPoints = new SortedDictionary(); foreach (var intersection in intersections){ if (End.IsBetweenTwoPoints(Start, intersection.Value) || intersection.Value.IsBetweenTwoPoints(Start, End)){ double distanceToPoint = Start.DistanceToPoint(intersection.Value); intersectionPoints[distanceToPoint] = intersection.Value; } } if (intersectionPoints.Count == 1){ Point endPoint = intersectionPoints.First().Value; intersectionLine = new LineEquation(Start, endPoint); return true; } if (intersectionPoints.Count == 2){ Point start = intersectionPoints.First().Value; Point end = intersectionPoints.Last().Value; intersectionLine = new LineEquation(start, end); return true; } return false; } public override string ToString(){ return "[" + Start + "], [" + End + "]"; } }
完整样本描述[这里] [1]