如何知道，如果一條線相交的矩形

Question

我已經檢查了這個問題，但答案是非常大的對我說：

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 
} 

在此先感謝。

Answer 1

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

Answer 2

沒有簡單的預定義的.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); 

Answer 3

最簡單的計算幾何的方法是步行穿過多邊形的細分，看看它是否對任何人相交，因爲它當時還必須相交的多邊形。

這種方法（和大多數CG）唯一的缺陷是我們必須小心邊緣情況。如果這條線在某個點上穿過矩形會怎麼樣 - 我們將其計爲交叉點還是不是？在執行時要小心。

編輯：於線相交段計算的典型工具是LeftOf(Ray, Point)測試，它返回如果點是於光線的左側。給定一個線l（這是我們作爲一個射線使用），並含有點a和b段，線路相交的部分，如果一個點是在左，一個點是不是：

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

同樣，你需要注意邊緣情況，當點在線時，但取決於你希望如何實際定義交叉點。

Answer 4

窮舉算法...

首先檢查，如果矩形是到線端點的左邊或右邊：

• 樹立線端點的最左和最右的X值：XMIN和XMAX
• 如果Rect.Left> XMAX，則不交叉。
• 如果Rect.Right < XMIN，那就不用交集了。

然後，如果上述不足以排除交點，檢查是否該矩形是高於或低於線端點：

• 建立最頂部和最底部線端點的Y值： YMAX和YMIN
• 如果Rect.Bottom> YMAX，則不交叉。
• 如果Rect.Top < YMIN，那麼沒有交集。

然後，如果上述還不足以排除路口，你需要檢查線路，y = m * x + b的方程，看是否RECT是線以上：

• 樹立線的Y值在Rect.Left和Rect.Right：LINEYRECTLEFT和LINEYRECTRIGHT
• 如果Rect.Bottom> LINEYRECTRIGHT & & Rect.Bottom> LINEYRECTLEFT，則不交叉。

然後，如果上述還不足以排除路口，你需要檢查的矩形是線下：

• 如果Rect.Top < LINEYRECTRIGHT & & Rect.Top < LINEYRECTLEFT，然後不交叉。

然後，如果你在這裏：

• 路口。

N.B.我確信有一個更優雅的代數解決方案，但用筆和紙幾何執行這些步驟很容易。

一些未經測試和未編譯的代碼去與那：

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

Answer 5

我把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。我會注意到，起初我編寫了自己的程序，檢查了梯度上的每個點，並且盡我所能做到了最大限度地提高性能，但這種速度立即更快。

Answer 6

不幸的是，錯誤的答案已被投票。計算實際的交點非常昂貴，你只需要比較。要查找的關鍵字是「線路剪輯」（http://en.wikipedia.org/wiki/Line_clipping）。維基百科的建議，當你想快速拒絕科恩 - 薩瑟蘭算法（http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland），這可能是最常見的場景。在維基百科頁面上有一個C++實現。如果您對剪切線不感興趣，可以跳過其中大部分。 @Johann的答案看起來與該算法非常相似，但我沒有詳細看它。

Answer 7

該代碼具有更好的性能：

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

Answer 8

對於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; 
     } 
    } 
}