winforms 如何知道直线是否与矩形相交

ruoxqz4g  于 2022-12-14  发布在  其他
关注(0)|答案(8)|浏览(123)

这个问题我已经查过了,但答案对我来说很大:
How to know if a line intersects a plane in C#? - Basic 2D geometry
是否有任何.NET方法可以知道由两点定义的直线是否与矩形相交?

public bool Intersects(Point a, Point b, Rectangle r)
{
   // return true if the line intersects the rectangle
   // false otherwise
}

先谢谢你。

sqougxex

sqougxex1#

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;
    }
cx6n0qe3

cx6n0qe32#

不幸的是,错误的答案已经被投票通过。计算实际的交点是非常昂贵的,你只需要比较。要寻找的关键字是“线裁剪”(http://en.wikipedia.org/wiki/Line_clipping).维基百科推荐使用Cohen-Sutherland算法(http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland)当您需要快速剔除时,这可能是最常见的情况。在维基百科页面上有一个C++-实现。如果你对实际剪切这行不感兴趣,你可以跳过大部分,@Johann的答案看起来和那个算法非常相似,但是我没有仔细看。

lxkprmvk

lxkprmvk3#

暴力算法......
首先检查矩形是在直线端点的左边还是右边:

  • 建立直线端点最左侧和最右侧的X值:最小和最大
  • 如果Rect.Left〉XMAX,则没有交集。
  • 如果Rect.Right〈XMIN,则没有交集。

然后,如果以上不足以排除相交,请检查矩形是在直线端点之上还是之下:

  • 建立直线端点最顶部和最底部的Y值:YMAX和YMIN
  • 如果Rect.Bottom〉YMAX,则没有交集。
  • 如果Rect.Top〈YMIN,则没有交集。

然后,如果以上不足以排除相交,则需要检查直线y = m * x + b的方程,以查看矩形是否在直线上方:

  • 在矩形左侧和矩形右侧建立直线的Y值:直线矩形左和直线矩形右
  • 如果矩形底部〉行Y矩形右侧&&矩形底部〉行Y矩形左侧,则没有交集。

然后,如果上面的不足以排除相交,你需要检查矩形是否在下面的行:

  • 如果矩形顶部〈LINEYRECTRIGHT &&矩形顶部〈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;
}
x6yk4ghg

x6yk4ghg4#

此代码具有更好的性能:

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/
如果你有两个点和矩形,你可以这样调用这个函数:

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);
    }
gk7wooem

gk7wooem5#

我采用了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。我会注意到,一开始我写了自己的例程来检查梯度沿着的每个点,我做了我能做的一切来最大限度地提高性能,但这马上就快多了。

p8h8hvxi

p8h8hvxi6#

对于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;
        }
    }
}
wlsrxk51

wlsrxk517#

最简单的计算几何技术是遍历多边形的线段,看看它是否与其中任何一个相交,因为它也必须与多边形相交。
这种方法(以及CG的大多数方法)唯一的警告是,我们必须小心边缘情况。如果直线与矩形相交于一点,我们是否将其视为相交?在实现过程中要小心。

编辑:计算线段与线段相交的典型工具是LeftOf(Ray, Point)测试,如果点在射线的左侧,则返回。给定一条l线(我们将其用作射线)和一条包含点ab的线段,如果一个点在左侧而另一个点不在左侧,则该线与线段相交:

(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))

同样,当点在直线上时,您需要注意边缘情况,但这取决于您希望如何实际定义相交。

rryofs0p

rryofs0p8#

没有简单的预定义.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);

相关问题