從邊緣看多邊形的可見性

Question

給出的是具有多邊形的2D。我需要找出位於該區域內的給定線段的垂直視線中可見的多邊形。例如

• 此外，

  什麼可以是優化時的多邊形僅具有垂直和水平邊緣。

Answer 1

我建議以下...

• 旋轉的問題，所以你的段「視線」對齊於x軸。
• 找到每個多邊形的（軸對齊）邊界矩形（BR）。
• 使用每個BR的底部邊緣的Y座標對多邊形排序
• 創建一個限幅「範圍緩衝區」來標記將不再可見的觀看段的各個部分。
• 對於排序列表中的每個多邊形C（電流）做...
  1. 按C的左右邊界作爲其初始剪輯範圍。
  2. 修剪C的裁剪範圍，範圍已經標記爲「範圍緩衝區」中的裁剪範圍。
  3. 現在對於一個類似的深度的每個隨後的多邊形S（即其中，S的BR底部邊緣開始低於C的BR頂邊）...
     • 循環到下一個S，如果它不水平以C重疊
     • 確定S是否從左邊或右邊重疊（例如通過比較S和C的BR水平中點）。如果S與右側重疊且S的最左側頂點低於C的最右側頂點，則相應地截斷C的裁剪範圍。 （同樣，如果S與左側重疊）
  4. 如果殘差剪切範圍不爲空，則至少部分C在您的觀看段中可見。現在將C的殘差剪切範圍添加到剪輯'範圍緩衝區'中。