Planar_straight-line_graph
計算幾何学および幾何グラフ理論では、平面直線グラフ、略してPSLG (または直線平面グラフ、または平面直線グラフ) は、次のような平面への平面グラフの埋め込みに使用される用語です。そのエッジは直線セグメントにマッピングされます。 Fáry の定理(1948) は、すべての平面グラフにはこの種の埋め込みがあると述べています。
平面直線グラフの例
計算幾何学では、PSLG は、サブディビジョンが曲線の境界を持つのではなく多角形であるという仮定または主張を伴って、平面サブディビジョンと呼ばれることがよく
PSLG は、地理情報システムの地理地図など、さまざまな地図の表現として機能する場合が
PSLG の特殊なケースは、三角形分割 (ポリゴン三角形分割、点集合三角形分割) です。点集合三角形分割は、グラフを平面に保ちながら直線エッジを追加することが不可能であるという意味で、最大の PSLG です。三角形分割は、さまざまな分野で数多くの用途が
PSLG は、特別な種類のユークリッド グラフとみなされる場合がただし、ユークリッド グラフに関する議論では、主な関心はその計量特性、つまり頂点間の距離ですが、PSLG の場合、主な関心は位相特性です。ドロネー三角形分割などの一部のグラフでは、計量プロパティと位相プロパティの両方が重要です。
コンテンツ
1 表現
2 PSLGの問題点
3 こちらも参照
4 参考文献
表現
PSLG を表現するためのよく知られた 3 つのデータ構造が存在します。これらは、Winged-edgeデータ構造、Halfedge、およびQuadedgeです。winged-edge データ構造は 3 つのデータ構造の中で最も古いものですが、これを操作するには複雑な大文字と小文字の区別が必要になることがよくこれは、エッジ参照にはエッジの方向が保存されず、面の周囲のエッジの方向が一貫している必要がないためです。ハーフエッジ データ構造はエッジの両方の方向を保存し、それらを適切にリンクすることで、操作と保存スキームを簡素化します。Quadedge データ構造は、平面サブディビジョンとそのデュアルの両方を同時に保存します。そのレコードは明示的にエッジ レコードのみ (エッジごとに 4 つ) で構成され、簡略化された形式で PSLG を格納するのに適しています。
PSLGの問題点
ポイントの位置。クエリ ポイントの場合、それが PSLG のどの面に属しているかを見つけます。
マップオーバーレイ。2 つの PSLG (マップ) のオーバーレイを見つけます。これは、同時に埋め込まれた 2 つの PSLG による平面の細分化です。GIS では、この問題は「主題図オーバーレイ」として知られています。
こちらも参照
二重接続エッジ リスト、PSLG を表すデータ構造
局所特徴量のサイズ
参考文献
^ フランコ P. プレパラタとマイケル イアン シャモス(1985)。計算幾何学 – 入門。スプリンガー・フェルラーグ。ISBN 0-387-96131-3。初版: ; 第 2 刷、修正および増補、1988 年:
ISBN 3-540-96131-3 ; ロシア語翻訳、1989 年:
ISBN 5-03-001041-6。
^ ジョージ、ナギー; Wagle、Sharad (1979 年 6月）、「地理データ処理」、ACM Computing Surveys、11 (2): 139–181、doi : 10.1145/356770.356777、S2CID 638860
^ データ構造とアプリケーションのハンドブック、DP Mehta および S. Sahni、2005 年、
ISBN 1-58488-435-5 、第 17 章