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

Question

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

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

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

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

Получить прямоугольник используется для ограничения поиска, SE нам не нужно идти Thoug все изображение

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

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

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

Вы можете захотеть искать Плигон триангуляция алгоритм.

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

   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

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