如何判斷一條線是否與C＃中的多邊形相交？

Question

我有非常類似這樣的一個問題：

How to know if a line intersects a plane in C#?

我正在尋找一種方法（在C＃），告訴如果一個線相交的任意多邊形。

我認爲algorithm by Chris Marasti-Georg是非常有用的，但缺少最重要的方法，即線到線的交集。

有誰知道一個線交集方法來完成Chris Marasti-Georg的代碼或者有類似的東西嗎？

C＃中是否有內置的代碼？

該方法適用於增強了禁用區域功能的Bing Maps算法。得到的路徑不得通過禁區（任意多邊形）。

Answer 1

.NET框架內置的邊緣檢測沒有內置代碼。

這裏已經做了你需要的東西（實際的算法是在comp.graphics.algorithms發現在谷歌組）代碼（移植到C＃）：

public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF end2) 
{ 
    float denom = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X)); 

    // AB & CD are parallel 
    if (denom == 0) 
     return PointF.Empty; 

    float numer = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y)); 

    float r = numer/denom; 

    float numer2 = ((start1.Y - start2.Y) * (end1.X - start1.X)) - ((start1.X - start2.X) * (end1.Y - start1.Y)); 

    float s = numer2/denom; 

    if ((r < 0 || r > 1) || (s < 0 || s > 1)) 
     return PointF.Empty; 

    // Find intersection point 
    PointF result = new PointF(); 
    result.X = start1.X + (r * (end1.X - start1.X)); 
    result.Y = start1.Y + (r * (end1.Y - start1.Y)); 

    return result; 
} 

Answer 2

這篇文章看起來像它會幫助

http://www.codeproject.com/KB/recipes/2dpolyclip.aspx

此代碼是一個二維的多邊形裁剪算法來決定恰恰是一個符合多邊形的邊界相交。此代碼適用於完全任意形狀的凹面和凸面多邊形，並且能夠處理任何線方向。

Answer 3

爲了檢測我們的Silverlight地圖項目多邊形之間的碰撞，我們正在使用剪輯庫：

免費用於商業用途，體積小，性能卓越，非常易於使用。

Clipper webpage

Answer 4

稍微偏離主題，但如果該行無限我覺得有一個更簡單的解決方案：

線不通過多邊形去，如果所有的點位於同方的線。

有了這兩個求助：

• Using linq or otherwise, how do check if all list items have the same value and return it, or return an 「otherValue」 if they don’t?
• Determine which side of a line a point lies

我得到了這個小寶石：

public class PointsAndLines 
    { 
    public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region) 
    { 
     if (region == null || !region.Any()) return true; 
     var side = GetSide(lineP1, lineP2, region.First()); 
     return 
     side == 0 
     ? false 
     : region.All(x => GetSide(lineP1, lineP2, x) == side); 
    } 

    public static int GetSide(Point lineP1, Point lineP2, Point queryP) 
    { 
     return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X)); 
    } 
    }