设有一组互不相交的多边形障碍物 S,边的总数为 n,现要构造 S 的可见性图。

算法 VISIBILITYGRAPH(S)

1. 初始化图 G=(V, E),其中 V 包含 S 中所有多边形的顶点,E 为空集

2. 对图中每个顶点 v

3. 计算 v 在 S 中的可见顶点集合 W = VisibilityVertices(v, S)

4. 对每个 w∈W,将边 (v, w) 加入 E

5. 返回 G