Calcola pixel all'interno di un poligono

Question

In un incarico per la scuola abbiamo bisogno di fare un po 'di immagini che riconosce, in cui dobbiamo trovare un percorso per un robot.

Finora siamo stati in grado di trovare tutti i poligoni nell'immagine, ma ora abbiamo bisogno di generare una mappa di pixel, che essere utilizzato per un algoritmo Astar tardi. Abbiamo trovato un modo per fare questo, mostrare al di sotto, ma il problema è che è molto lento, come andiamo se ogni pixel e verificare se è all'interno del poligono. Quindi la mia domanda è, ci sono un modo che possiamo generare questa mappa di pixel più veloce?

Abbiamo una lista di coordinate del poligono

private List<IntPoint> hull;

La funzione "getMap" è chiamato ad ottenere la mappa di pixel

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 rettangolo viene utilizzato per limitare la ricerca, se non dobbiamo andare thoug l'intera immagine

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

E atlast questo è il modo controlliamo per vedere se un pixel è all'interno del poligono

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

Si consiglia di cercare un Plygon Triangolazione algoritmo.

Si noti inoltre che la cattura un'eccezione è molto più in termini di tempo che il controllo la condizione giusta. Quindi vi suggerisco di convertire il codice esistente in:

   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

Ci sono alcune discussioni interessanti qui sul poligono colpito test, ma Sembra a me come se si potrebbe essere meglio con un riempimento poligono.