4

点 (P1) までの距離が最小の閉領域内の点 (P2) を見つけようとしています。この領域は均質なピクセルで構成されており、完全な形状ではなく、必ずしも凸状であるとは限りません。これは基本的に、最短経路からエリアに到達する問題です。

空間全体がビットマップの形式でメモリに格納されます。P2を見つけるための最良の方法は何ですか? ランダム検索 (最適化) メソッドを使用する必要がありますか? 最適化手法では正確な最小値は得られませんが、領域のすべてのピクセルを強制的に処理するよりも高速です。これらの決定を数秒で何千回も実行する必要があります。

領域の MinX、MinY、MaxX、MaxY が利用可能です。

問題

ありがとう。

4

4 に答える 4

4

これが私のコードです。離散座標を使用した離散バージョンです。

ヒント: エリアの円周を見つけるために使用した方法は単純です。陸地からビーチをどのように知るかのようなものです。答え: ビーチは片側から海に覆われているので、私のグラフ マトリックスでは、NULL 参照は海、ポイントは陸地です!

クラスポイント:

class Point
{
    public int x;
    public int y;

    public Point (int X, int Y)
    {
        this.x = X;
        this.y = Y;
    }
}

クラスエリア:

class Area
{
    public ArrayList<Point> points;

    public Area ()
    {
        p = new ArrayList<Point>();
    }
}

離散距離ユーティリティ クラス:

class DiscreteDistance
{

    public static int distance (Point a, Point b)
    {
        return Math.sqrt(Math.pow(b.x - a.x,2), Math.pow(b.y - a.y,2))
    }

    public static int distance (Point a, Area area)
    {
        ArrayList<Point> cir = circumference(area);
        int d = null;

        for (Point b : cir)
        {
            if (d == null || distance(a,b) < d)
            {
                d = distance(a,b);
            }
        }

        return d;
    }

    ArrayList<Point> circumference (Area area)
    {
        int minX = 0;
        int minY = 0;
        int maxX = 0;
        int maxY = 0;

        for (Point p : area.points)
        {
            if (p.x < minX) minX = p.x;
            if (p.x > maxX) maxX = p.x;
            if (p.y < minY) minY = p.y;
            if (p.y > maxY) maxY = p.y;
        }

        int w = maxX - minX +1;
        int h = maxY - minY +1;

        Point[][] graph = new Point[w][h];

        for (Point p : area.points)
        {
            graph[p.x - minX][p.y - minY] = p;
        }

        ArrayList<Point> cir = new ArrayList<Point>();

        for (int i=0; i<w; i++)
        {
            for (int j=0; j<h; j++)
            {
                if ((i > 0 && graph[i-1][j] == null)
                  || (i < (w-1) && graph[i+1][j] == null)
                  || (j > 0 && graph[i][j-1] == null)
                  || (i < (h-1) && graph[i][j+1] == null))
                {
                    cir.add(graph[i][j]);
                }
            }
        }

        return cir;
    }    
}
于 2013-03-21T13:58:52.453 に答える
1

エリア内の少なくとも 1 つのピクセル アドレス (x0,y0) を知っているか、簡単に見つけることができると仮定する必要があります。最速の解決策は、このピクセルから直線で、たとえばプラス x 方向に検索することです。別の方法として、バウンディング ボックスがあるので、最も近い境界に向かってコンパス ポイントを選択し、その方向に進みます。

領域の端を見つけたら、まず境界に沿って深さを検索します。 自己交差および/または穴を含む一般的なポリゴンの場合、これは、既に訪問した頂点のセットを維持する、完全で慎重に実装された DFS である必要があります。 ポリゴンが単純な場合にのみ、最後にアクセスしたピクセルのみを記憶して、既に検索されたものを 2 倍に戻さないようにするだけで十分です。

DFS 中に、境界ピクセルごとに p1 の二乗距離を計算し、最小値を追跡します。

パフォーマンスが本当に必要な場合は、この距離の二乗を段階的に更新して、乗算を加算に置き換えることができます。つまり、知っていて、境界の周りで次のステップを実行するために 1d2=(x2-x1)^2+(y2-y1)^2ずつ増やした場合x2、新しい距離の 2 乗は次のようになります。

((x2+1) - x1)^2 + (y2-y1)^2 = d2 + 2(x2 - x1) + 1

d2で更新できますd2 += 2(x2 - x1) + 1。2 の乗算はもちろん左シフトなので、これは非常に安価です。各方向のステップには、同様の非常に安価な更新があります。

于 2013-03-21T14:38:13.600 に答える
0

アプローチの 1 つは、最初に領域の三角形分割を計算して近似解を設定することです。その後、三角形の角だけをチェックする必要があります。このアプローチは、計画している多くの評価で、外側の点が変化しても形状自体は変化しない場合に特に有益です。

于 2013-03-21T14:03:31.783 に答える
0

領域の四角形の中心を見つけ、2 点間の三角形を使用して角度を見つけ、関数 f(x) = mx + b を使用して、そのピクセルが見つかるまでピクセル ウォークを実行します。距離を計算し、最短経路が見つかるまで角度を回転させます。

于 2013-03-22T08:18:19.987 に答える