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

Question

Ho una domanda molto simile a questo:

  

Come sapere se una linea interseca un aereo in C #?

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

Credo che l'algoritmo da Chris Marasti-Georg è stato molto disponibile, ma manca il metodo più importante, vale a dire la linea di intersezione linea.

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

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

Questo metodo è per l'uso con l'algoritmo di Bing Maps migliorato con una caratteristica zona proibita. Il percorso risultante non deve passare attraverso la zona proibita (poligono arbitrario).

Answer 1

Non esiste un 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

Un po 'fuori tema, ma se la linea è infinito Penso che ci sia una soluzione molto più semplice:

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

Con l'aiuto di questi due:

• utilizzando LINQ o in altro modo, come si fa controllare se tutte le voci di elenco hanno lo stesso valore e restituirlo, o restituire un‘otherValue’se non lo fanno?
• Determinare quale parte di una linea di un punto si trova

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

Answer 3

Per rilevare le collisioni tra poligoni nel nostro progetto mappa Silverlight, stiamo usando la libreria tagliatore:

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

Clipper pagina web

Answer 4

In questo articolo sembra che sarà 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 per entrambi i poligoni concavi e convessi di forma del tutto arbitraria ed è in grado di gestire qualsiasi orientamento linea.