二维空间中的声线模拟

感觉这个挺有意思的就做了一下，虽然是和虚拟现实沾边的东西，但说不定以后在数据挖掘上也能用来给数据在不同属性上分类什么的。

做了个最简单的：模拟声音在理想二维空间中的反射，而且假设二维空间是封闭的矩形区域，其中可能有若干的垂直或者水平的墙，将空间分割为若干的子空间，空间中有一个声源和一个接收点。

声源向四周均匀发射n条声线，反射深度为m（经过m次反射，强度会衰减到0），空间中公有y条互不交叉的墙壁。

例如下图是程序的演示效果：

蓝色的为墙壁，共有7条，声源在左上角，向周围均匀发出10条声线，最终经过反射，有1条到达接收者。

实现这个的算法有很多，其中效率比较高的是BSP二叉树算法。

BSP树就是用来对N维空间中的元素进行排序和查找的二叉树。BSP树表示整个空间，BSP树中的任意一个接点表示一个凸的子空间。每个接点包含一个“超平面”，将这个接点表示的空间分割成两个子空间。每个接点除了保存其两个子接点的引用以外，还可以保存一个或多个元素。对于N维空间，超平面为N-1维的对象。通常，用BSP树来表示二维或者三维空间，这时，空间中的元素分别指的是线段和多边型。

在二维空间中，就是选择一条线段作为树的根节点，被线段分隔开的两个空间中的线段分别在左右两棵子树中。二叉树调整平衡后查找的平均时间纷杂度为O(log n)，所以整个绘制声线的过程的时间复杂度为n*m*log(y)。

但是建个平衡的BSP二叉树要写多少代码啊，我就用了个很naive的算法，压根没有去存储空间信息，直接存下了所有的墙壁线段，其中求一条声线的反射线的伪代码如下：

输入：一条声线L

返回：输入声线的反射声线RL

List<wall> walls;
List<Point> points;
遍历所有的墙壁
{
	如果墙壁与L有交点P
	{
		walls.add(墙壁)
		points.add(P)
	}
}
遍历points，找出距离L出射点最近的一个反射点Pr
根据Pr和对应的wall求出反射声线RL，返回RL

用了这个算法，整个过程的复杂度就是m*n*y了，但是对于几十条墙壁、几十条声线和十几个反射深度，还是眨眼功夫的事，效果如上图所示。绘图用的是GDI+。