Come capire se una linea interseca un poligono in C#?

Question

Ho una domanda molto simile a questo:

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

Sto cercando un metodo (in C#), che indica se una linea è interseca un poligono arbitrario.

Penso che il algorithm by Chris Marasti-Georg sia stato molto utile, ma mancava il metodo più importante, vale a dire l'intersezione da linea a linea.

Qualcuno sa di un metodo di intersezione della linea per completare il codice di Chris Marasti-Georg o qualcosa di simile?

C'è un codice incorporato per questo in C#?

Questo metodo è da utilizzare con l'algoritmo di Bing Maps ottimizzato con una funzione area vietata. Il percorso risultante non deve passare attraverso l'area proibita (il poligono arbitrario).

Answer 1

Non esiste alcun codice integrato per il rilevamento dei bordi integrato nel framework .NET.

Ecco il codice (porting su C#) che fa quello che è necessario (l'algoritmo attuale si trova al comp.graphics.algorithms sui gruppi di 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

Questo articolo sembra che aiuterà

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

Questo codice è un algoritmo poligono-clipping bidimensionale che determina con precisione dove una linea interseca con un bordo poligono. Questo codice funziona sia per poligoni concavi che convessi di forma completamente arbitraria ed è in grado di gestire qualsiasi orientamento di linea.

Answer 3

per rilevare le collisioni tra poligoni nel nostro progetto Silverlight Map , stiamo usando la libreria clipper:

Gratuito per uso commerciale, dimensioni ridotte, grandi prestazioni e molto facile da usare.

Clipper webpage

Answer 4

Leggermente fuori tema, ma se la linea è infinita Penso che ci sia una soluzione molto più semplice:

La linea non passa attraverso il poligono, se tutti i punti si trovano sullo stesso lato della linea.

Con l'aiuto di questi due:

• 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

ho avuto questo piccolo gioiello:

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