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個元素的逆序數，最后在排序過程中合并前后兩部分之間的逆序數。

小結

從上面的分析中可以看出，在把一個相當復雜的解答轉換成一個相對容易的解答的過程中，經歷了三次的問題轉換和轉化。同樣地，在實際問題的分析中，我們也需要盡量考慮，問題是否就這么復雜，是否可以進一步轉化呢？是否有更簡單或優雅的辦法來實現呢？