1.7 光影切割问题

不少人很爱玩游戏，例如CS，游戏设计也成为程序开发的热点之一。我们假设要设计破旧仓库之类的场景作为战争游戏的背景，仓库的地面会因为阳光从屋顶的漏洞或者窗口照射进来而形成许多光照区域和阴影区域。简单起见，假设不同区域的边界都是直线，我们把这些直线都叫做“光影线”，并假设没有光影线是平行于Y轴的，且不存在三条光影线相交于一点的情况。如图1-9所示。

那么，如果我们需要快速计算某个时刻，在X坐标[A, B]区间的地板上被光影划分成多少块。如何设计算法？

分析与解法

解法一

在分析问题之前，我们可以先研究一下图形中不同线段之间的关系。

在图1-10中，每一条直线代表一条光影。那么，直线相交之后产生的分块信息是否和直线的交点有直接的关系呢？

可以先通过分析比较简单的例子来得到一些规律。

对于两条直线的情况，如图1-11所示。

显然，两条直线最多能把区间分划为4个部分。

对于三条直线，会有如下的情况，如图1-12所示。

三条直线如果只有两个交点，会把空间分成6个部分（图1-12左）；如果有三个交点，会把空间分为7个部分（图1-12右）。

那么，如下规律可循：

两条直线→一个交点→空间分成4个部分

三条直线→两个交点→空间分成6个部分

三条直线→三个交点→空间分成7个部分

由上可以推出，每增加一条直线，如果增加m个交点，那么这条直线被新增加的m个交点，分成（m+1）段。每一段直线会将原来一块区域分成两块，因此，新增加（m+1）块新区域。如果总共有N条直线，M个交点，那么区域的数目为N+M+1。

因此，平面被划分成多少块的问题可以转化为直线的交点有多少个的问题。

那么，将N条直线逐一投影到坐标区间上，假设当第k条直线投影到坐标区间的时候，它与之前的k-1条直线的交点为Nk个，那么它使得区间[A, B]之间的平面块增加Nk+1个（为什么），全部直线（N条）都投影完毕之后，我们可得到区间[A, B]平面被划分的块数，即，其中1为区间[A, B]的初始平面块数。

因此，只要求出所有直线两两相交的交点，然后再查找哪些交点在[A, B]之间，进而就可以求出平面被划分的块数。我们可以考虑将N条直线的所有交点存储于数组Intersect中，然后进行计算。这样，原问题就转化成查找交点数组的问题了。

需要对数组进行初始化。初始化的过程，实质上就是计算所有交点的过程。我们需要查询每条直线是否与其他N-1条直线有交点，初始化的时间复杂度将为O（N2）。每次查询的时间复杂度为O（|Intersect|）。

如果在初始化后对所有交点按X轴坐标排序，则复杂度为O（N2+|Intersect|×log|Intersect|），其中|Intersect|×log|Intersect|为排序时间，之后可采用二分查找，每次查询的时间复杂度将为O（log|Intersect|）。

解法二

但是，如果查询比较少，我们是否可以不浪费那么多时间来预处理呢？

分析上面两个情况（如图1-13所示），左图为有一个交点的情况，两条直线a和b与左边界的交点从上到下按顺序为（a, b），右边界上的交点顺序为（b, a），可以看到，顺序被反过来了，因为它们在两个边界之间有一个交点。如果没有交点，它们与边界的交点顺序则不会有变化。

进一步分析图1-13的右图可以知道，区域内的交点数目就等于一个边界上交点顺序相对另一个边界交点顺序的逆序总数（这里利用到条件“没有三条直线相交于一个点”）。在右图中，左边界顺序为（a, b, c），右边界为（c, b, a），假设a=1, b=2, c=3，那么（c, b, a）=（3, 2, 1），它的逆序数为3。

因此，问题转化为求一个N个元素的数组的逆序数（第三次对问题进行了转换☺）。

最直接的求解逆序数方法还是O（N2），如果用分治的策略可以将时间复杂度降为O（N×log2N），求N个元素的逆序数的分治思想如下，首先求前N/2个元素的逆序数，再求后N/2个元素的逆序数，最后在排序过程中合并前后两部分之间的逆序数。

小结

从上面的分析中可以看出，在把一个相当复杂的解答转换成一个相对容易的解答的过程中，经历了三次的问题转换和转化。同样地，在实际问题的分析中，我们也需要尽量考虑，问题是否就这么复杂，是否可以进一步转化呢？是否有更简单或优雅的办法来实现呢？