Làm thế nào để biết một đường cắt một đa giác trong C#?

Question

Tôi có một câu hỏi rất tương tự như sau:

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

tôi đang tìm kiếm một phương pháp (trong C#) mà nói nếu một dòng được giao nhau một đa giác tùy ý.

Tôi nghĩ rằng algorithm by Chris Marasti-Georg rất hữu ích, nhưng thiếu phương pháp quan trọng nhất, tức là đường giao nhau với đường thẳng.

Có ai biết phương pháp giao cắt đường để hoàn thành mã của Chris Marasti-Georg hay có bất kỳ điều gì tương tự không?

Có mã tích hợp trong C# không?

Phương pháp này được sử dụng với thuật toán Bing Maps được tăng cường với tính năng khu vực cấm. Đường dẫn kết quả không được đi qua vùng cấm (đa giác tùy ý).

Answer 1

Không có mã nội bộ để phát hiện cạnh được tích hợp vào khung .NET.

Đây là mã (chuyển sang C#) mà những gì bạn cần (các thuật toán thực tế được tìm thấy ở comp.graphics.algorithms vào nhóm Google):

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

Bài viết này có vẻ như nó sẽ giúp

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

Mã này là một thuật toán đa giác-cắt hai chiều xác định chính xác nơi một dòng giao cắt với đường biên giới đa giác. Mã này hoạt động cho cả đa giác lõm và lồi của hình dạng hoàn toàn tùy ý và có thể xử lý bất kỳ định hướng dòng nào.

Answer 3

Để phát hiện va chạm giữa đa giác trong dự án bản đồ Silverlight của chúng tôi , chúng tôi đang sử dụng thư viện clipper:

Miễn phí cho mục đích thương mại, kích thước nhỏ, hiệu suất tuyệt vời và rất dễ sử dụng.

Clipper webpage

Answer 4

Hơi off topic, nhưng nếu dòng là vô hạn Tôi nghĩ rằng có một giải pháp đơn giản hơn nhiều:

Dòng không đi qua các đa giác nếu tất cả các điểm nằm trên cùng bên cạnh của dòng.

Với sự giúp đỡ từ hai:

• 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

tôi đã đá quý này chút:

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