Berechnen Pixel innerhalb eines Polygons

Question

In einer Zuweisung für die Schule brauchen wir einige Bild zu tun, zu erkennen, wo wir einen Weg für einen Roboter finden haben.

Bisher konnten wir alle die Polygone in dem Bild finden, aber jetzt brauchen wir eine Pixelkarte zu erzeugen, das später für einen astar Algorithmus verwendet werden. Wir haben einen Weg gefunden, dies zu tun gefunden, unten zeigen, aber das Problem ist, dass es sehr langsam ist, wie wir, obwohl jedes Pixel und Test gehen, wenn es innerhalb des Polygons ist. Also meine Frage ist, gibt es eine Möglichkeit, dass wir diese Pixelkarte schneller erzeugen kann?

Wir haben eine Liste von Koordinaten für das Polygon

private List<IntPoint> hull;

Die Funktion "getMap" aufgerufen, um die Pixel-Karte zu erhalten

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 Rechteck wird verwendet, um die Suche zu begrenzen, se wir müssen nicht gehen thoug das ganze Bild

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

Und atlast das ist, wie wir überprüfen, ob ein Pixel innerhalb des Polygons ist

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

Sie können für eine Plygon Triangulation Algorithmus suchen.

Auch diese Note eine Ausnahme zu kontrollieren ist weit mehr zeitraubend, dass der richtigen Zustand zu überprüfen. Also ich Ihnen vorschlagen, um Ihre vorhandenen Code konvertieren 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

Es gibt einige interessante Diskussion href="https://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test"> auf Polygon-Tests getroffen, aber es klingt für mich, als ob Sie mit einer Polygonfüllprozedur könnten besser dran.