最速の水平線＆lt;-＆gt;凸多角形交差アルゴリズム？

Question

比較的単純なことを解決する必要があります。n頂点の凸2Dポリゴンと、「y」座標を持つ水平（！）ラインがあります。必要なことは1つだけです。ポリゴンがこのラインと交差しているかどうか（つまり、2つの交差点があるかどうか）を確認することです。

私が考えることができる最速の方法は、ポリゴン内で最小/最大y座標を見つけ（2回の比較と2回のストアでn回繰り返されるループ）、その後、min y＆lt; = y＆lt;最大y。

どういうわけか、これはもっと「数学的に」解決できると思う。しかし、私は常に遅いコードで終わります（たとえば、ベクトルの方法-n [i]とn [i + 1]の差を計算し、それらを乗算し、加算する必要があります-2cmps + storesよりはるかに遅いです。

Answer 1

ポリゴンにy1＆lt;のポイントがあるかどうかを確認するだけです。 yとy2の1つ＆gt; y。このような2つのポイントを見つけたらすぐに完了です。 y座標でポイントにインデックスを付けることができる場合は、高速ルックアップにする必要があります。

Answer 2

水平の2Dラインの場合、はい、説明した方法はおそらく最速です。チェックを途中で終えて、最小値と最大値が＆gt;であるかのように、短絡させることもできます。および＆lt;あなたのY値は交差点を持っています。

Answer 3

毎回rawで実行する必要がある場合、それよりも速くするためのトリックはおそらく見つかりません。

ポリゴンで最小/最大Y値をキャッシュできる場合、テストを実行するたびに各頂点をループしないことで時間を節約できます。

ポリゴンにアラインされた境界ボックスがある場合、ポリゴンの代わりにボックスの範囲に対してテストし、同じ結果をより速く取得できます。

Answer 4

別のアプローチは、ここで説明されています： 線が凸多角形と交差する場合の最適なアルゴリズム。 しかし、直交線で処理しているため、少し単純化できます:)。したがって、合計の複雑さは、値を保存しないlog Nです。