最大の空きスペースを決定するための効率的なアルゴリズム

Question

私は以下のように巧みに描かれた状況を持っています。これは、エリア内で最大の円（空きスペース）を計算する必要があります。以下の例では、黒い円は固定された既知の位置です。黒い円に触れない最大の領域（橙色と緑色の円で表されます）を見つける必要があります。以下の例では、オレンジ色の円が最大の空白です。これは計算したい領域です。

私はそれが黒のポイントに当たるまで、ちょうど円（オープンスペース）の位置と半径を記録し、それを強制位置を選んで、輪を広げブルートでしたが、これは、大規模になるだろうすべての可能な位置を反復するのに非効率的です。

このインスタンスで最大のオープンスペースがどこにあるかを効率的に分析する方法はありますか？このフィールドの黒点の最大数は15であることに留意してください。

EDITありがとうございましたYvesさんと他のすべてのコメント投稿者答えと他のコメントに基づいて説明のカップル。ブラックボックスはバインドされているため、定義された領域はブラックボックスの内側になければなりません。黒丸の半径は既知であり、静的であるが、これらの目的のためには、それらをポイントに縮小することができる。最後に、円の近似が許容される。いずれにしてもどの領域が最も良いかを判断する上で誤差マージンを持つAIルーチンで使用されます。だから、サークルが半径または位置が多少外れている場合、大きな問題にはなりません。

私は現在Voronoiの方法を検討していますが、私はそれを理解していると思っていますが、今は適合するアルゴリズムを引き出そうとしています。私はテストして、あなたに戻ってきます。

EDIT 2：イヴのおかげで、私はボロノイ図に見て（それが境界ボックスと交差し、点）のすべてのボロノイ頂点をループとdoesnのその中心点から最大の円を見つける簡単な方法を使用「黒丸」のいずれかを含んでいない。比較的小さな、有限の点集合で、私はこの実装で十分満足しています。その結果を下記に示し、スペース内の空白の円の上3つを表示します。

Answer 1

これは "最大空円" の問題として知られています。ボロノイ図で効率的に解くことができます。

黒い円が有限の直径を持つ場合、それらを中心に縮小し、後で見つけた解から半径を推定することができます。

とにかく、矩形に対して円が許可されている場合、これを考慮に入れてアルゴリズムを変更する必要があります。些細ではない仕事。

更新：

関連の問題がで対処して

「場所の制約とTOUSSAINT、Godfried T.コンピューティング最大の白丸コンピュータ&情報科学の国際ジャーナル、1983年、12.5：347-358」と " CHEW、L. Paul; DRYSDALE、Scot。位置制約付きの最大空白円の発見1986. "中心が所与の凸多角形の内部に拘束されているときの効率的な解法を説明している。 （しかしあなたは、私が推測するように、円が完全に含まれるように求めています。）

---

完全に異なるアプローチが離散画像、有限の大きさのピクセル）を扱う（デジタルドメインで可能である：あなたが黒画素にユークリッド距離マップを計算することができます。線形時間（障害物の数ではなく画像サイズで）を達成する非常にスマートな効率的なアルゴリズムがあります。 「A.Meijster、J.B.T.M RoerdinkおよびW.H. Hesselink、線形時間における距離変換を計算するための一般的なアルゴリズム」を参照されたい。

距離マップを計算した後、目的の円の中心が最大の距離値を持つピクセルになります。この方法は、どんな形の障害物でも機能します。

---

更新：あなたのケースでは

障害物が少ないように、徹底的な検索が許容できるかもしれません。あなたは3点を通過する円を試し、2点を通過して辺に接したり、1点を通過して2辺に接したりする必要があります。

これらのサークルすべてについて、他の点が含まれていないことを確認し、最大値を維持してください。原則として、これにはO（N^4）時間がかかります。どうやらこの複雑さはO（N³）に引き下げることができますが、この問題で見つかったすべてのエントリは、ボロノイベースのアプローチであり、完全なものではありません。