0

学校の課題では、ロボットのパスを見つける必要がある画像認識を行う必要がありますか。

これまでのところ、画像内のすべてのポリゴンを見つけることができましたが、後で 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();
}

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

2 に答える 2

2

ここでは、ポリゴン ヒット テストに関する興味深い議論がいくつかありますが、ポリゴン フィルを使用したほうがよいように思えます。

于 2010-05-05T09:04:14.630 に答える
1

Plygon Triangulationアルゴリズムを探すことができます。

また、例外のキャッチは、適切な条件をチェックするよりもはるかに時間がかかることに注意してください。したがって、既存のコードを次のように変換することをお勧めします。

   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;
    }
于 2010-05-05T09:20:16.323 に答える