我已经检查了这个问题，但答案对我来说非常大：
是否有任何 .NET 方法可以知道由两点定义的线是否与矩形相交？
public bool Intersects(Point a, Point b, Rectangle r)
{
// return true if the line intersects the rectangle
// false otherwise
}
提前致谢。
问问题
28950 次
8 回答
30
public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
{
return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
(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;
}
于 2011-04-01T14:15:08.937 回答
14
不幸的是，错误的答案被投了赞成票。计算实际的交点非常昂贵，您只需要比较。要查找的关键字是“Line Clipping”（http://en.wikipedia.org/wiki/Line_clipping）。当您想要快速拒绝时，维基百科推荐 Cohen-Sutherland 算法 ( http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland )，这可能是最常见的情况。维基百科页面上有一个 C++ 实现。如果您对实际剪裁线不感兴趣，则可以跳过大部分内容。@Johann 的答案看起来和那个算法很像，但是我没有仔细看。
于 2014-05-13T20:30:22.927 回答
8
蛮力算法...
首先检查矩形是在线端点的左侧还是右侧：
- 建立线端点的最左边和最右边的 X 值：XMIN 和 XMAX
- 如果 Rect.Left > XMAX，则没有交集。
- 如果 Rect.Right < XMIN，则没有交集。
然后，如果上述内容不足以排除相交，请检查矩形是在线端点上方还是下方：
- 建立线端点的最高和最低 Y 值：YMAX 和 YMIN
- 如果 Rect.Bottom > YMAX，则没有交集。
- 如果 Rect.Top < YMIN，则没有交集。
然后，如果以上不足以排除相交，您需要检查直线的方程y = m * x + b，以查看矩形是否在线上方：
- 在 Rect.Left 和 Rect.Right 处建立直线的 Y 值：LINEYRECTLEFT 和 LINEYRECTRIGHT
- 如果 Rect.Bottom > LINEYRECTRIGHT && Rect.Bottom > LINEYRECTLEFT，则没有交集。
然后，如果以上内容不足以排除相交，则需要检查矩形是否在该线下方：
- 如果 Rect.Top < LINEYRECTRIGHT && Rect.Top < LINEYRECTLEFT，则没有交集。
然后，如果你到了这里：
- 路口。
注意我确信有一个更优雅的代数解决方案，但是用笔和纸以几何方式执行这些步骤很容易遵循。
一些未经测试和未编译的代码：
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;
}
于 2011-04-01T14:29:10.093 回答
6
此代码具有更好的性能：
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(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
}
于 2017-02-24T09:41:22.497 回答
4
我采用了 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。我会注意到，起初我编写了自己的例程来检查渐变中的每个点，并且我尽我所能最大限度地提高性能，但这马上要快得多。
于 2012-11-23T09:48:24.710 回答
0
您可以调用没有简单的预定义 .NET 方法来完成此操作。但是，使用 Win32 API，有一种非常简单的方法可以做到这一点（在实现意义上很容易，性能不是强项）：LineDDA
BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)
该函数为要绘制的线的每个像素调用回调函数。在此功能中，您可以检查像素是否在矩形内 - 如果找到，则它相交。
正如我所说，这不是最快的解决方案，但很容易实现。要在 C# 中使用它，您当然需要从 gdi32.dll ddlimport 它。
[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);
于 2011-04-01T14:10:15.560 回答
0
最简单的计算几何技术是遍历多边形的各个部分，看看它是否与其中任何一个相交，因为它也必须与多边形相交。
这种方法（以及大部分 CG）的唯一警告是我们必须小心边缘情况。如果线在某个点穿过矩形怎么办 - 我们是否将其视为交叉点？执行时要小心。
编辑：线相交线段计算的典型工具是LeftOf(Ray, Point)测试，如果该点位于光线的左侧，则返回。给定一条线l（我们将其用作射线）和一个包含点a和b的线段，如果一个点在左侧而一个点不在，则该线与该线段相交：
(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))
同样，当点在线时，您需要注意边缘情况，但这取决于您希望如何实际定义交点。
于 2011-04-01T14:10:32.340 回答
0
对于 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(a.x, b.x);
var maxX = Math.Max(a.x, b.x);
var minY = Math.Min(a.y, b.y);
var maxY = Math.Max(a.y, b.y);
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<float, float> yForX = x => a.y - (x - a.x) * ((a.y - b.y) / (b.x - a.x));
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;
}
}
}
于 2018-02-01T07:01:27.317 回答