Comment vérifier si un ensemble de polygones plan crée un polyèdre étanche?

Question

Je me demande actuellement s'il existe un algorithme commun pour vérifier si un ensemble de polygones plans, pas nécessairement des triangles, construisent un polyèdre étanche. Chaque polygone a une oriantation (vecteur normal). Une solution simple serait simplement de dire oui ou non. Une version plus avancée serait de pointer les bords, où le polyèdre est "ouvert". Je ne suis pas vraiment intéressé par la façon de fermer les polyèdres.

Je voudrais souligner que mes "trous" ne sont pas nécessairement petits, par exemple, une face d'un cube peut être manquante. Ainsi, les algorithmes de "sous-échantillonnage de correction" ne semblent pas être la bonne approche. De plus, je parle de 100 - 1000, pas de polygones de 1000000, donc le temps de calcul ne devrait pas vraiment poser de problème.

Des conseils ou des astuces?

salutations les, conservateur

Answer 1

je crois que vous pouvez utiliser un simple test topologique - compter le nombre de fois que chaque bord apparaît dans la liste complète des polygones.

Si l'ensemble de polygones définit la surface d'un volume fermé, chaque arête doit avoir count>=2, indiquant que chaque arête est partagée par (au moins) deux polygones adjacents. Si la surface est exactement count==2.

Les bords avec count==1 indiquent les zones ouvertes de la surface.

Answer 2

La réponse ci-dessus ne couvre pas beaucoup de cas. Un algorithme plus correct (mais pas nécessairement complet: je ne saurais dire) consiste à s'assurer que chaque bord de chaque polygone (ou du maillage/polyèdre) a un nombre pair de faces qui lui sont connectées. Considérons la maille suivante:

Le segment (line) entre le plus proche sommet et celui ci-dessous est fixé sur 3 faces (un un du triangle externe et deux du triangle interne), qui est plus grande que deux visages. Cependant, ce n'est clairement pas fermé.