Рассчитать пиксели внутри многоугольника

Question

В задании для школы мы должны сделать некоторое распознавание изображения, где мы должны найти путь для робота.

Пока мы смогли найти все многоугольники на изображении, но теперь нам нужно сгенерировать карту пикселей, которая позже будет использоваться для алгоритма астар. Мы нашли способ сделать это, покажите ниже, но проблема в том, что это очень медленно, так как мы проходим каждый пиксель и проверяем, находится ли он внутри многоугольника. Итак, мой вопрос, есть ли способ, которым мы можем генерировать эту карту пикселей быстрее?

У нас есть список координат для многоугольника

private List<IntPoint> hull;

Функция getMap вызывается для получения карты пикселей

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 используется для ограничения поиска, так что нам не нужно переходить к целому изображению

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

И вот как мы проверяем, находится ли пиксель внутри многоугольника

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

Здесь есть интересная дискуссия здесь о тестах на попадание полигонов, но для меня это звучит так, как будто вам может быть лучше с заливкой полигонов.

Answer 2

Возможно, вам понадобится алгоритм Триангуляция Плигона .

Кроме того, обратите внимание, что отлов исключения занимает гораздо больше времени, чем проверка правильного условия. Поэтому я предлагаю вам преобразовать существующий код в:

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