データ構造の平面直線グラフ（PSLG）

計算幾何学の場合、平面直線グラフ、略してPSLG（または直線平面グラフ、または平面直線グラフ）は、平面に平面グラフを埋め込むために実装される用語として定義されます。そのエッジは直線セグメントにマッピングされます。 Fáryの定理（1948）のステートメントは、すべての平面グラフにこの種の埋め込みがあるというものです。

計算幾何学の場合、PSLGは平面細分割と呼ばれることが多く、細分割は多角形であるという仮定または主張があります。

次数1の頂点がない場合、PSLGは平面の細分割を多角形領域に定義します。その逆も同様です。次数1の頂点がないため、さまざまなアルゴリズムの説明が簡単になりますが、必須ではありません。

さまざまな地図の表現は、地理情報システムの地理地図など、PSLGによって提供される場合があります。

PSLGにはいくつかの特殊なケースがあります。特殊なケースは三角形分割です（ポリゴン三角形分割、ポイントセット三角形分割）。ポイントセットの三角形分割は、グラフを平面に保ちながら直定規を追加できないという意味で、最大PSLGです。三角測量には、非常に多くの分野でさまざまな用途があります。

PSLGは、特別な種類のユークリッドグラフと見なすことができます。さらに、ユークリッドグラフに関する議論では、主な関心はそれらのメトリックプロパティ、つまり頂点間の距離ですが、PSLGの主な関心はトポロジカルプロパティです。ドロネー三角形分割などの一部のグラフの場合、メートル法と位相特性の両方が重要です。

表現

PSLGは、3つのよく知られたデータ構造で表されます。これらのデータ構造は、ウィングエッジデータ構造、ハーフエッジ、およびクアッドエッジです。ウィングエッジデータ構造は3つのうちで最も古いものですが、それを操作するには複雑な大文字と小文字の区別が必要になることがよくあります。そのエッジ参照の背後にある理由は、エッジの方向を保存せず、面の周りのエッジの方向が一貫している必要はありません。ハーフエッジデータ構造は、エッジの両方の方向を格納し、それらを適切にリンクして、操作とストレージスキームを簡素化するのに役立ちます。クアッドエッジデータ構造は、平面サブディビジョンとそのデュアルの両方を同時に格納するのに役立ちます。そのレコードは、エッジレコードのみで明示的に構成され、エッジごとに4つあり、簡略化された形式でPSLGを保存するのに役立ちます。