The scientist builds in order to study,
the engineer studies in order to build.
-- Fred Brooks

最近在忙各種畢業(yè)事項之余，一直在努力搞 Real-time GI ，可惜時間總是顯得如此的不夠用，搞完了 RSM 卻忘了做 SRM，哈哈。為了避免長時間不思考算法問題，導致智商下降，決定弄個小問題來做一下。這個問題也是在搞 GI 的時候想到的，該問題的二維版本跟 GI 也算是有那么一丁點關系，盡管從原則上來說只用一個高度場來表示場景的話顯然丟失了太多信息。

前面都是廢話，現在正式開始，問題是這樣的：

1-Dimensional Heightfield Visibility Query Problem

給定一個一維的高度場，可用數組 H 來表示，其中第 i 個元素 H[i] 代表點 i 處的高度，判斷其中任意兩點是否相互可見？

比如，若 H = {1, 0, 2, 2, 1, 3, 1, 0}，根據 H 可以繪制出一個輪廓如圖 1 所示：

??????? ????? 圖1：1維高度場示意圖

我們想查詢任意兩個點 i, j 是否相互可見（用 visible(i, j) 來表示，另外在后文中均假設 i <= j）。比如，在圖1中有 visible(2, 5) = true（見圖中綠色虛線），而 visible(3, 6) = false（見圖中紅色虛線）。

這個問題說簡單也簡單，因為若要查詢 visible(i, j)，只需要順序從 H[i] 掃描到 H[j] ，判斷一下斜率即可。這樣每次查詢的時間復雜度為 O(n)。

但是我們希望能做得更好，最好是能設計一個 online algorithm，先對 H 進行一下預處理，然后將每次查詢的時間降為 O(1)。這當然可以做到，因為很明顯我們可以預先將所有的 visible(i, j) 計算好并存儲起來，這樣的話需要 O(n^2) 的預處理時間，O(1) 的查詢時間，同時需要 O(n^2) 的存儲空間，為方便我們采用這樣一種方式 <O(n^2), O(1) | O(n^2)> 來表示其復雜度。然而，當 n 較大時，這里 O(n^2) 的空間需求是不太能夠接受的，如果你有過設計 online algorithm 的經驗，此時的第一個想法可能會是看看能不能將空間復雜度降為 O(nlogn)，同時仍然維持 O(1) 的查詢時間。

幸運的是，這的確是可能的，采用常規(guī)的 sparse table 就可以做到。當然，這里對 sparse table 的處理與經典的 RMQ 問題稍有差別，因為這里需要建立兩個 sparse table。其基本動機基于以下觀察：

定理1：對于任意一個點對 (i, j)，以及任意的另外兩個點 k1, k2 位于 i, j 之間，且滿足 k1 >= k2 – 1。若用 partial(i, k, j) 來表示點 i 在經過 i 到 k 之間的所有點后是否還能看到點 j（意思是不考慮 k+1 到 j 之間的點是否構成遮擋），于是有：

visible(i, j) 當且僅當 partial(i, k1, j) 且 partial(j, k2, i)。

定理1的證明很簡單，在這里略過。事實上只要你想到它，那么它幾乎就是不證自明的。若設 slope(i, k) 為點 i 在經過 i 到 k 之間的所有點后的最小未被遮擋斜率，那么只要知道 slop(i, k) 就能在 O(1) 時間內計算出 partial(i, k, j)。這個事實再加上定理1就構成了使用 sparse table 的基礎：

1. sparse table 的預計算過程

對于每個點 i, 計算并存儲 slope(i, i + 1), slope(i, i + 2), slope(i, i + 4), slope(i, i + 8), …. 以及 slope(i, i – 1), slope(i, i – 2), slope(i, i – 4), slope(i, i – 8)….

2. 查詢過程

若要查詢 visible(i, j), 先計算出 k = 2^( floor(log2( j - i) ), 即不大于 j – i 的最大2冪。然后從 sparse table 中查得 slope(i, i + k), slop(j, j – k)，計算出 partial(i, i + k, j) 和 partial(j, j – k, i)，從而得到 visible(i, j)。整個查詢過程的時間復雜度為 O(1).

很遺憾在這里對 sparse table 的構造并不能像 RMQ 那樣做到 O(nlogn)，如果直接暴力搞的話需要 O(n^2) 的時間，使得整個 online algorithm 的復雜度為 <O(n^2), O(1) | O(nlogn)>。所幸，通過一些簡單的優(yōu)化，可以大幅度的提高建立 sparse table 的效率，經過我測試的數千組數據表明，優(yōu)化后的算法的期望復雜度很有可能是 <O(nlognlogn, O(1) | O(nlogn)>，但我并沒有進行詳細的分析，因為對于這個問題很難去假定其輸入應該滿足什么樣的分布條件。在我所使用測試的數據中，每個點的高度值都是互相獨立的隨機數，這在直觀上其實并不符合現實。

優(yōu)化的方法說起來很麻煩，懶得講了，感興趣的可以在直接看源代碼。

如果不是要求查詢時間一定為O(1)，那么下面這個方法也可能行得通。先建立一個 cartesian tree, 然后通過 LCA 來搞，對于兩個點 (i, j)，若 LCA(i, j) != i && LAC(i, j) != j，那么直接就可以返回 visible(i, j) = false. 否則若某個點是另一個點的祖先，比如 j 是 i 的祖先，那么可以在樹中從 i 遍歷到 j 來進行判斷。中間也可以根據凸性建立一些額外的連接來進行優(yōu)化。這樣預處理時間和空間都為 O(n) ，查詢時間最壞也為 O(n)，但大多數情況下應該非常快，因為 cartesian tree 的期望高度是 O(logn) 的，何況還有一堆優(yōu)化手段可以搞，比如可以利用凸性建立一些額外的連接等等。哈，以后有時間再來嘗試一下。

如果有人想到更好的方法，歡迎討論…

轉載于:https://www.cnblogs.com/atyuwen/archive/2011/03/09/visibility_query.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的1-Dimensional Heightfield Visibility Query的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。