直線と長方形の平面領域内の特定のボロノイ分割のすべてのエッジとの交点を決定する計算効率の良い方法はありますか?
ありがとう
質問する
1029 次
1 に答える
2
最初の交点があれば、あとは簡単です。
エッジのデータベースを準備します。エッジごとに、それが属する両方のポリゴンをリストするか、それが外側のエッジであるとします (したがって、1 つのポリゴンのみに属します)。あなたの写真では、長方形の下側に 4 つの異なる多角形の 4 つのエッジが含まれます。
線を引き、最初の交点を見つけます (図の [0, 0.25]、丸で囲まれていません)。ポリゴン A だとします。次に、次の交点 (図で丸で囲まれた最も低い点) も A に属します。A のエッジのリストを二分探索して、関連するエッジを見つけます。
A の 2 番目のエッジが見つかったので、それが属している他のポリゴンを見つけます。次に、バイナリ検索を使用して、線が交差する他のポリゴンの他のエッジを見つけます。四角形を終了するまで続きます。
于 2013-05-03T20:38:07.550 に答える