計算幾何学と幾何学的グラフ理論において、平面直線グラフ（PSLG）は、直線平面グラフまたは平面直線グラフとも呼ばれ、平面グラフの辺が直線セグメントにマッピングされるように平面グラフを平面に埋め込むものである。 [1]ファリーの定理（1948）は、すべての平面グラフがこの種の埋め込みを持つと述べている。
計算幾何学では、PSLG は平面細分と呼ばれることが多く、細分は曲線境界ではなく多角形であるという仮定または主張に基づいています。
PSLGは、地理情報システムにおける地図など、様々な地図の表現として利用される。[2]
PSLGの特殊な例として、三角形分割（多角形三角形分割、点集合三角形分割）が挙げられます。点集合三角形分割は、グラフを平面に保ちながら直線の辺を追加することが不可能であるという意味で、最大PSLGです。三角形分割は様々な分野で多くの応用があります。
PSLGはユークリッドグラフの特殊な種類と見なすことができます。しかし、ユークリッドグラフに関する議論では、その計量特性、すなわち頂点間の距離が主な関心事となるのに対し、PSLGでは位相特性が主な関心事となります。ドロネー三角形分割など、一部のグラフでは、計量特性と位相特性の両方が重要となります。
表現
PSLGを表現するためのデータ構造として、 Winged-edgeデータ構造、Halfedge、Quadedgeの3つがよく知られています。Winged-edgeデータ構造は3つの中で最も古いものですが、その操作には複雑なケースの区別が必要になることがよくあります。これは、エッジ参照がエッジの方向を格納せず、面の周りのエッジの方向が一貫している必要がないためです。Halfedgeデータ構造は、エッジの両方の方向を格納し、それらを適切にリンクすることで、操作と格納方式を簡素化します。Quadedgeデータ構造は、平面細分とその双対を同時に格納します。そのレコードは、エッジレコード（エッジごとに4つ）のみで明示的に構成され、簡略化された形式でPSLGの格納に適しています。[3]
PSLGに関する問題点
- 点の位置。クエリポイントがPSLGのどの面に属しているかを調べます。
- 地図オーバーレイ。2つのPSLG（地図）のオーバーレイを求めます。これは、同時に埋め込まれた2つのPSLGによる平面の細分化です。GISでは、この問題は「主題図オーバーレイ」として知られています。
参照
- 二重連結エッジリスト、PSLGを表現するデータ構造
- 局所特徴サイズ
参考文献
- ^ Preparata, Franco P. ; Shamos, Michael Ian (1985).計算幾何学入門（第1版）. Springer-Verlag . ISBN 0-387-96131-3. 第2刷、訂正・増補、1988年：ISBN 3-540-96131-3; ロシア語訳、1989年：ISBN 5-03-001041-6。
- ^ Nagy, George; Wagle, Sharad (1979年6月). 「地理データ処理」. ACM Computing Surveys . 11 (2). Association for Computing Machinery : 139–181 . doi :10.1145/356770.356777. S2CID 638860.
- ^ データ構造とアプリケーションのハンドブック、DP MehtaとS. Sahni、2005年、ISBN 1-58488-435-5第17章
