从边缘看多边形的可见性

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的残差剪切范围添加到剪辑'范围缓冲区'中。