¿Cómo saber si una línea se cruza con un polígono en C #?

Question

Tengo una pregunta muy similar a este:

  

¿Cómo saber si una línea se cruza con un avión en C #?

Estoy buscando un método (en C #) que indica si una línea se intersectan un polígono arbitrario.

Creo que el algoritmo por Chris Marasti-Georg fue muy útil, pero falta el método más importante, es decir, la línea de línea de intersección.

¿Alguien sabe de un método de intersección de líneas para completar el código de Chris Marasti-Georg o tienen algo similar?

¿Existe un código incorporado para esto en C #?

Este método es para su uso con el algoritmo de Bing Maps mejorada con una característica de zona prohibida. La trayectoria resultante no debe pasar a través de la zona prohibida (el polígono arbitrario).

Answer 1

No hay un código incorporado para la detección de bordes integrado en el marco .NET.

Aquí está el código (portado a C #) que hace lo que necesita (el algoritmo real se encuentra en comp.graphics.algorithms en grupos de 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 poco fuera de tema, pero si la línea es infinito Creo que hay una solución mucho más simple:

La línea no pasa por el polígono si todos los puntos se encuentran en el mismo lado de la línea.

Con la ayuda de estos dos:

• Uso de LINQ o de otra manera, ¿cómo comprobar si todos los elementos de la lista tienen el mismo valor y devolverlo, o devolver un‘otherValue’si no lo hacen?
• determinar qué lado de una línea de un punto se encuentra

Tengo esta pequeña joya:

  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

Para detectar colisiones entre polígonos en nuestro proyecto de mapa Silverlight, estamos utilizando la biblioteca podadoras:

Gratis para uso comercial, tamaño pequeño, gran rendimiento y muy fácil de usar.

Clipper página web

Answer 4

Este artículo parece que va a ayudar a

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

Este código es un algoritmo de polígono-recortes de dos dimensiones que determina precisamente donde una línea se cruza con una frontera polígono. Este código funciona para ambos polígonos cóncavos y convexos de forma completamente arbitraria y es capaz de manejar cualquier orientación de la línea.