計算多邊形和柵格圖像之間的交點

Question

如果我有一個二值圖像和一個不規則的凸多邊形，我該如何計算它們是否相互交叉？根據圖像描述多邊形的座標。

我對此有幾點想法，來自碰撞檢測或填充算法的角度來看，但我不認爲兩者都是最優的。我確信有一個經過實踐檢驗的方法，但不能想到關鍵字。

這裏是我的意思的例子：

在這種情況下，它應該返回true。

Answer 1

我會推薦這下面的算法：

導線採用布氏算法每行的多邊形的邊界，並在每個像素，採樣光柵。如果它是您接受可見的顏色，例如非零字母，請報告交叉點。

這樣做的好處是隻能處理多邊形的邊緣，所以不需要迭代多邊形內的所有像素。