language-agnostic - ポリゴンとラスターイメージの交点かどうかを計算します

Question

バイナリイメージと不規則な凸多角形がある場合、それらが互いに交差するかどうかをどのように計算できますか？ポリゴンの座標は、画像の観点から記述されています。

衝突検出または塗りつぶしアルゴリズムの観点から、これについていくつかのアイデアがありますが、どちらも最適ではないと思います。これには、試行錯誤された方法があると思いますが、キーワードについて考えることはできません。

これが私が意味することの例です：

この場合、trueを返す必要があります。

Answer 1

次のアルゴリズムをお勧めします。

各ラインに対してブレゼンハムのアルゴリズムを使用してポリゴンの境界をトラバースし、各ピクセルでラスターをサンプリングします。ゼロ以外のアルファなど、表示を許可する色の場合は、交差を報告します。

これには、ポリゴンのエッジに対してのみ作業するという利点があるため、ポリゴン内のすべてのピクセルを反復処理する必要はありません。