如何知道线是否与矩形相交
我已经查看了这个问题，但答案对我来说非常大：
如何知道一条线是否与C＃中的平面相交？ – 基本2D几何
是否有任何.NET方法可以知道由两个点定义的直线是否与矩形相交？
public bool Intersects(Point a, Point b, Rectangle r) { // return true if the line intersects the rectangle // false otherwise } 提前致谢。
public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r) { return LineIntersectsLine(p1, p2, new Point(rX, rY), new Point(rX + r.Width, rY)) || LineIntersectsLine(p1, p2, new Point(rX + r.Width, rY), new Point(rX + r.Width, rY + r.Height)) || LineIntersectsLine(p1, p2, new Point(rX + r.Width, rY + r.Height), new Point(rX, rY + r.Height)) || LineIntersectsLine(p1, p2, new Point(rX, rY + r.Height), new Point(rX, rY)) || (r.Contains(p1) && r.Contains(p2)); } private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2) { float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y); float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X); if( d == 0 ) { return false; } float r = q / d; q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y); float s = q / d; if( r < 0 || r > 1 || s < 0 || s > 1 ) { return false; } return true; }
不幸的是，错误的答案已被否决。 计算实际交叉点的成本太高，您只需要进行比较。 要查找的关键字是“Line Clipping”（ http://en.wikipedia.org/wiki/Line_clipping ）。 当您想要快速拒绝时，维基百科推荐使用Cohen-Sutherland算法（ http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland ），这可能是最常见的情况。 维基百科页面上有一个C ++实现。 如果您对实际剪切线不感兴趣，可以跳过大部分内容。 @Johann的答案看起来与该算法非常相似，但我没有详细研究它。
蛮力算法……
首先检查rect是否在行端点的左侧或右侧：
- 建立线端点的最左边和最右边的X值：XMIN和XMAX
- 如果Rect.Left> XMAX，则没有交集。
- 如果Rect.Right
然后，如果上述内容不足以排除交集，请检查rect是否在行端点之上或之下：
- 建立线端点的最高和最低Y值：YMAX和YMIN
- 如果Rect.Bottom> YMAX，则没有交集。
- 如果Rect.Top
然后，如果以上不足以排除交点，则需要检查线的方程y = m * x + b ，以查看矩形是否在线上方：
- 在Rect.Left和Rect.Right上建立线的Y值：LINEYRECTLEFT和LINEYRECTRIGHT
- 如果Rect.Bottom> LINEYRECTRIGHT && Rect.Bottom> LINEYRECTLEFT，则没有交集。
然后，如果以上不足以排除交集，则需要检查rect是否在行下方：
- 如果Rect.Top
然后，如果你到这里：
- 路口。
NB我确信有更优雅的代数解决方案，但用笔和纸几何方式执行这些步骤很容易理解。
一些未经测试和未编译的代码：
public struct Line { public int XMin { get { ... } } public int XMax { get { ... } } public int YMin { get { ... } } public int YMax { get { ... } } public Line(Point a, Point b) { ... } public float CalculateYForX(int x) { ... } } public bool Intersects(Point a, Point b, Rectangle r) { var line = new Line(a, b); if (r.Left > line.XMax || r.Right < line.XMin) { return false; } if (r.Top < line.YMin || r.Bottom > line.YMax) { return false; } var yAtRectLeft = line.CalculateYForX(r.Left); var yAtRectRight = line.CalculateYForX(r.Right); if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight) { return false; } if (r.Top < yAtRectLeft && r.Top < yAtRectRight) { return false; } return true; }
我采用了HABJAN的解决方案，该解决方案运行良好，并将其转换为Objective-C。 Objective-C代码如下：
bool LineIntersectsLine(CGPoint l1p1, CGPoint l1p2, CGPoint l2p1, CGPoint l2p2) { CGFloat q = (l1p1.y - l2p1.y) * (l2p2.x - l2p1.x) - (l1p1.x - l2p1.x) * (l2p2.y - l2p1.y); CGFloat d = (l1p2.x - l1p1.x) * (l2p2.y - l2p1.y) - (l1p2.y - l1p1.y) * (l2p2.x - l2p1.x); if( d == 0 ) { return false; } float r = q / d; q = (l1p1.y - l2p1.y) * (l1p2.x - l1p1.x) - (l1p1.x - l2p1.x) * (l1p2.y - l1p1.y); float s = q / d; if( r < 0 || r > 1 || s < 0 || s > 1 ) { return false; } return true; } bool LineIntersectsRect(CGPoint p1, CGPoint p2, CGRect r) { return LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y)) || LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height)) || LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y + r.size.height)) || LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y)) || (CGRectContainsPoint(r, p1) && CGRectContainsPoint(r, p2)); }
非常感谢HABJAN。 我会注意到，起初我编写了我自己的例程，它检查了渐变中的每个点，并且我做了我能做的所有事情以最大化性能，但这立即快得多。
此代码具有更好的性能：
public static bool SegmentIntersectRectangle( double rectangleMinX, double rectangleMinY, double rectangleMaxX, double rectangleMaxY, double p1X, double p1Y, double p2X, double p2Y) { // Find min and max X for the segment double minX = p1X; double maxX = p2X; if (p1X > p2X) { minX = p2X; maxX = p1X; } // Find the intersection of the segment's and rectangle's x-projections if (maxX > rectangleMaxX) { maxX = rectangleMaxX; } if (minX < rectangleMinX) { minX = rectangleMinX; } if (minX > maxX) // If their projections do not intersect return false { return false; } // Find corresponding min and max Y for min and max X we found before double minY = p1Y; double maxY = p2Y; double dx = p2X - p1X; if (Math.Abs(dx) > 0.0000001) { double a = (p2Y - p1Y)/dx; double b = p1Y - a*p1X; minY = a*minX + b; maxY = a*maxX + b; } if (minY > maxY) { double tmp = maxY; maxY = minY; minY = tmp; } // Find the intersection of the segment's and rectangle's y-projections if (maxY > rectangleMaxY) { maxY = rectangleMaxY; } if (minY < rectangleMinY) { minY = rectangleMinY; } if (minY > maxY) // If Y-projections do not intersect return false { return false; } return true; }
您还可以在JS演示中查看它的工作原理： http ： //jsfiddle.net/77eej/2/
如果你有两个Points和Rect，你可以像这样调用这个函数：
public static bool LineIntersectsRect(Point p1, Point p2, Rect r) { return SegmentIntersectRectangle(rX, rY, rX + r.Width, rY + r.Height, p1.X, p1.Y, p2.X, p2.Y); }
没有简单的预定义.NET方法可以调用来实现它。 但是，使用Win32 API，有一种非常简单的方法（在实现方面很容易，性能不是强项）： LineDDA
BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)
此函数为要绘制的行的每个像素调用回调函数。 在此函数中，您可以检查像素是否在矩形内 – 如果找到一个，则它会相交。
正如我所说，这不是最快的解决方案，但很容易实现。 要在C＃中使用它，您当然需要从gdi32.dll中删除它。
[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);
最简单的计算几何技术是遍历多边形的各个部分，看它是否与它们中的任何一个相交，因为它必须也与多边形相交。
这种方法（以及大部分CG）的唯一警告是我们必须小心边缘情况。 如果线在一个点处穿过矩形怎么办？我们是否将其视为交叉点？ 在实施时要小心。
编辑 ：线 – 交叉 – 线段计算的典型工具是LeftOf(Ray, Point)测试，如果该点位于光线的左侧，则返回该测试。 给定一条线l （我们用作光线）和一条包含点a和b的线段，如果一个点在左边而另一个点不在，则该线与线段相交：
(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))
同样，当点在线上时，您需要注意边缘情况，但取决于您希望如何实际定义交点。
对于Unity（颠倒y！）。 这样可以解决其他方法存在的除零问题：
using System; using UnityEngine; namespace Util { public static class Math2D { public static bool Intersects(Vector2 a, Vector2 b, Rect r) { var minX = Math.Min(ax, bx); var maxX = Math.Max(ax, bx); var minY = Math.Min(ay, by); var maxY = Math.Max(ay, by); if (r.xMin > maxX || r.xMax < minX) { return false; } if (r.yMin > maxY || r.yMax < minY) { return false; } if (r.xMin < minX && maxX < r.xMax) { return true; } if (r.yMin < minY && maxY < r.yMax) { return true; } Func yForX = x => ay - (x - ax) * ((ay - by) / (bx - ax)); var yAtRectLeft = yForX(r.xMin); var yAtRectRight = yForX(r.xMax); if (r.yMax < yAtRectLeft && r.yMax < yAtRectRight) { return false; } if (r.yMin > yAtRectLeft && r.yMin > yAtRectRight) { return false; } return true; } } }