Lignes aux polygones

11

J'ai échoué à trouver le "nom" de l'algorithme qui permettrait de convertir des lignes en polygones. Depuis, ce problème traverse le SIG et les domaines de la géométrie numérique et de l'informatique. Je ne sais pas quoi ajouter au mix. Je suis réticent à fournir une liste de ce que j'ai recherché car j'aimerais également savoir quels autres personnes considéreraient leur premier choix de critères de recherche.

Le scénario ... J'ai des lignes (deux points nécessaires pour construire une ligne) ... chaque ligne est connectée à au moins une autre ligne. L'espace intermédiaire entre les lignes connectées formerait un polygone. Le scénario le plus simple serait un triangle ... un rectangle ... et l'on pourrait aller au-delà des entités multi-segmentées.

Désolé pour toute description vague, mais comme je l'ai dit, je ne veux pas guider les solutions possibles sur un chemin que j'ai déjà visité, car je suis autant intéressé par la "première pensée" que par la solution finale.

polygon algorithm geometry-conversion Germán Carrillo
la source
Les lignes peuvent-elles coïncider? Les lignes peuvent-elles se croiser? (c.-à-d. est-ce propre?) Si c'est le cas, j'espère qu'appeler ce processus Build ne serait pas trop spécifique à l'application.
Kirk Kuykendall
Kirk Les lignes coïncidentes et autres "défauts" auraient été supprimés avant la construction des polygones ... J'essaie de trouver le "nom de l'algorithme" qui, j'en suis sûr, a été implémenté dans divers packages SIG (par exemple arcgis). Donc, en bref, considérez que toutes les conditions dégénérées ont été traitées et que vous vous retrouvez avec des lignes propres (lignes à 2 points) qui coïncident aux nœuds que vous devriez pouvoir construire des polygones. La clé est que les lignes existent, il n'y a pas de conditions dégénérées et l'espace intermédiaire doit être converti en polygones. Merci
Les points sont-ils sur un plan ou sur une sphère?
Kirk Kuykendall
Kirk ... Sur un plan, les coordonnées métriques x, y, pas les coordonnées sphériques. Par exemple, supposons que vous ayez les segments de ligne qui formeraient un diagramme de voronoi, mais tout ce que vous avez, ce sont les segments qui le forment, mais pas la structure de données réelle qui y a conduit. En bref, chaque segment est connecté et chaque segment est unique.

Réponses:

4

Peut-être "remplissage de zone"? Voir ici et ici .

Éditer

Une autre possibilité est la triangulation contrainte . (Le lien est vers une applet Java qui vous permet de dessiner un graphique avec la souris, puis illustre un algorithme de balayage plan pour le trianguler.) Le résultat d'une telle triangulation, quelle que soit la façon dont elle est effectuée, peut facilement être traité pour créez les polygones souhaités: fusionnez simplement tous les triangles voisins qui partagent un bord nouvellement créé.

Exemple

Graphique d'origine:

Graphique d'origine

Graphique triangulé:

entrez la description de l'image ici

whuber
la source
Projet de loi Monter aux voix puisque je n'avais pas rencontré cela ... ne voulant pas limiter les autres commentaires de personnes dans diverses disciplines.
Bien que, traitant en grande partie des remplissages raster, c'est la réponse la plus proche. Je n'ai toujours pas de nom d'algorithme à moins qu'il ne soit attaché à un raster ou à un vecteur, mais un algorithme de "balayage" pourrait suffire, mais je ne peux pas comprendre pour la vie de moi pourquoi les coordonnées seraient triées par Y plutôt que X ( qui est facile à mettre en œuvre dans la plupart des langues).
@Dan Le tri par y ou x est sans importance, comme vous le suggérez. Vous avez également raison de penser que les algorithmes de balayage plan ou de balayage linéaire sont impliqués, mais malheureusement c'est une technique générale qui couvre presque toutes les procédures de géométrie de calcul, donc ce n'est pas un terme approprié pour rechercher spécifiquement votre algorithme. Notez que ce problème particulier n'est pas purement théorique, car il implique une incorporation du complexe polyligne dans un plan (ou une sphère), et donc un bon algorithme doit conserver des informations sur l'incorporation: c'est pourquoi c'est vraiment un problème de remplissage de zone au coeur.
whuber
5

En théorie des graphes , cette opération est appelée calcul des faces . Elle est liée au calcul du dual d'un graphe donné.

Par exemple, dans la bibliothèque Java GeOxygène , un graphe (appelé CarteTopo ) a une méthode getFaces pour récupérer son visage .

C'est ce qu'on appelle la polygonisation dans JTS

julien
la source
De bons liens. Cependant, ils présument tous que le problème de @ Dan a déjà été résolu: pouvoir appeler un graphique "planaire" signifie que vous avez déjà identifié les faces polygonales. Il veut savoir comment on peut convertir une collection arbitraire d'arcs (dans le plan) en un graphe planaire honnête à bon en premier lieu. Cela nécessite de construire une représentation de sa «topologie», comme un DCEL.
whuber
Merci beaucoup, vous êtes une source de connaissances! Je me demande comment quelqu'un peut être si brillant.
julien
4

Le logiciel hôte RepRap convertit une liste de segments de ligne (dans un ordre aléatoire inconnu) en une liste de polygones, ce qui ressemble à ce que vous essayez de faire.

En particulier, l' algorithme RepRap "End Matching" gère un tas de cas pathologiques.

Hélas, le logiciel RepRap suppose que chaque coin a un nombre pair d'arêtes y allant - 2 lignes allant à un coin sur un objet normal; 4 lignes allant ensemble lorsque le coin d'un objet touche le coin d'un autre objet, etc. Je ne sais pas combien il serait difficile d'adapter cet algorithme pour gérer les diagrammes voronoi, qui ont généralement 3 bords allant à chaque coin.

David Cary
la source
+1 trouvaille intéressante! Attention, bien que ce logiciel semble capable de résoudre de nombreux problèmes liés à la connexion de lignes en polygones, il peut en faire trop : il semble qu'il tente également de simplifier les fonctionnalités, ce qui peut être un effet secondaire indésirable. (Par exemple, il peut détruire l'intégrité topologique.)
whuber
3

avez-vous exploré la base de code de GRASS pour trouver une solution à votre problème? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
la source
1
Merci ... mais je ne recherche pas une solution "packagée" spécifique mais l'algorithme sous-jacent et / ou son nom qui viendraient des différents domaines du SIG, du Comp Geom et / ou du Comp Sci ... garder les idées à venir
Je pensais à regarder spécifiquement le code source derrière les 2 processus mentionnés dans mon lien pourrait vous aider.
étrangère à
Je suppose que je devrais installer le logiciel pour voir le code car je ne vois aucune liste sur ces pages, sauf si je manque quelque chose.
1
Vous pouvez parcourir la source GRASS en ligne: trac.osgeo.org/grass/browser
underdark
@underdark Merci pour le pointeur. Pour autant que je sache main.cdans la v.typesource, tout ce qui se passe, c'est que les entités sont renommées en tant que limites: aucun traitement réel ne se produit. Rétrospectivement, cela n'est pas trop surprenant: si (je ne suis pas sûr) les entités sont conservées avec des informations topologiques 2D complètes, alors tous les calculs pour identifier les régions polygonales ont automatiquement eu lieu lors de la création ou de l'importation des entités et sont conservés tout au long toutes les opérations de géotraitement.
whuber
3

Bonjour

Je ne pense pas que ce que vous recherchez soit un algorithme spécifique. La tâche peut être assez difficile ou très simple selon votre jeu de données.

Vous devez diviser le problème en au moins 2 parties. 1) est plus un problème de réseau, comment trouver des anneaux fermés de chaînes de lignes. 2) exprimer la chaîne fermée comme un polygone

La deuxième partie, qui consiste à "convertir des lignes en polygones", dépend davantage du format que de la représentation des polygones / chaînes de lignes. Je veux dire de:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

à:
POLYGON ((1 1,2 2,2 1,1 1))

convertit la ligne en polygone, mais ce n'est pas ce dont vous parlez, je suppose. La partie la plus difficile est la première. Si vous avez un spaghetti de lignes, comment les commander en tant que lignes fermées.

Je suppose que la réponse à cette question dépend en grande partie de l'ensemble de données. Comme Kirk le demande, si les lignes peuvent traverser, le problème est beaucoup plus important. Si vous savez que toutes les "collections de lignes" font partie d'une chaîne fermée, cela devient plus facile. Ensuite, vous pouvez saisir n'importe quelle ligne et marcher sur le chemin jusqu'à ce que vous soyez de retour, puis passer à l'étape deux ci-dessus.

Mon point est que la condition de l'ensemble de données définit toutes les règles sur la façon de le faire. Si vous voulez trouver tous les polygones possibles dans un spaghetti de chaînes de lignes, je suppose qu'il faudra beaucoup d'algorithmes différents pour mettre des points de sommet dans tous les croisements, rechercher tous les chemins possibles, etc.

Dans PostGIS, la fonction s'appelle ST_Polygonize. Cette fonction crée tous les polygones possibles à partir des chaînes de lignes que vous lui donnez.

Cela est effectué par GEOS afin que vous puissiez trouver les algorithmes derrière dans le code GEOS et JTS.

Juste quelques réflexions

/ Nicklas

Nicklas Avén
la source
1

Vous pouvez essayer de rechercher l'algorithme "Forward Star". On m'a dit que c'est générique, mais les seules discussions à ce sujet que j'ai jamais lues étaient toujours en référence à arcgis. Peut-être regardez les références citées dans ces notes de cours pour l'étoile en avant.

Kirk Kuykendall
la source
1
Je commenterai ici, même si ce commentaire traite également d'autres solutions proposées: le problème ne peut pas être représenté dans un réseau (ou graphique). Il nécessite des informations sur la façon dont les lignes sont connectées au sein d'une surface bidimensionnelle . Ainsi, les représentations d'étoiles vers l'avant / vers l'arrière seraient de peu d'utilité; un DCEL ou quelque chose comme ça est nécessaire.
whuber
@whuber - Je supposais que le commentaire de Dan selon lequel tous les "défauts" avaient été supprimés impliquait que les lignes étaient propres. En tant que tel, il devrait être possible de réduire cela à un problème de traversée de graphe de trouver tous les cycles dans un graphe. Au début, je pensais que l'étoile vers l'avant aiderait les algorithmes qui parcourent un graphique en prenant le virage à droite le plus net possible à chaque nœud. Cependant, en regardant un peu plus, il semble qu'il existe de meilleures façons. stackoverflow.com/questions/261573/… Mais tout de même, cela suppose que le problème peut être reformulé sous forme de graphique.
Kirk Kuykendall
1
La recherche de cycles dans un graphique n'est pas la même chose que la recherche de faces dans un graphique plan. Considérons le graphe abstrait avec les sommets {a, b, c, d} et les arêtes {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Une base pour les cycles se compose de a-> b-> d-> c-> a et a-> b-> c-> a. Dans l'incorporation planaire a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (où toutes les arêtes sont des segments de droite), le cycle a-> b-> d-> c-> a est pas un visage, mais si on se déplace d à (1,1), il est un visage. Cela montre pourquoi le concept de "face" nécessite que le graphe soit intégré dans le plan et pourquoi les faces ne peuvent pas être calculées uniquement à partir de la structure abstraite du graphe.
whuber