資料結構中的平面直線圖 (PSLG)

在計算幾何中，平面直線圖 (簡稱 PSLG)（或直線平面圖，或平面直線圖）定義為平面圖在平面上的嵌入，其邊對映為直線段。Fáry 定理 (1948) 的陳述是，每個平面圖都有這種嵌入。

在計算幾何中，PSLG 通常被稱為平面細分，並假設或斷言細分是多邊形的。

如果沒有度為 1 的頂點，PSLG 定義了平面到多邊形區域的細分，反之亦然。度為 1 的頂點的缺失簡化了各種演算法的描述，但這並非必需的。

PSLG 可以用於表示各種地圖，例如地理資訊系統中的地理地圖。

PSLG 有一些特殊情況。特殊情況是三角剖分（多邊形三角剖分，點集三角剖分）。點集三角剖分是最大 PSLG，因為在保持圖平面性的同時，不可能向其中新增直線邊。三角剖分在許多領域都有各種應用。

PSLG 可以看作是歐幾里德圖的一種特殊型別。此外，在涉及歐幾里德圖的討論中，主要關注的是它們的度量屬性，即頂點之間的距離，而對於 PSLG，主要關注的是拓撲屬性。對於某些圖，例如 Delaunay 三角剖分，度量屬性和拓撲屬性都很重要。

表示

PSLG 由三種眾所周知的資料結構表示。這些資料結構是帶翼邊資料結構、半邊資料結構和四邊資料結構。帶翼邊資料結構是最古老的三種之一，但是操作它通常需要複雜的案例區分。其原因在於邊引用不儲存邊方向，並且面周圍邊的方向不必一致。半邊資料結構用於儲存邊的兩種方向並正確地連結它們，從而簡化操作和儲存方案。四邊資料結構用於同時儲存平面細分及其對偶。它的記錄只明確包含邊記錄，每條邊四個，簡化形式可用於儲存 PSLG。

Arnab Chakraborty

更新於：2020年1月7日

315 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習