Calcular píxeles dentro de un polígono

Question

En una misión para la escuela qué tenemos que hacer alguna imagen reconociendo, cuando tenemos que encontrar un camino para que un robot.

Hasta ahora hemos sido capaces de encontrar todos los polígonos en la imagen, pero ahora tenemos que generar un mapa de píxeles, que se puede utilizar para un algoritmo Astar más tarde. Hemos encontrado una manera de hacer esto, mostrará más adelante, pero el problema es que es muy lento, a medida que avanzamos, aunque cada píxel y probar si se encuentra dentro del polígono. Así que mi pregunta es, ¿hay una manera que podemos generar este mapa de píxeles más rápido?

Tenemos una lista de coordenadas para el polígono

private List<IntPoint> hull;

La función "getMap" se llama para obtener el mapa de píxeles

public Point[] getMap()
{
    List<Point> points = new List<Point>();
    lock (hull)
    {
        Rectangle rect = getRectangle();
        for (int x = rect.X; x <= rect.X + rect.Width; x++)
        {
            for (int y = rect.Y; y <= rect.Y + rect.Height; y++)
            {
                if (inPoly(x, y))
                    points.Add(new Point(x, y));
            }
        }
    }
    return points.ToArray();
}

Get rectángulo es utilizado para limitar la búsqueda, en sí no tenemos que ir thoug la imagen entera

public Rectangle getRectangle()
{
    int x = -1, y = -1, width = -1, height = -1;
    foreach (IntPoint item in hull)
    {
        if (item.X < x || x == -1)
            x = item.X;
        if (item.Y < y || y == -1)
            y = item.Y;


        if (item.X > width || width == -1)
            width = item.X;
        if (item.Y > height || height == -1)
            height = item.Y;


    }
    return new Rectangle(x, y, width-x, height-y);
}

Y así es como atlast, comprobamos para ver si un píxel está dentro del polígono

public bool inPoly(int x, int y)
{
    int i, j = hull.Count - 1;
    bool oddNodes = false;

    for (i = 0; i < hull.Count; i++)
    {
        if (hull[i].Y < y && hull[j].Y >= y
        || hull[j].Y < y && hull[i].Y >= y)
        {
            try
            {
                if (hull[i].X + (y - hull[i].X) / (hull[j].X - hull[i].X) * (hull[j].X - hull[i].X) < x)
                {
                    oddNodes = !oddNodes;
                }
            }
            catch (DivideByZeroException e)
            {
                if (0 < x)
                {
                    oddNodes = !oddNodes;
                }
            }
        }
        j = i;
    }
    return oddNodes;
}

Answer 1

Es posible que desee buscar un Plygon triangulación algoritmo.

Además, cabe destacar que la captura de una excepción es mucho más lento que el control de la condición correcta. Así que sugiero que para convertir el código existente en:

   public bool inPoly(int x, int y)
    {
        int i, j = hull.Count - 1;
        var oddNodes = false;

        for (i = 0; i < hull.Count; i++)
        {
            if (hull[i].Y < y && hull[j].Y >= y
                || hull[j].Y < y && hull[i].Y >= y)
            {
                var delta = (hull[j].X - hull[i].X);
                if (delta == 0)
                {
                    if (0 < x) oddNodes = !oddNodes;
                }
                else if (hull[i].X + (y - hull[i].X) / delta * delta < x)
                {
                    oddNodes = !oddNodes;
                }

            }
            j = i;
        }
        return oddNodes;
    }

Answer 2

Hay alguna discusión interesante aquí el polígono de pruebas de golpe, pero sonidos a mí como si te pueden ser mejor con un relleno de polígono.