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

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

前面都是廢話，現(xiàn)在正式開始，問題是這樣的：

1-Dimensional Heightfield Visibility Query Problem

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

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

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

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

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

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

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

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

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

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

1. sparse table 的預(yù)計算過程

對于每個點(diǎn) 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)。整個查詢過程的時間復(fù)雜度為 O(1).

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

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

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

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

轉(zhuǎn)載于:https://www.cnblogs.com/atyuwen/archive/2011/03/09/visibility_query.html

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

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。