現在常用的地圖標記避讓演算法有哪些啊?

01-25

在地圖標註中，有些標註會出現位置衝突，這時候就需要進行避讓，更換標註的位置，使得地圖上可以儘可能多的顯示標註信息而又不重疊。
想問下現在業內成熟的避讓演算法又哪些啊。
其中實時標註計算的時候使用哪種比較好

離線切圖繪製中，使用哪種會比較好。

一點點點帥其實講的挺好的，我簡單補充

註記是NP難問題，ArcGIS為了提升自己的註記配置效果，專門購置了Maplex註記引擎；商業實現上來看，Maplex是最值得學習的；開源實現的話，可以參考mapserver的maplabel.c或QGIS。

1. 關於註記的位置：

4方位模型、8方位模型、滑動模型

2. 實時標註和離線切圖的時間要求不同，導致其演算法實現的差異。

對於實時標註而言，演算法設計主要面向如何實時避讓和註記，需要將註記位置預處理和實時配置結合起來，合理的預存儲數據結構將能夠實現最合理的結合；如Petzold提出的reactive conflict graph是其中一種數據結構。

離線切圖(將矢量數據渲染成地圖瓦片)的話，不太需要關注時間效率，因此註記效果是演算法追求的目標。因此，各種數學優化演算法如模擬退火、遺傳演算法等在這裡都有用武之地。

自動地圖標記應該算是GIS中最複雜的問題之一吧（屬於NP複雜度問題，所以通常不能找到最優解，只能找到較優解），已經有不少的文章討論過相關演算法。跟解決其他NP問題一樣，大部分演算法的思路都是提供一個啟發（heuristic）給演算法作為下一步執行的依據。

常見的演算法大致可分為這麼幾類（或者是他們的結合）：

基於規則的演算法（rule-based algorithms）：給演算法預先擬定一些規則（這些規則的好壞會在很大程度上影響結果的好壞），按照這些規則執行演算法。比如對地名的標註：首先標註且不衝突重要城市的標註；盡量標註在城市的上方，如果遇到衝突則再依次嘗試右左下。其他規則還可以描述諸如標註的方向，邊緣處如何解決等等。

局部優化演算法（local optimization algorithms）：依次擺放標註盡量使之不出現衝突，直到某一處標記所有潛在的位置都會出現衝突時，則選擇衝突最少（例如給標註擬定一個輪廓，選擇重合面積最少的）的一處擺放。這個方法通常結果不會太好，但速度很快。

分而治之演算法（divide-and-conquer algorithms）：這既可以作為一種策略，也可以作為一種演算法的思路。作為策略，比如很有可能在有些地方標註比較稀疏（例如沙漠地區城市較少），可以將那些地方隔離，用快速簡單的演算法得到令人滿意的結果，這在很大程度上能夠提高整體的效率（如果地地圖很大標註很多，運算時間可能會很長）；而在那些標註密集的地方採用更複雜的演算法。作為演算法，將地圖內容分成小塊進行標註，小塊再分成更小的小塊（遞歸地），當集合小到可以進行較好的標註（比如分到只對兩個地名進行不衝突標註），然後再考慮他們的結合。這種演算法分割和結合的方法對結果影響比較大。

我覺得除非你自己就是想研究/比較各種演算法或者想提出新演算法，或者對標註結果有特別或較高的要求，不然沒有必要自己去實現這些演算法（感覺要花點時間）。ArcGIS QGIS這些平台工具一般都包含地圖標記工具。

QGIS: 2. Lesson: The Label Tool

ArcGIS: ArcGIS Help 10.1

好像沒聽過離線切圖，不好發表意見。