我需要一些提示：
如果在 P 的內部存在點 p 使得邊界上的任何其他點（頂點）對 p 可見，則多邊形 P 是星形的。
給定一個多邊形 P，我如何確定 P 是否是一個星形多邊形？
平均時間復雜度應該是o(n)。
我已經坐了一段時間了，任何幫助都會得到幫助。
uj5u.com熱心網友回復：
根據那個圓圈和餡餅對星星的非常奇怪的定義也是星星......
O(n)我能想到的第一個簡單且可行的方法是渲染可見性貼圖：
計算形狀的 BBOX
創建 BBOX 的 2D 地圖并將其清除為零
所以將二維陣列（紋理）映射到某個解析度的 BBOX
xs*ys對于每個凸頂點增量可見性圖
只需將“無限”三角形/四邊形渲染到地圖上
您可以使用纏繞規則來選擇頂點是凸的還是凹的，只需根據形狀的纏繞規則檢查相鄰邊叉積的 z 坐標的符號。
掃描包含凸頂點數量的單元格的 2D 地圖
所有包含凸頂點數量的單元格/像素都是可能的
Z，因此如果發現任何形狀是“星形”。
這是（凸）頂點的數量并且O(n*xs*ys)是可見性貼圖的解析度。請注意，如果您的解析度由于不準確而太低，您可能會產生誤報/誤報......如果地圖的（最大）解析度是恒定的，那么復雜性將變為.nxs*ysO(n)
渲染可以簡單地完成，例如使用 OpenGL 和 STENCIL 緩沖區，它直接具有增加 STENCIL 像素的操作，但是n由于 STENCIL 現在只有 8 位（在 OpenGL 更改后），因此將限制為 255...但是您可以解決這通過將 BBOX 設定為1并清除三角形/四邊形的外部而不是增加其內部。那么持有的像素1是你的Z，這可以與任何渲染引擎一起使用，不需要 STENCIL
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422813.html
標籤：