正方形セルポリゴン例えば

Question

内にあるかどうかを決定し、Iは、グリッドセル（四角）の内部または部分的ポリゴン＃14内を＃14に関連付けます。四角形がポリゴンの中に効率的にあるかどうかを計算するアルゴリズムはありますか？

ポリゴンを構成するエッジの座標があります。

Answer 1

私は右のそれを取得する場合、これは（sites呼ばれる）2次元点のセットを受け取り、この点について計算Voronoi diagramためのデータを含む構造体を返すJavaScriptでFortune's algorithmの実装です。 cellsというリスト内のポリゴンを返します。測定にはEuclidean distanceが使われているようです。それが真実であれば、ポリゴンは常に凸であることがわかります（フォーマル定義セクションVoronoi wiki pageを参照）。

1.多角形クリッピング：

1. 正方形のための多角形を形成

   は今、これらは、（ハードシンプルに）この問題を解決するためのオプションです。

2. Find its intersectionすべての細胞を含む。この交差点の
3. Calculate area。
4. 最大の交差点を見つけます。ポリゴンで

2 - ポイント：

あなたは、単に正方形の中心が内側にあるセルを見つけることができます。 Ray castingは堅牢なPIPアルゴリズムです。凸多角形の方が簡単です（凸多角形のセクションhereを参照してください）。

3ポイント間の距離：あなたは、各cellに関連するsiteを知っていれば、私は、あなただけのすべてのsitesに正方形の中心間の距離を計算する必要が

。 distance measurementがVoronoiを計算するのに関係なく、正方形の中心点はcell内にあり、これはsiteの距離が最小であることを示します。これは、実際にはボロノイ図の平面を分割するための考えであるためです。

---

例外：

• 最初のアプローチは、計算コストが高いが、最も正確です。第2および第3のオプションは、しかし、彼らは正確に決定するために失敗し、例外があり、ほとんどの場合、正常に動作：

• 第2および第3はかなり似ているが、しかし、PIPの下側には、ポリゴンの端にポイントがあり、検出するオーバーヘッドが増えます。