C# Punto en el polígono

Question

Estoy tratando de determinar si un punto está dentro de un polígono. el Polígono está definido por una matriz de objetos Point. Puedo averiguar fácilmente si el punto está dentro de la caja delimitada del polígono, pero no estoy seguro de cómo decir si está dentro del polígono real o no. Si es posible, me gustaría usar solo C# y WinForms. Prefiero no invocar OpenGL o algo para hacer esta simple tarea.

Aquí está el código que tengo hasta ahora:

private void CalculateOuterBounds() 
{ 
    //m_aptVertices is a Point[] which holds the vertices of the polygon. 
    // and X/Y min/max are just ints 
    Xmin = Xmax = m_aptVertices[0].X; 
    Ymin = Ymax = m_aptVertices[0].Y; 

    foreach(Point pt in m_aptVertices) 
    { 
     if(Xmin > pt.X) 
      Xmin = pt.X; 

     if(Xmax < pt.X) 
      Xmax = pt.X; 

     if(Ymin > pt.Y) 
      Ymin = pt.Y; 

     if(Ymax < pt.Y) 
      Ymax = pt.Y; 
    } 
} 

public bool Contains(Point pt) 
{ 
    bool bContains = true; //obviously wrong at the moment :) 

    if(pt.X < Xmin || pt.X > Xmax || pt.Y < Ymin || pt.Y > Ymax) 
     bContains = false; 
    else 
    { 
     //figure out if the point is in the polygon 
    } 

    return bContains; 
} 

Answer 1

Ver this está en C++ y se puede hacer en C# de la misma manera.

de polígono convexo es demasiado fácil:

Si el polígono es convexo entonces uno puede consideran el polígono como un "camino" de el primer vértice. Un punto está en el interior de estos polígonos si es siempre en el mismo lado de todos los segmentos de línea que componen la ruta.

Dado un segmento de línea entre P0 (x0, y0) y P1 (x1, y1), otro punto P (x, y) tiene la siguiente relación al segmento de línea. Compute (y - y0) (x1 - x0) - (x - x0) (y1 - y0)

si es menor que 0, entonces P es la derecha del segmento de línea, si es mayor que 0 Está a la izquierda, si es igual a 0, entonces se encuentra en el segmento de línea.

Y esto es un código para ello en C#, puede ser tiene fallos:

 public static bool IsInPolygon(Point[] poly, Point point) 
     { 
      var coef = poly.Skip(1).Select((p, i) => 
              (point.Y - poly[i].Y)*(p.X - poly[i].X) 
             - (point.X - poly[i].X) * (p.Y - poly[i].Y)) 
            .ToList(); 

      if (coef.Any(p => p == 0)) 
       return true; 

      for (int i = 1; i < coef.Count(); i++) 
      { 
       if (coef[i] * coef[i - 1] < 0) 
        return false; 
      } 
      return true; 
     } 

lo prueba con un simple rectángulo funciona bien:

  Point[] pts = new Point[] { new Point { X = 1, Y = 1 }, 
             new Point { X = 1, Y = 3 }, 
             new Point { X = 3, Y = 3 }, 
             new Point { X = 3, Y = 1 } }; 
      IsInPolygon(pts, new Point { X = 2, Y = 2 }); ==> true 
      IsInPolygon(pts, new Point { X = 1, Y = 2 }); ==> true 
      IsInPolygon(pts, new Point { X = 0, Y = 2 }); ==> false 

Explicación de la consulta LINQ:

poly.Skip(1) ==> crea una nueva lista que comenzó en la posición 1 del poly lista y luego por (point.Y - poly[i].Y)*(p.X - poly[i].X) - (point.X - poly[i].X) * (p.Y - poly[i].Y) vamos a calcular la dirección (que se menciona en el párrafo al que se hace referencia). ejemplo similar (con otra operación):

lst = 2,4,8,12,7,19 
lst.Skip(1) ==> 4,8,12,7,19 
lst.Skip(1).Select((p,i)=>p-lst[i]) ==> 2,4,4,-5,12 

Answer 2

Puede utilizar el algoritmo de ray casting. Está bien descrito en la página de wikipedia para el Point in polygon problem.

Es tan simple como contar el número de veces que un rayo desde el exterior hasta ese punto toca los límites del polígono. Si toca un número par de veces, el punto está fuera del polígono. Si toca un número impar de veces, el punto está adentro.

Para contar la cantidad de veces que el rayo toca, puede verificar las intersecciones entre el rayo y todos los lados del polígono.

Answer 3

algoritmo completo junto con el código C está disponible en http://alienryderflex.com/polygon/
la conversión a C#/winforms sería trivial.

Answer 4

La respuesta aceptada no funcionó para mí en mi proyecto. Terminé usando el código que se encuentra aquí http://social.msdn.microsoft.com/Forums/en-US/winforms/thread/95055cdc-60f8-4c22-8270-ab5f9870270a/.

public static bool IsInPolygon(Point[] poly, Point p) 
    { 
     Point p1, p2; 


     bool inside = false; 


     if (poly.Length < 3) 
     { 
      return inside; 
     } 


     var oldPoint = new Point(
      poly[poly.Length - 1].X, poly[poly.Length - 1].Y); 


     for (int i = 0; i < poly.Length; i++) 
     { 
      var newPoint = new Point(poly[i].X, poly[i].Y); 


      if (newPoint.X > oldPoint.X) 
      { 
       p1 = oldPoint; 

       p2 = newPoint; 
      } 

      else 
      { 
       p1 = newPoint; 

       p2 = oldPoint; 
      } 


      if ((newPoint.X < p.X) == (p.X <= oldPoint.X) 
       && (p.Y - (long) p1.Y)*(p2.X - p1.X) 
       < (p2.Y - (long) p1.Y)*(p.X - p1.X)) 
      { 
       inside = !inside; 
      } 


      oldPoint = newPoint; 
     } 


     return inside; 
    } 

Answer 5

He comprobado los códigos aquí y todos tienen problemas.

El mejor método es:

/// <summary> 
    /// Determines if the given point is inside the polygon 
    /// </summary> 
    /// <param name="polygon">the vertices of polygon</param> 
    /// <param name="testPoint">the given point</param> 
    /// <returns>true if the point is inside the polygon; otherwise, false</returns> 
    public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint) 
    { 
     bool result = false; 
     int j = polygon.Count() - 1; 
     for (int i = 0; i < polygon.Count(); i++) 
     { 
      if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) 
      { 
       if (polygon[i].X + (testPoint.Y - polygon[i].Y)/(polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) 
       { 
        result = !result; 
       } 
      } 
      j = i; 
     } 
     return result; 
    } 

Answer 6

Mi respuesta es tomado de aquí: Link

Tomé el código C y se convierte en C# y lo hizo funcionar

static bool pnpoly(PointD[] poly, PointD pnt) 
    { 
     int i, j; 
     int nvert = poly.Length; 
     bool c = false; 
     for (i = 0, j = nvert - 1; i < nvert; j = i++) 
     { 
      if (((poly[i].Y > pnt.Y) != (poly[j].Y > pnt.Y)) && 
      (pnt.X < (poly[j].X - poly[i].X) * (pnt.Y - poly[i].Y)/(poly[j].Y - poly[i].Y) + poly[i].X)) 
       c = !c; 
     } 
     return c; 
    } 

Usted puede probarlo con este ejemplo:

PointD[] pts = new PointD[] { new PointD { X = 1, Y = 1 }, 
            new PointD { X = 1, Y = 2 }, 
            new PointD { X = 2, Y = 2 }, 
            new PointD { X = 2, Y = 3 }, 
            new PointD { X = 3, Y = 3 }, 
            new PointD { X = 3, Y = 1 }}; 

     List<bool> lst = new List<bool>(); 
     lst.Add(pnpoly(pts, new PointD { X = 2, Y = 2 })); 
     lst.Add(pnpoly(pts, new PointD { X = 2, Y = 1.9 })); 
     lst.Add(pnpoly(pts, new PointD { X = 2.5, Y = 2.5 })); 
     lst.Add(pnpoly(pts, new PointD { X = 1.5, Y = 2.5 })); 
     lst.Add(pnpoly(pts, new PointD { X = 5, Y = 5 })); 

Answer 7

Recomiendo este maravilloso trabajo de 15 páginas escrito por Kai Hormann (Universidad de Erlangen) y Alexander Agathos (Universidad de Atenas). Consolida todos los mejores algoritmos y le permitirá detectar soluciones de devanado y fundición de rayos.

The Point in Polygon Problem for Arbitrary Polygons

El algoritmo es interesante para poner en práctica, y bien vale la pena. Sin embargo, es tan complejo que no tiene sentido para mí a cualquier parte de él directamente. En cambio, me quedo con que si quieres EL algoritmo más eficiente y versátil, estoy seguro de que esto es todo.

El algoritmo se vuelve complejo porque está muy optimizado, por lo que requerirá mucha lectura para comprenderlo e implementarlo. Sin embargo, combina los beneficios de los algoritmos de número de bobina y de número de cuerda y el resultado es un número único que proporciona ambas respuestas a la vez. Si el resultado es mayor que cero e impar, entonces el punto está completamente contenido, pero si el resultado es un número par, entonces el punto está contenido en una sección del polígono que se repliega sobre sí misma.

Buena suerte.