Générer des polygones à partir d'un ensemble de lignes qui se croisent

10

C'est une question simple et assez courante qui a déjà été posée à des fins différentes (voir ce lien et cela aussi , par exemple), ici, cependant, nous ne recherchons pas un progiciel mais des algorithmes que nous pourrions essayer d'implémenter disons dans Python .

Ainsi, comme illustré ci-dessous, un ensemble de lignes est mappé (elles sont déjà coupées, BTW).
Algorithmes / idées pour générer des polygones (comme les rouges le montrent) ?

entrez la description de l'image ici

algorithm polygonize geometry-conversion Développeur
la source
La frontière du carré extérieur est-elle connue, ou est-ce aussi, à lire à partir des lignes d'entrée?
Devdatta Tengshe

Réponses:

5

Eh bien, nous mettons ici une réponse qui n'est pas une réponse complète à notre question, c'est-à-dire que la question restera " ouverte à la réponse ". C'est cependant une solution au problème de la question. Voici l'astuce que nous avons utilisée:

Voyons d'abord les résultats :
entrez la description de l'image ici

Ainsi, les lignes données dans les leftpolygones construits indiqués dans le middle. Ce sont de vrais polygones comme le montre le right;)

Pour l'algorithme donné ci-dessous, nous avons utilisé le Shapelypackage en Python .

  • lignes ==> MultiLineString {:: M}
  • ajoutez un petit buffer, dites eps{:: MB}
  • region ==> Polygon {:: P} (région ici est un carré)
  • P.difference(MB) {polygones résultants}

Notez qu'il est silencieux et rapide en fonctionnement. Cependant, le point manquant est que l'algorithme n'est pas une méthode originale pour construire un polygone à partir de lignes . Néanmoins, cela a parfaitement fonctionné pour le problème que nous avions dans la main.

Développeur
la source
4

JTS Topology Suite a une classe Polygonizer, qui fait à peu près cela.

Vous pouvez consulter le code source, disponible ici , et le convertir en Python.

Devdatta Tengshe
la source
Comme l'indique la description du code, cela ne fonctionnera pas comme prévu par l'auteur de la question: "les bords doivent être correctement inclinés; c'est-à-dire qu'ils ne doivent se rencontrer qu'à leurs extrémités. Le polygoniseur fonctionnera sur une entrée incorrectement inclinée mais ne formera pas de polygones à partir de -noded bords "
Pablo
1
Il existe une opération dans JTS pour diviser correctement les lignes aux sommets. Peut-être que le PO pourrait examiner cela également.
Devdatta Tengshe
3

Vous pourriez jeter un œil au package Python Shapely, en particulier polygonize ()

Dave
la source
Une note rapide qui polygonise dans Shapely ( from shapely.ops import polygonize) utilise GEOS.Polygonize de GEOS . C'est donc un lien où il y a un lien vers un lien ...: |
Développeur
Nos essais avec polygonizen'ont pas réussi du tout. Cependant merci de nous avoir rappelé Shapelyavec qui nous pourrions trouver une solution (une astuce, en fait) telle que publiée comme réponse.
Développeur
2

Voici une autre solution que nous pourrions trouver.

En utilisant, DCELnous pouvons faire des blocs en touchant des lignes.

Pour Python, il y a un package {ici} . C'est une minuscule implémentation avec quelques bugs. Néanmoins, avec un certain effort, il peut être utilisé pour ce problème. Notez également les étapes suivantes:

Une étape de prétraitement avec laquelle toutes les intersections entre les lignes sont trouvées. En conséquence, toutes les lignes sont divisées en segments aux points d'interaction. Une liste de points d'intersection et une liste d'arêtes associées sont celles nécessaires pour DCEL.

Développeur
la source
Comme cette méthode est une solution originale et donne de bien meilleures performances par rapport à l'autre méthode dans laquelle l' differenceopération est utilisée.
Développeur