1

特定の1つのピクセルまでの距離が最小であるピクセルのグループの中からグループを見つけるには、アルゴリズムが必要です(疑似コードでも問題ありませんが、できればC++で)。

距離は、グループの各ピクセルから特定のピクセルまでの距離の合計として定義されますが、各距離は |x|+|y| に等しくなります。座標。

十分に明確でない場合は、明確にするよう努めます

ありがとうございました

4

3 に答える 3

3

距離の計算方法はすでにご存知のようです。

for ループは遅すぎますか? ループは N^2 でしょうか?

もしそうなら、あなたはBSPまたはQuadtreeの使用を検討するかもしれません。私が目にする唯一の問題は、近接テストを実行しようとしていることです。これらは主に衝突テスト用に設計されています。グループのセットをより迅速に排除できる可能性があります。

確実に機能する方法は (計算数を減らす効果は、グループの分布に大きく依存しますが)、単純に世界を等間隔でまばらに配置されたグリッドに分割することです。グループがグリッドの複数のセクションに分類される場合は、両方のグリッド エントリに追加してください。比較を実行するときは、最も近いグリッド エントリを選択し、そのグリッド エントリ内のグループに対してのみポイントツーグループ アルゴリズムを実行します。

于 2011-03-25T21:16:26.390 に答える
2

更新しました

このソリューションの最初のドラフトでは、質問者がマンハッタン距離を参照したときに幾何学的 (ユークリッド) 距離を計算しました。

これにより、最適化がより簡単になります。

  1. ピクセルのグループごとに、1 つのピクセルをプライマリ ピクセルとして選択します。どちらでも構いません。

  2. グループ内の他の各ピクセルについて、プライマリ ピクセルからのオフセット (x および y) を計算します。マンハッタン距離とは異なり、このオフセットの符号を保持します。

  3. すべてのオフセット (x オフセットと y オフセットの両方) を 1 つの数値に合計し、これを total_offsets と呼びます。

  4. 指定したピクセルからの距離が必要な場合は、プライマリ ピクセルの (マンハッタン) 距離を計算します。これにピクセル数を掛け、total_offsets を加算して、マンハッタンの合計距離を取得します。

手順 1 ～ 3 は各グループに対して 1 回だけ実行する必要があり、必要に応じて手順 4 を実行できます。

例えば

  Area A consists of 4 pixels: (8, 8), (8, 9), (9, 8) and (9, 9).  

  Declare (8, 9) as primary pixel.  Offsets are   
      (8, 9) --> (8, 8) = (0, -1)  
      (8, 9) --> (9, 8) = (1, -1)  
      (8, 9) --> (9, 9) = (1, 0)  
  total_offset = 0 + -1 + 1 + -1 + 1 + 0   
               = 0  
  num_pixels = 4  

To compute Manhattan distance from pixel (2, 4)

  distance to primary pixel  
  (2, 4) --> (8, 9) = (6, 5)   
                    = 11  
  dist * num_pixels + total_offsets = 11 * 4 + 0
                                    = 44

これを確認するために、長い道のりを計算できます。

      (2, 4) --> (8, 8) = (6, 4)   
      (2, 4) --> (8, 9) = (6, 5)   
      (2, 4) --> (9, 8) = (7, 4)   
      (2, 4) --> (9, 9) = (7, 5)   

  distance = 6 + 4 + 6 + 5 + 7 + 4 + 7 + 5 
           = 44
于 2011-03-25T22:44:38.330 に答える
1

以下は簡単な例です。距離を計算するには、関数「int distance(Point p1, Point p2)」が必要です (アルゴリズムを使用して)。

Point pxTest = ... // the single pixel to use for distance checking
List<Point> pxGroup = ... // the group of pixels to check

Point pxMin = null; // the pixel with the minimum distance
int iMin = int.MAX; // the minimum distance so far

foreach(Point pxOther in pxGroup)
    if(iMin > distance(pxTest, pxOther))
    {
        iMin = distance(pxTest, pxOther); // this could be cached in the line before as well to save this call
        pxMin = pxOther;
    }

// now pxMin will include the closest point, iMin the distance
于 2011-03-25T21:18:31.070 に答える