「倒置」凹多邊形

Question

我正在構建2D遊戲，玩家只能看到未被其他對象阻擋的事物。現在看看這個例子：

我已經實現了這個的光線跟蹤算法，它似乎工作得很好（我減少了演示的邊界，使所有邊緣可見）。

正如你所看到的，較輕的區建成了一堆三角形的，他們每個人的具有玩家的位置共同點。每兩個鄰居有兩個共同點。

但是我願意計算外部的邊界多邊形的一部分填充黑色三角形「隱藏」玩家看不到的部分。

這樣做的一種方法是用當前多邊形「遮罩」黑色矩形，但恐怕它非常無效。

任何關於實現這一目標的有效算法的想法？

謝謝！

Answer 1

一個非分析的，粗略的解決方案。

• 投射的光線與逐漸增加極角
• 記錄當光線首先撞擊的物體（和其中它擊中點）
• 繼續下去，直到它不再擊中相同的對象（和記錄它先前命中）
• 使用兩個記錄點，構建體，其延伸到無窮大（或任何一個梯形）

個

注意事項：

• 不與凹陷工作得很清楚 - 需要包括所有點之間爲好。可能需要Delaunay三角測量等...凌亂！

• 可能需要額外的狀態來計算相互隱藏的對象。