online - test dome c#

C#Point 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

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

Answer 2

El guion meowNET no incluye los vértices poligonales en el polígono y los puntos exactamente en los bordes horizontales. Si necesita un algoritmo "inclusivo" exacto:

public static bool IsInPolygon(this Point point, IEnumerable<Point> polygon)
{
    bool result = false;
    var a = polygon.Last();
    foreach (var b in polygon)
    {
        if ((b.X == point.X) && (b.Y == point.Y))
            return true;

        if ((b.Y == a.Y) && (point.Y == a.Y) && (a.X <= point.X) && (point.X <= b.X))
            return true;

        if ((b.Y < point.Y) && (a.Y >= point.Y) || (a.Y < point.Y) && (b.Y >= point.Y))
        {
            if (b.X + (point.Y - b.Y) / (a.Y - b.Y) * (a.X - b.X) <= point.X)
                result = !result;
        }
        a = b;
    }
    return result;
}

Answer 3

He verificado 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 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

Mi respuesta está tomada desde aquí: Link

Tomé el código C y lo convertí en C # y lo hice 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;
    }

Puedes 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 6

Puedes usar el algoritmo de lanzamiento de rayos. Está bien descrito en la página de wikipedia para el problema Point in polygon .

Es tan simple como contar el número de veces que un rayo desde afuera 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 toca el rayo, comprueba las intersecciones entre el rayo y todos los lados del polígono.

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.

El problema del punto en el polígono para polígonos arbitrarios

El algoritmo es interesante de implementar y 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.

Answer 8

Vea this está en c ++ y se puede hacer en c # de la misma manera.

para polígono convexo es muy fácil:

Si el polígono es convexo, entonces uno puede considerar el polígono como una "ruta" desde el primer vértice. Un punto está en el interior de estos polígonos si siempre está en el mismo lado de todos los segmentos de línea que forman 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 con el segmento de línea. Compute (y - y0) (x1 - x0) - (x - x0) (y1 - y0)

si es menor que 0, entonces P está a 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 este es un código para él en c #, puede ser con errores:

        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 pruebo con rectángulo simple 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 en la consulta de linq:

poly.Skip(1) ==> crea una nueva lista iniciada desde la posición 1 de la lista poly y luego por (point.Y - poly[i].Y)*(pX - poly[i].X) - (point.X - poly[i].X) * (pY - 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