graphe planaire avec longueur maximale fixe des arêtes

Question

Je veux générer des points aléatoires dans un espace 2D, ces points seront des noeuds d'un graphe planaire (construit en utilisant l'algorithme Gabriel graph ou RNG). J'ai écrit du code java pour le faire, mais j'ai deux problèmes difficiles à résoudre.

1) J'ai besoin que tous les bords du graphe ne sont pas plus à un seuil donné

2) Après que je veux connaître les visages de graphique, un visage est un ensemble de noeuds connectés par le bord. Un visage ne contient pas d'autres noeuds. Dans l'image ci-dessous les visages sont signés par l'étiquette (F1, F2 ...)

Comment faire ces deux choses? des algorithmes? Il y a un moyen déjà connu?

Ci-dessous, il est un exemple du graphique que je dois créer

http://imageshack.us/photo/my-images/688/immagineps.png/

Answer 1

1. Si vous pouvez tolérer un certain écart du nombre de points, vous pouvez modifier votre algorithme de graphe de Gabriel être incrémentiel (la plus grande partie de l'effort consisterait à incrémenter votre algorithme de Delaunay), puis chaque fois qu'un bord est trop long, insérez un point aléatoire dans le cercle ayant ce bord comme diamètre.

2. Les structures de données les plus pratiques pour les graphes plans sont centrées sur les bords: par exemple, les représentations doubly-connected edge list et quad-edge. Si vous n'utilisez pas déjà une structure de données de ce type pour l'étape Delaunay (et je ne peux pas imaginer pourquoi vous ne le seriez pas), vous pouvez trier les connexions sortantes de chaque sommet par angle. De là, il est facile d'implémenter une fonction qui prend une demi-arête et retourne la demi-arête suivante sur la même face dans le sens inverse des aiguilles d'une montre. Passez maintenant à travers tous les demi-arêtes, et pour chaque demi-arête non déjà visitée, parcourez le visage jusqu'à ce que vous reveniez à l'endroit où vous avez commencé. Marquez tous les demi-arêtes de l'itération intérieure comme une face.