點合并算法的思考

1.寫在前面

去年因為某項目遇到模型卡頓問題，分析原因發現是模型中點沒有進行合并，故而設計了點合并的技術方案，由于某些原因該方案未能實施，僅僅是方案，放在技術方案堆裡，以一篇文檔形式。

平時的積累尤其重要，嘗試更優，加之日積月累，會有比較大的進展和進步，技術如此，工作也一樣。

平時面試偶爾也會以該題目為背景問一下面試者，看看思路怎樣，有想法還不錯的，也有不知所措的...好了，閑扯到這裡，開始吧。

2.思路

2.1.方案一

ifcOpenShell是将點的hash作為key，建立map，map<pair<pair<x,y>, z>, T>，這樣利用map（特化的紅黑樹）的查取效率，效率較高，查取一次複雜度為o(logN)，整個點合并過程複雜度為o(N*logN)。這是一種實作成本低，且效率較高的方式，值得使用或借鑒。

2.2.方案二

曾經有面試者這樣回答：

以每個點為中心，以空間對齊的方式建立一定範圍的格子，比如坐标為(102.3, 5.6, 9.8)的點建立格子的範圍為x:[102,103)，y:[5,6)，z:[9,10)，格子對齊空間的位序為x:103,y:6,z:10，這樣，n個點建立格子，然後建立完也就點合并完成，複雜度為o(N)，此時如果某個格子有多個點，就認為這些點是誤差範圍内相同的點，就可以合并。

該思路對嗎？

如果隻建立格子而不進行格子間的去重合并，那麼這個過程複雜度确實是o(N)，但是這是滿足不了要求的，是以需要對格子進行去重歸并，單單是歸并，如果是高效的方法，複雜度也是o(N*logN)。

面試的同學又說了，

在建立格子的過程中進行格子查詢歸并，比如格子對齊空間的位序為x:103,y:6,z:10，那麼就去一個三維數組中利用下表索引快速定位的方式判斷是否存在，複雜度為o(1)，這樣整體複雜度還是o(N)。

這樣的說法正确嗎？

我們來推敲一下，數組存儲空間是連續的，下表索引定位複雜度确實是o(1)，如果存在這樣符合條件的數組就可以，那麼存在嗎？前提是對點清單所屬三維空間進行全區域覆寫的格子建立，形成全區域的覆寫的三維數組，然後每建立一個格子，就去進行代價為3*o(1)的查詢，傳回格子索引（即合并後點的索引）。看出問題了沒？“對點清單所屬三維空間進行全區域覆寫的格子建立，形成全區域的覆寫的三維數組”這個過程複雜度為多少？o(1)~o(n^3)？最壞為多少？這種方式恐怕是撿了芝麻，丢了大西瓜。

那麼可以在上述思路的基礎上進行改進嗎？

可以的，無須建立全空間區域覆寫的格子，将格子的三個索引作為key進行搜尋，其實和上述方案一是一樣的了。

2.3.方案三

利用布爾短路運算、紅黑樹、嵌套的動态生長的紅黑樹思路進行方案設計，

看到這裡應該還是困惑，這有什麼高效嗎？

布爾短路運算的特點是發現不一緻即傳回，無須進行後續計算，

紅黑樹的特點是搜尋高效，複雜度為o(n)，

哦？好像懂了，懂了？那麼嵌套的紅黑樹又是作甚呢？

主要是用來優化記憶體使用，嗯？

如果10個點的x坐标一樣，那麼即存儲一份x資料，如果是map<pair<pair<x,y>, z>, T>的方式，那麼豈不是要存10份x，y，z資料？大機率是的。

那為什麼要紅黑樹嵌套後為什麼還要動态生長呢？主要是為了和布爾短路運算一起使用，搜尋的過程中，當判斷第一層哈希值（x）一樣時才進行下一層哈希值的計算（此時就是樹的生長過程），如果不一樣，那麼對于該目标點，僅計算第一層哈希值即可，傳回點索引值。

想一想，計算目标點哈希值複雜度為多少？o(1)~3*o(1)，相對于上面的方案的3*o(1)是不是高效了些？當然查詢的過程也一樣，短路運算。

實際上該方案複雜度仍為o(N*logN)，但是系數相比降下來了，而且記憶體占用也少，對于極端的情況，

1. n個點都一樣：複雜度為o(N)，占用記憶體為常量級（3坐标分量對應的float+3個單元素的紅黑樹），此時效率和記憶體和方案一相差無幾，幾乎一樣。
2. n個點都不一樣（x都不一樣）：複雜度為o(N*logN)，但是！隻計算了n個點的x哈希值（比如x*100，保留兩位小數對比），隻存儲了n個點的x哈希值；如果是方案一呢？計算n個點的x,y,z哈希值，且存儲x,y,z哈希值，查詢過程倒是都是短路的，判斷x不一樣即退出。

明白了沒？方案三整體複雜度沒有下降，但是其效率系數和記憶體系數均有提升，因為實際點清單情況基本都介于上述兩個極端之間。

進行完點合并之後，“嵌套的動态生長的紅黑樹”是一顆不完全生長的樹，即存在x，y都一樣的點對應的分支是完全生長的，其他的都是不完全生長的，記憶體和計算過程均有精簡。

2.4.方案四

将x,y,z計算一個哈希值，這樣建立一個map就可以，省事。這樣理論可行，但是将三個坐标分量壓縮為一個哈希值會有哈希計算重複的機率，也就是有不準确的機率，可能會把兩個根本不一樣的點認為是同一個點。

 3.總結

平時的積累尤其重要，嘗試更優，加之日積月累，會有比較大的進展和進步，技術如此，工作也一樣。

 該思路可以擴充開來，用于更多的場景優化。

不要吝啬你的點贊、收藏、評論，這也是一種表達。

熬夜傷身體，也傷腦...