<-- Home

Visibility Graph

可见性图(Visibility Graph)算法是计算几何中的基础算法,该算法解决n维空间中的多个图形的每个顶点与其他顶点之间的可见性问题。所谓“可见性”,即图中任意两个顶点的连线不会与图中其他边相交,也就是说这两个点之间没有阻碍。

可见性图G中的几何图形可以由不同类型的形状组成:直线、圆形、线段、简单多边形。

计算可见性图的算法

台湾计算机科学家Der-Tsai Lee提出了一种时间复杂度为的求解算法。

在该算法中,我们通过一条扫描线,按照顺时针或者逆时针的顺序,依次检查各个顶点的可见性。我们假设扫描线起始的方向为坐标系的x轴方向,按顺时针方向扫描。

1.选取一个点作为中心点,按照顺时针(或逆时针)顺序扫描,将扫描到的点根据扫描角度值存入AVL树

上图按照顺时针顺序存储在中的值依次为:

图中n个点,依次被选取为中心点进行扫描操作,故时间复杂度为

在C++中可以直接使用STL中的multiset。


2.将与扫描线起始状态(坐标系的x轴方向)相交的线段按照交点距离值存入AVL树

上图存储在中的值依次为:


3.对内所有顶点,执行下列算法:

  1. 如果对于是可见的,添加到可见性图中。
  2. 如果对应的线段在扫描线的顺时针方向,将该线段存入中。
  3. 如果对应的线段在扫描线的逆时针方向且该线段已在中,将该线段从中删除。

 其中,是可见的,满足下列条件:

  1. 不在障碍物(多边形等)内部。
  2. 不在同一条线段上。
  3. 中的键值最小的线段不相交。

下面来演示该算法的执行过程:

当扫描线转到时,中最小线段为,两者相交,不可见,对应的两条线段在扫描线的顺时针方向,将两条线段存入中。 在中的值依次为:

当扫描线转到时,中最小线段为,两者相交,不可见,对应的两条线段在扫描线的顺时针方向,将两条线段存入中。 在中的值依次为:

当扫描线转到时,中最小线段为,两者相交,不可见,对应的两条线段在扫描线的逆时针方向,将两条线段从删除。 在中的值依次为:

算法按照这个过程,一直执行下去,处理完最后一个点结束,可得到关于的可见点集,时间复杂度为

n个点按照上述算法需执行n次,时间复杂度为

判断射线与线段是否相交

上述算法中的重要步骤之一是判断射线是否与线段相交。设射线起点为,方向为,判断该射线是否与线段相交。

这个问题即判断射线和线段是否存在至少一个交点,我们首先将射线和线段上的点用参数方程表示出来。

射线上点的参数方程可以表示为:

线段上点的参数方程可以表示为:

现在我们可以令,来寻找,其中。为了使结果显示更加整洁,我们设。其中的正交向量。

其结果为:

如果,那么该射线与线段相交。将带入原参数方程可求得交点坐标。

判断点是否在多变形内部

我们已经知道如何判断射线是否和线段相交,如果点在多边形内部,我们从该点引一条射线,那么该射线与多边形相交的边数一定为奇数。将多边形的所有边与该点发出的一条射线做相交判断。如果相交边数为偶数,该点在外部,否则在内部。

运行示例

_(:з」∠)_