0

写真から選択したデータを表す 2 次元配列があります。興味のないデータはすべて 0 に設定されます。2 つのインデックスから、0 ではない (座標を表す) インデックスに最も近い値 (幾何学的に) を見つける必要があります。

これまでの私の方法は、対象の点を中心とする値を円で調べ、ゼロ以外の値が見つからない円を通過するたびに半径を大きくすることです。

この方法の複雑さは指数関数的であるように見え、最も近いポイントが ~25 ピクセル以上離れている場合、プログラムは非常に長い時間がかかります。

これを達成するための別の方法/既存のアルゴリズムについてのアドバイスはありますか?

編集：リクエストごとに、私の現在のコードは以下の通りです：

        int height;
        int width;
        ushort[,] _2dfat;

        private ushort getAssociatedFat(int centerX, int centerY) 
        {
            int radiusmax = (int)Math.Ceiling(Math.Sqrt(Math.Pow(height,2) + Math.Pow(width, 2) + 1));
            return getAssociatedFat(1, centerX, centerY,radiusmax); 
        }

        private ushort getAssociatedFat(int radius, int centerX, int centerY,int radiusmax) //RECURSIVE METHOD: requires extensive analysis and testing
        {

            ushort max=circleSym8(centerX, centerY, radius);
            if (max != 0) return max;
            else if (radius <= radiusmax)
                return getAssociatedFat(radius + 1, centerX, centerY, radiusmax);
            else 
            { 
                MessageBox.Show("WARNING: empty fat array/image"); 
                return 0; 
            }
        }

        private ushort getMax(ushort max, int x, int y)
        {
            try
            {
                if (_2dfat[y, x] == 0) return max;
                else if (_2dfat[y, x] > max) return _2dfat[y, x];
                else return max;
            }
            catch (IndexOutOfRangeException) { return max; }


        }

        private ushort circleSym8(int xCenter, int yCenter, int radius)
        {
            int x, y, r2;
            r2 = radius * radius;
            ushort max=0;
            max=getMax(max, xCenter, yCenter + radius);
            max = getMax(max, xCenter, yCenter - radius);
            max = getMax(max, xCenter + radius, yCenter);
            max = getMax(max, xCenter - radius, yCenter);

            y = radius;
            x = 1;
            y = (int)(Math.Sqrt(r2 - 1) + 0.5);
            while (x < y)
            {
                max = getMax(max, xCenter + x, yCenter + y);
                max = getMax(max, xCenter + x, yCenter - y);
                max = getMax(max, xCenter - x, yCenter + y);
                max = getMax(max, xCenter - x, yCenter - y);
                max = getMax(max, xCenter + y, yCenter + x);
                max = getMax(max, xCenter + y, yCenter - x);
                max = getMax(max, xCenter - y, yCenter + x);
                max = getMax(max, xCenter - y, yCenter - x);
                x += 1;
                y = (int)(Math.Sqrt(r2 - x * x) + 0.5);
            }
            if (x == y)
            {
                max = getMax(max, xCenter + x, yCenter + y);
                max = getMax(max, xCenter + x, yCenter - y);
                max = getMax(max, xCenter - x, yCenter + y);
                max = getMax(max, xCenter - x, yCenter - y);
            }
            return max;
        }
4

1 に答える 1

3

興味深いデータをポイントとしてQuadtreeまたはkd-treeに保存し、その方法で範囲検索を実行できます。これらのデータ構造は、実行している検索の種類に合わせて最適化されており、各検索の複雑さが軽減されます。

私は、以下を提供する十分な Quadtree の実装を想定しています。

// Given some point in the quadtree, walk upwards and outwards
// returning points found ordered by distance
var nearestNeighbor = quadTree.Neighbors(point)
                              .OrderBy(pp => point.Distance(pp))
                              .First();
于 2012-11-19T17:38:11.160 に答える