Calculer pixels à l'intérieur d'un polygone

Question

Dans une mission pour l'école doit-on faire une image de reconnaissance, où nous devons trouver un chemin pour un robot.

Jusqu'à présent, nous avons été en mesure de trouver tous les polygones dans l'image, mais maintenant nous avons besoin de générer une carte de pixels, qui est utilisé pour un algorithme de Astar plus tard. Nous avons trouvé une façon de faire, montrer ci-dessous, mais le problème est qu'il est très lent, comme nous allons bien chaque pixel et tester si elle est à l'intérieur du polygone. Donc, ma question est, y at-il une manière que nous pouvons générer cette carte de pixels plus rapide?

Nous avons une liste de coordonnées du polygone

private List<IntPoint> hull;

La fonction "getMap" est appelée pour obtenir la carte de 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 Rectangle est utilisé pour limiter la recherche, se nous n'avons pas aller thoug l'ensemble de l'image

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

Et atlast voici comment nous vérifions pour voir si un pixel est à l'intérieur du polygone

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

Vous voudrez peut-être chercher un Plygon Triangulation algorithme.

En outre, notez que la capture une exception est beaucoup plus de temps que la vérification de la bonne condition. Donc, je vous suggère de convertir votre code existant dans:

   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

Il y a une discussion intéressante sur les tests a frappé un polygone, mais me semble que si vous pourriez être mieux avec un remplissage de polygone.