2Dブール行列で最も近い "真の"要素を見つけるか？

Question

私はブール値を持つ2D行列を持っています。これは頻繁に更新されます。私は、マトリックス内の2Dインデックス{x、y}を選択し、すべての要素を通過することなくテーブル内の "真"である最も近い要素を探したい（マトリックスが大量です）。例えば

、Iは行列がある場合：

0000100 
0100000 
0000100 
0100001 

およびIは{x1, y1}ような座標を選択し、{4,3}、Iは、最も近い「真」値の位置を、返された場合は、この中のどのcaseは{5,3}です。要素間の距離は、標準的なピタゴラス式：

distance = sqrt(distX * distX + distY * distY)（distX = x1 - xおよびdistY = y1 - y）を使用して測定されます。

私は行列のすべての要素を調べ、 "真の"値のリストを保持し、最短の距離結果を持つものを選択することができますが、それは非常に非効率的です。検索時間を短縮するためにどのようなアルゴリズムを使用できますか？

詳細：マトリクスサイズは1920x1080で、フレームごとに約25のクエリが行われます。マトリックス全体がフレームごとに更新されます。私は妥当なフレームレートを維持しようとしています、7fps以上で十分です。

Answer 1

行列は常に更新されている場合は、距離変換のようないくつかのauxillary構造を構築する必要がない、Voronoy図など

あなただけのBFS（パン型検索）のような検索を実行できるクエリ点から伝播。通常のBFSとの唯一の違いはユークリッドのメトリクスです。だから、(u^2+v^2)順(u, v)ペアを生成し、（uまたはvが8ポイントそれ以外の場合は、ゼロの場合4点）(+-u,+-v),(+-v,+-u)組み合わせによってシフト対称の点を確認することができます

Answer 2

あなたは4分木のようなツリーデータ構造を使用することができます（https://en.wikipedia.org/wiki/Quadtreeを参照してください）を使用して、値が「true」のすべての場所を格納します。このようにして、所与の場所の近傍のすべての「真の」値を素早く反復することが可能でなければならない。さらに、場所の値が変化した場合、木は対数時間で更新することができる。