Graphe planaire depuis un arrangement de droites

Pour représenter visuellement ce problème, il faut donc pouvoir représenter de manière logicielle un arrangement de droites et le graphe dual (ou graphe des cellules) associés. Autrement dit : à partir d'un arrangement de n droites en position générale, calculer le graphe dual.

Structures de données

Aperçu

Représentation de la structure de données

Détails

Les points sont représentés par un couple de coordonnées P = (x,y).

Les droites sont représentées par un couple de points différents D = (A, B). Des méthodes getSlope et getY0 existent pour accéder respectivement au coefficient angulaire ou à l'ordonnée à l'origine.

Les graphes planaires peuvent être représentés via une DCEL [1]. Ici, vu que nous sommes dans un cas particulier où toutes les faces sont convexes (et sans "trous"), on peut utiliser une version simplifiée des DCEL avec:

  • Une liste de Vertex, des structures composées des champs suivants:
    • coordinates: Un point (x, y)
    • incidentEdge: Une demi-arête sortante (choisie arbitrairement)
  • Une liste de Face, des structures composées des champs suivants:
    • outerComponent: Une demi-arête de sa bordure (choisie arbitrairement)
  • Une liste de HalfEdge, des structures composées des champs suivants:
    • origin: Le Vertex d'origine (sens trigonométrique autour de la face)
    • twin: La demi-arête correspondante sur une autre face
    • incidentFace: La face bornée par la demi-arête.
    • next: La HalfEdge suivante dans le tour de IncidentFace
    • prev: La HalfEdge précédente dans le tour de IncidentFace

On définit également les méthodes suivantes: 

function HalfEdge.destination()
    return self.twin.origin
function Face.getBorder()
    var currentHalfEdge = this.OuterComponent
    var startVertex = currentHalfEdge.origin
    var border = {}
    do
        border.add(currentHalfEdge.origin
        currentHalfEdge = currentHalfEdge.next
    while currentHalfEdge.origin != startVertexfunction Vertex.getNeighbors()
    var neighbors = {}
    var currentHalfEdge = this.incidentEdge
    var startEdge = currentHalfEdge
    do
        neighbors.add(currentHalfEdge.destination)
        currentHalfEdge = currentHalfEdge.twin.next
    while currentHalfEdge != startEdge

Pour simplifier la représentation en mémoire, on ne représente pas les faces extérieures (infinies) comme telle. On ajoute donc quatre droites supplémentaires à l'arrangement qui servent à borner l'espace et qui correspondent aux bords de l'écran.

Obtenir le DCEL : Méthode itérative

Algorithme

Pour obtenir le DCEL depuis l'arrangement de droite, on part d'une face vide représentant tout l'espace, puis on ajoute les droites une à une, en modifiant à chaque fois les faces affectées. Pour cela, en partant de la première face rencontrée, on évolue de face en face dans le DCEL avec la procédure suivante:

  • Trouver les deux demi-arêtes de la face intersectée par la droite.
  • Créer deux nouvelles demi-arêtes jumelles ayant pour origine les deux intersections
  • Modifier les champs next et prev des demi-arêtes adjacentes aux demi-arêtes intersectées
  • À ce niveau, la face d'origine a été coupée en deux par la droite. Il faut donc ajouter une nouvelle face correspondant à la deuxième moitié de la face d'origine. 
  • Prendre la demi-arête twin de la deuxième demi-arête intersectée pour trouver la face suivante.
Illustration de l'état initial de l'algorithme avant l'ajout d'une droite

Complexité

La complexité de l'algorithme dépend du nombre d'arêtes dans les faces rencontrées par chaque droite. On définit donc la zone d'une droite dans un graphe planaire comme l'ensemble des faces traversées par la droite. Par exemple, voici la zone de deux droites différentes dans le même arrangement de droites :  

 Zone d'une droite dans un arrangement (1/2)
Zone d'une droite dans un arrangement (2/2) 

La complexité de la zone (le nombre de demi-arêtes de la zone) est montré être linéaire dans [1]. Vu qu'on ajoute itérativement n droites, chacune avec une complexité O(n), la complexité finale de l'algorithme est de O(n2). À titre de comparaison, un algorithme de balayage adapté de celui vu au cours demande une complexité de O(n2 log n).

Obtenir le graphe dual depuis le DCEL

On veut maintenant le graphe dual du graphe des segments donnés par le DCEL. Cependant, ce graphe dual ne sera utilisé que pour calculer des plus longs chemins. On peut donc simplement le représenter comme une liste de sommets et une liste d'arêtes les reliant.
function DCEL.getDual()
    // create vertices list from primal faces
    var faceToVertex = dictionary (key: Faces, value: Vertices)
    for face in self.faceList
        var verticeList = face.getBorder()
        faceToVertex[face] = average(verticeList)
    var dualVertices = values of faceToVertex
    // create edge list from primal twin edges
    var dualEdges = empty list
    for halfEdge in self.halfEdgeList
        var originFace = face of halfEdge
        var destinationFace = face of halfEdge.twin
        var originP = faceToVertex[originFace]
        var destinationP = faceToVertex[destinationFace]
        dualEdges.add([originP, destinationP])
    return [dualVertices, dualEdgeList]

Lien vers l'article suivant.

Liens externes

Notes d'un cours sur les DCEL de la Simon Fraser University :
http://www.cs.sfu.ca/~binay/813.2011/DCEL.pdf

Bibliographie

[1] DE BERG, Mark, VAN KREVELD, Marc, OVERMARS, Mark, et al. Computational geometry. Springer Berlin Heidelberg, 2000. (page 172, section 8.3)

[FIND] [TOP]