多边形从边的可见性 [英] Visibility of polygons from an edge

问题描述

给出的是带有多边形的2D.我需要从位于该区域内的给定线段中找出在垂直视线内可见的多边形.例如

Given is a 2D are with the polygons. I need to find out the polygons visible in a perpendicular line of sight from the a given line segment lying within that area. e.g.

• 进一步，

• Further,

当多边形仅具有垂直和水平边缘时，可以进行哪些优化.

What can be the optimizations when the polygons have only vertical and horizontal edges.

推荐答案

我建议以下内容...

I'd suggest the following ...

• 旋转问题，使您的视线"段与x轴对齐.
• 找到每个多边形的(与轴对齐)边界矩形(BR).
• 使用每个BR底部边缘的Y坐标对多边形进行排序
• 创建一个剪辑范围缓冲区"以标记观看片段的不再可见的部分.
• 对于排序列表中的每个多边形C(当前)，请执行以下操作:

• Rotate the problem so your 'line of sight' segment is aligned to the x axis.
• Find the (axis aligned) bounding rectangle (BR) of each polygon.
• Sort the polygons using the Y coordinate of the bottom edge of each BR
• Create a clipping 'range buffer' to mark the portions of the viewing segment that will be no longer visible.
• For each polygon C (current) in the sorted list do ...

1. 使用C的左右边界作为其初始裁剪范围.
2. 修剪C的剪切范围，该范围已在范围缓冲区"中标记为已剪切.
3. 现在，每个后续深度相似的多边形S(即S的BR底边从C的BR顶边开始的位置)...
   • 如果不与C水平重叠，则循环到下一个S
   • 确定S是从左还是从右重叠(例如，通过比较S和C的BR水平中点).如果S从右边重叠，并且S的最左边的顶点低于C的最右边的顶点，则相应地截断C的剪切范围. (同样，如果S从左侧重叠.)

1. Use C's left and right bounds as its initial clipping range.
2. Trim C's clipping range with the range already marked as clipped in the 'range buffer'.
3. Now for each subsequent polygon S of a similar depth (ie where S's BR bottom edge starts below C's BR top edge) ...
   • loop to next S if it doesn't overlap horizontally with C
   • determine if S is overlapping from the left or right (eg by comparing the BR horizontal midpoints of S and C). If S overlaps from the right and S's left-most vertex is below C's right-most vertex, then truncate C's clipping range accordingly. (Likewise if S overlaps from the left.)

这篇关于多边形从边的可见性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！