既存の点と衝突することなく最も近い利用可能な空間を見つける

Question

点の集合を与えられた場合、指定された点（赤い枠で表される）の幅と高さの最も近い利用可能な空間を効率的に見つける方法この例ではポイント4）。

はまた、私はまだ（示すように）最も近いスペースを見つけることを望んでいる箱は4を指すようにすぐに次の収まらないポイント（下図）の異なるセットを与えられました。私はポイント4と赤いボックスの中心の間の距離で「最も近い」と判断しています。

すべてのヘルプや思考がはるかに高く評価されるだろう。

Answer 1

この問題を解決するための鍵は、すべての点が4つ（重複する）の半平面（北、南、西または東）で空間を分割することを考慮しています。

基準点を考慮することから始めて、矩形はその北または南など、すなわち上で定義した半平面の1つになければなりません。

半平面の代わりに、無限にある面を持つ軸に沿った長方形と考えることができます。

これらの境界矩形のすべてについて、ターゲット矩形を参照点に最も近い位置に配置してみます。任意の点と衝突する場合は、その点の境界矩形を4つの新しい境界矩形で分割して繰り返します。

ので、要約すると：

1）は、基準点までの距離が注文した四角形の境界のキューを保持します。

2）最初の要素を取得し、参照点に最も近い位置に四角形を収めることができるかどうかを確認します。可能であれば、問題は解決されます。

3）そうでなければ、任意の衝突点で境界矩形を分割し、結果として得られる4つの境界矩形をキューに押し込みます（小さすぎるものを除外します）。

4）繰り返し。