比較的単純なことを解決する必要があります。n個の頂点の凸型2Dポリゴンと、「y」座標を持つ水平（！）線があります。必要なのは1つだけです。ポリゴンがこの線と交差しているかどうか（つまり、2つの交差があるかどうか）を確認することです。
私が考えることができる最も速いものは、ポリゴン内の最小/最大y座標を見つけ（2つの比較と2つのストアでn回繰り返されるループ）、次に最小y <=y<最大yであるかどうかを比較することです。
どういうわけか、これはもっと「数学的に」解決できると思いますが、私は常に遅いコードで終わります（たとえば、ベクトルの方法-n[i]とn[i + 1]の差を計算してから、それらを乗算したり、追加したりする必要があります- -2 cmps +ストアよりもはるかに遅い）。
ポリゴンに y1 < y のポイントと y2 > y のポイントがあるかどうかのみを確認する必要があります。このような 2 つのポイントを見つけるとすぐに、完了です。y 座標でポイントにインデックスを付けることができれば、ルックアップが高速になります。
水平の 2D ラインの場合は、はい、説明した方法がおそらく最速です。チェックの途中で最小+最大値が>および<y値である場合、交差があるかのように、それを短絡することもできます。
毎回 raw で実行する必要がある場合、それよりも高速にするためのトリックはおそらく見つからないでしょう。
最小/最大 Y 値をポリゴンでキャッシュできる場合は、テストを実行するたびに各頂点をループしないことで時間を節約できます。
ポリゴンに関連付けられた位置合わせされた境界ボックスがある場合、ポリゴンではなくボックスの範囲に対してテストして、同じ結果をより速く得ることができます。
別のアプローチは、ここで説明されています: ラインが凸多角形と交差する場合の最適なアルゴリズム。しかし、直交する線を扱っているので、少し単純化できます:)。したがって、値を格納しない場合、合計の複雑さは log N になります。