Trouver toutes les faces d'un polygone à partir de quelques diagonales.

Question

Nous avons un polygone, donné sous la forme d'une liste de sommets dans le sens inverse des aiguilles d'une montre en partant du sommet le plus bas( points ). Certaines diagonales du même polygone sont données (aucune d'entre elles ne se croise), comme un ensemble de paires de points ( diagonals ).

Nous devons trouver toutes les faces dans lesquelles le polygone est coupé (comme une liste de sommet pour chaque face).

Exemple :

La sortie comprendrait les visages suivants :

face1 = [(-68,-36), (-53,-40), (-39,44)]
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)]
...

Comme vous l'avez peut-être remarqué, les diagonales découpent le polygone en polygones monotones par rapport à l'axe des x. Si cela peut vous aider en quoi que ce soit.

Je suis sur ce problème depuis plusieurs heures maintenant. Je n'arrive pas à trouver un problème même lié à celui-ci. Toute aide serait appréciée, merci.

Modifier : Le problème peut être réduit à trouver tous les cycles simples dans un graphe(i.e. les cycles sans corde). J'ai trouvé ces questions similaires :

Trouver des polygones dans un graphe non orienté

Trouver tous les cycles sans cordon dans un graphe non orienté

Cependant, la solution retenue dans la seconde ne semble pas fonctionner.

Answer 1

1. Commencez par le polygone entier.

2. Prenez la première diagonale et divisez le polygone en deux. L'un aura les points jusqu'au premier point de la diagonale, puis tous les points après (y compris) le deuxième point de la diagonale. L'autre aura le premier point de la diagonale et tous les points jusqu'au deuxième point de la diagonale (y compris).

3. Prenez la diagonale suivante, décidez quel polygone sera divisé (ce ne peut être qu'un seul car les diagonales ne se croisent pas) et divisez-le comme décrit à l'étape 2.

4. Répétez 3. jusqu'à ce que toutes les diagonales soient traitées.