変更FLOODFILL-アルゴリズムは、2つのデータポイントのボロノイテリトリーを取得しますか？

Question

私は2つの点でグリッドを得ました。私は、各点は、他の前に達することができる量の正方形を計算します。現在、私は一点が到達できる正方形の量を計算することができますFLOODFILL-そのアルゴリズムを実装します。

どのように私は両方のポイントについて「洪水」を次々simaltaneuoslyまたは少なくともいずれかを実行するためにそのアルゴリズムを変更できますか？

Answer 1

あなたは「各点は、他の前に達することができる」？

とはどういう意味ですか あなたはBF検索を必要とするように

これは、私には見えます。そのようにFIFOキューを使用します：

P1およびP2は、2つの点の位置とする。

fはキューおよびl最後の最初の要素とします。当初はF = 0、L = 1レッツQキューなります。

Q[f] = p1
Q[l] = p2
while ( f <= l )
{
   poz = Q[f];
   ++f;

   for each neighbour poz' of poz
      if poz' hasn't been marked yet
      {
         mark poz'
         add poz' to Q: Q[++l] = poz
      }
}

Qは、（行がCOLSをx）は、あなたのグリッドのサイズが必要になります。次の2つの行列を使用することができます。位置P1との1が到達することができますし、位置P2に他には到達することができ、またはあなたが1つの行列を使用して正方形に正の数と負の数との二乗P2が到達すると、P1に達するにマークを付けることができます。彼らが出会う場所あなたが興味を持っている場合、あなたはちょうどあなたが負の値（POZマイナスとPOZ」正）から正の値または他の方法で回避をマークしようとしているかどうかを確認する必要があります。これは基本的にターンであなたの洪水を行います：洪水1平方をP1から、その後、P2から、その後、P1から、その後、P2からのように。