Graphique linéaire planaire - Planar straight-line graph

Un exemple de graphique linéaire planaire

En géométrie de calcul , un graphe planaire en ligne droite , en court PSLG , (ou graphe plan en ligne droite , ou graphe en ligne droite plane ) est un terme utilisé pour une incorporation d'un graphe plan dans le plan de telle sorte que ses arêtes soient cartographiées en segments de ligne droite. Le théorème de Fáry (1948) stipule que chaque graphe planaire a ce type d'enfouissement.

En géométrie de calcul, les PSLG ont souvent été appelés subdivisions planes , avec une hypothèse ou une affirmation que les subdivisions sont polygonales plutôt que d'avoir des limites courbes.

Les PSLG peuvent servir de représentations de diverses cartes , par exemple des cartes géographiques dans des systèmes d'information géographique .

Cas particuliers de PSLGs sont triangulations ( triangulation des polygones , triangulation point ensemble ). Les triangulations par ensembles de points sont des PSLG maximales dans le sens où il est impossible de leur ajouter des arêtes droites tout en gardant le graphe planaire. Les triangulations ont de nombreuses applications dans divers domaines.

Les PSLG peuvent être considérés comme un type particulier de graphes euclidiens . Cependant, dans les discussions impliquant des graphes euclidiens, l'intérêt principal est leurs propriétés métriques, c'est-à-dire les distances entre les sommets, tandis que pour les PSLG, l'intérêt principal est les propriétés topologiques. Pour certains graphiques, tels que les triangulations de Delaunay , les propriétés métriques et topologiques sont importantes.

Représentations

Il existe trois structures de données bien connues pour représenter les PSLG, à savoir la structure de données Winged-edge , Halfedge et Quadedge . La structure de données ailée est la plus ancienne des trois, mais sa manipulation nécessite souvent des distinctions de cas compliquées. En effet, les références d'arête ne stockent pas la direction des arêtes et les directions des arêtes autour d'une face n'ont pas besoin d'être cohérentes. La structure de données demi-bord stocke les deux orientations d'un bord et les lie correctement, simplifiant les opérations et le schéma de stockage. La structure de données Quadedge stocke simultanément la subdivision plane et son double. Ses enregistrements se composent explicitement uniquement d'enregistrements de bord, quatre pour chaque bord, et sous une forme simplifiée, il convient au stockage des PSLG.

Problèmes en termes de PSLG

  • Emplacement du point . Pour un point de requête, recherchez à quelle face du PSLG il appartient.
  • Superposition de carte . Trouvez la superposition de deux PSLG (cartes), qui est la subdivision du plan par les deux PSLG intégrés simultanément. Dans le SIG, ce problème est connu sous le nom de " superposition de cartes thématiques ".

Voir également

Références

  1. ^ Franco P. Preparata et Michael Ian Shamos (1985). Géométrie computationnelle - Une introduction . Springer-Verlag . 1ère édition: ISBN   0-387-96131-3 ; 2e impression, corrigée et augmentée, 1988: ISBN   3-540-96131-3 ; Traduction russe, 1989: ISBN   5-03-001041-6 .
  2. ^ Nagy, George; Wagle, Sharad (juin 1979), "Geographic Data Processing", ACM Computing Surveys , 11 (2): 139-181, doi : 10.1145 / 356770.356777
  3. ^ Manuel des structures de données et des applications, DP Mehta et S. Sahni, 2005, ISBN   1-58488-435-5 , chapitre 17