设有一组互不相交的多边形障碍物 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
设有一组互不相交的多边形障碍物 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