如何判斷一個點是多邊形內部紋理

Question

這似乎是一個相當被問到的問題 - ！（聽我說完先:)

我已經創建了Perlin雜多邊形形狀，它看起來像這樣：

我需要生成從該陣列的點的質地。 （我使用Monogame/XNA，但我認爲這個問題有點不可知）。

無論如何，研究這個問題告訴我，很多人使用raycasting to determine how many times a line crosses over the polygon shape（如果一次，它在裏面，兩次或零次，它在外面）。這是有道理的，但我想知道是否有更好的方法，因爲我有所有的要點。 爲我想填充的每個像素做一個小型光線投射似乎過分 - 這是唯一/最好的方法嗎？

如果我有一個小廣場500px的形象，我需要填寫，我需要25萬個單個像素，這似乎是一個可怕的很多做了光線投射。

Answer 1

如果你想爲每個像素做到這一點，你可以用一個掃線：

開始從最上層的協調，從左至右檢查水平射線。計算與多邊形的所有交點並按x座標排序。然後迭代線上的所有像素，並記住你是否在進出。每當遇到交叉路口時，切換到另一側。如果某個像素處於，請設置紋理。如果沒有，請忽略它。對於每條可能的水平線，從上到下執行此操作。

交點計算可以通過幾種方式加以改進。例如。通過使用諸如網格，四叉樹等的加速度數據結構或者通過檢查之前的多邊形的相交或接觸邊緣。然後，當你掃過這條線時，你已經知道哪條邊會引起相交。